時間ギリギリ全完でした。
G2の方針自体はもっと速く思いついていたんだけど、これで計算量が良いかで迷い、またSortedSetを使わなくては実装できないのか？（使ったらTLEするのでは？） といったあたりでも迷って時間かかってしまった。
あと、並列二分探索でできないか？ などとも考えた（できなかった）。
実際に実装してみたらACでした。
コンテスト後のツイート
F 累積xorを取りこれをXORとする。l～rのxorが0ならOK。違うときは、間に、XOR[r]と同じもの、XOR[l-1]が含まれれば良い。
— titia (@titia_til) May 2, 2024
G1 Z algorithmした後二分探索
G2 x文字をLCPに持つものは何個取れるか？ を全探索しても、次の場所を二分探索していけば、二分探索のlogと調和級数のlogの二つで済む。
0 件のコメント:
コメントを投稿