beet's soil

競プロのことなど

ACPC VC 2019/12/04 DIV1

実装力、破滅…

高橋君とホテル / Tak and Hotels

ダブリングをします 終わり なんでバグるんですか?(4敗)

aからbへの移動回数を求めるときは以下のようにする

十分大きなkから考えて、2^k回移動してもbにたどり着かないなら移動する
最後にちょうど1回移動する

あるkで移動しなかった場合、移動に必要な回数は  2^k 回以下である
 \sum_{i=0}^{k-1} 2^i = 2^k - 1 であるからちょうど  2^k 回必要な時はこれでよい
そうでないならある l (l \lt k) で移動しないはずで、帰納法が回る

dbl[k][a]<=bでやると右端で大変なことになるので気をつけよう!

最良表現 / Best Representation

自明なケースを除くと分割は2つ 証明:前それで解いた

文字列の周期という概念がある
周期を二つ持つとき、そのgcdもまた周期になる

今日つぶあんくんに教えてもらった簡潔な証明:
Sを元の文字列を前後に無限個付け足した文字列とする
S[a] = S[a+x]=S[a+x+y]=S[a+kx+ly]
なので、拡張ユークリッドの互除法を考えるとgcd(x,y)のところは全て等しい

gcd(n,n-1) = 1 であることから、w[0:n) とw[0:n-1) が共に文字列の繰り返しで表される場合、全ての文字が同じ文字列になる そのケースは自明

あとは文字列の長さを決め打ってLCPをすればよい 今回はprefixとsuffixだけなのでZ-algoでできる
まあめんどくさいからSuffixArray+LCPを貼った

ヘラヘラしながら二重ループを書いたらO(N^2) になっていた(なんで?
調和級数にするやつは前計算するのが楽

AND Grid

あまりにも有名
www.nicovideo.jp

総評

競技プログラミング初心者ですか?