問題ページ F - Capture 考えたこと 尺取りとかするのかと思ったがどこまでで区間を伸ばすのを止めるのかわからない iまで網をかけている状況で[i,i+1]に新たに網をかけたときの利益の増加はv[i] = s[i+1] + (x[i+1] - x[i])になる 数列vの累積和を取れば区…

問題ページ E - White and Blue 考えたこと 全員反対した状態から1人ずつ賛成にしていき条件を満たしたタイミングで判断する 白票が多い順に賛成にしていくコードを書いたらサンプル通ったので投げると落ちる 白が少なくても青が多い人の方を先に賛成にする…

問題ページ D - Shock 考えたこと 頂点1が含まれる連結成分V1と頂点2が含まれる連結成分V2とそれ以外の頂点集合V3に分割して考える V1とV2の頂点が繋がれることはありえない V1とV3をつなげばV2とV3をつなぐのは不可能で逆も同様 V1とV2で要素数が多い方をV3…

問題ページ C - Garden 考えたこと 位置Yがk番目に植えられる花の位置X以上かを判定する問題を考えるとO(N)で解ける 各iについて(Y-w[i])/d[i]+1が位置Yまでに植える花の個数になるのでこの合計がK以上かどうかを見ればよい 上の問題は単調性があるので二分…

問題ページ B - Evergrowing Tree 考えたこと 同じ頂点にたどり着くまで上にたどっていけばよさそう 完全N分木なのでダブリングしなくても上にたどるのは対数オーダー 根を0とすると頂点vの親は(v-1)/Nになる vとwの深さをそろえた後頂点が一致するまでたど…

考えたこと 問題文を整理するとn頂点のグラフで同じ色の頂点が隣り合う数を最小にした全域木を求める問題 グラフでは頂点条件を辺に置き換えるといいというのを見たことがあったので考えるhttps://www.slideshare.net/tmaehara/ss-17402143 同じ色の頂点が隣…

考えたこと 奇数の和は平方数なのでx+yが平方数でなければ不可能 sqrt(x+y) でターン数は求められる できるだけ少ない個数の奇数の和で表したいので大きい奇数から貪欲に使っていけばいい気がした この貪欲でつくれない数が存在しない気がしたので出したら落…

考えたこと Nが一個あったら該当する一列には置くことはできない おけないところを全て消し、置けるところだけからなる連結成分ごとに考えてよさそう 連結成分に全部置いたとして'Y'の条件を満たすような連結成分が存在するか判定するとよさそう 愚直な実装…