Codeforces Div.1 #641

https://codeforces.com/contest/1349/my

ABCの3AC10WA。頭が悪かった。

A問題

素因数ごとに分けてよくて、入力は$1,p,p^2,p^3,\ldots$だけで構成されていると思っていい。このときの答えは最小から二番目の値になる。

B問題

ややこしい解法になった。Kの隣にK以上のものがあれば構成可能なのはよくて、そうでないとき。Kの塊を作ることを考える代わりに、K以上の塊を作ればよい。K以上の塊が作れる条件は、過半数がK以上となるような連続部分列が存在することなはずで、自分は次のような方法で判定した。

K以上であれば1、K未満であれば-1の配列を作る。累積和を取るとi番目からj番目までが過半数かどうかはS[i]-S[j-1]>0で判定できる。

もっと効率的に判定できて、11または101があればよい。直観的には1の同士の間に0が二つ以上ある場合、1の個数は1/3程度にしかならないため。一応帰納法で示す。Xが過半数の列を持つならば11または101を持つことを示す。

• 長さ3以下は基底。
• X=[0]+Yのとき、Xが過半数の列を持つならばYも持つ。
• X=[1,0,0]+Yのとき、Xが過半数の列を持つならばYも持つ。
• X=[1,0,1]+Yのとき、[1,0,1]が過半数の列である。
• X=[1,1]+Yのとき、[1,1]が過半数の列である。

C問題

最終的に周期2で繰り返すのは何となくわかって、周期にたどり着く時間もおよそH+Wっぽい気がして、さらにbitsetで高速化できることに気付いて、ほとんどシミュレーションみたいな解法で通してしまった。