脳log[20230326]

2023年03月26日 (日) [AtCoder] 精進１。昨日あった ABC295-D「Three Days Ago」(緑 diff)。いやあ、これ難しいよ。一日置いてもまだ考えたもんね。組み合わせを考える N^2 の処理が許されないから、右端を決め打って右端にある文字に応じて決まる嬉しい文字列の左端を数えることが許されない。よね？■提出 #40082295 (AC / 116 Byte / 145 ms)。昨日には訪れなかったひらめきはこう。文字列の先頭からの累積で 0-9 の数字の出現数の偶奇を記録する。状態数 1024。そのビットパターンの出現数を記録する。たとえば 10 文字目までの累積でビットパターンが 0b1010011000 になったとする。そしてこれまでに 4 文字目までの累積と 6 文字目までの累積でも同じビットパターンが出現していたとする。すると (l,r) = (4,10),(6,10) が嬉しい文字列としてカウントできる。これって全然明らかではないよ。１文字目からの累積状態を記録していく。数えるのは現在の累積状態と同じ状態の数。知りたいのは区間の状態だけど先頭からの状態と状態を比較する。前回の ABC-G について書いた「根からの距離がわかると２頂点間の距離がわかるか？ 「頂点 1 からのパスによって決まる値だけを考えて答えを出していい理由は、たぶん LCA までのパスが相殺されるからとか？」からの連想で、LCA を使って引き算すれば求められる気がした」。これと同じレベルの考察だと思うよ。ABC294-G や ARC045-C と同じ。でもまあ、解かれたからの緑 diff 下位なんだけど。しかたない、AtCoder には自分を除いて天才しかいない。■■■精進２。ABC232-F「Simple Operations on Sequence」(青 diff)。以前は TLE だった。N≦18 という制約を見て２週間前の精進を思い出す。「順列総当たりが許されない制約(N≦16)だけど、A<B、A>B を区別せずに２回目以降の数え上げがサボれるなら許される」。提出 #40085558 (AC / 1181 ms)。はい、許されました。