Fまで解けたが遅かった。
コンテスト後のツイート
AtCoder Beginner Contest 452 Fまで。
— titia (@titia_til) April 4, 2026
C len(S)ごとにSを列挙し、(Ai,Bi)の候補を挙げておく。
D 久しぶり。https://t.co/NeYvsecE9N
E Bのindexを固定とすると、0 1 2 0 1 2……みたいな係数をA[i]にかけて和を取るものになる。累積和で頑張る。計算量に調和級数のlogがついた。
G - 221 Substring
自力AC。
コンテスト中の方針であっていた。数字の個数=数字の大きさならそのまま、個数が数字の大きさより大きければ、k 0 kと置き換えて並べる。
その上で、Suffix array、各indexから0までの個数を調べていく。そのままだと重複が出るが、LCP配列を使えば重複は除ける。
コンテスト中に失敗していたのは、自分のライブラリだと文字列Sの後ろに、最も小さい文字(今回は数字)を置いておかねばいけないところだった。あとは、SA[i]でi番目に小さいindexを表すのだが、その逆関数なのかどちらか分からなくなって混乱したところ。ただ、これは久しぶりにSuffix arrayを使ったのだからしょうがない気もする。
後はすんなりできた。
Fより時間かからなかったと思うので、F捨ててG行けば通せてたかなぁ。
0 件のコメント:
コメントを投稿