問題ページ G - Coinage 考えたこと どちらか優先すべき文字列を連続して置いたあともう一方を連続して置くべきっぽいので優先すべき文字列を決定する sとtのうち辞書順で小さい方をできるだけ並べたあと残りを埋めればいい気持ちになって出すとWA s="bb", t…

問題ページ 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の深さをそろえた後頂点が一致するまでたど…