Fまで。
コンテスト後のツイート
F DP。Kが小さいので、index iまで見て、最後の二文字がj,kで、元の部分文字列よりk(<=K)個ABCが増えているときの最小の交換した個数。
— titia (@titia_til) June 13, 2026
G 攪乱順列（完全順列）の求めかたと同じようにできるのでは？ と思い考えていたが、漸化式も包除原理も上手くいかなかった。
G - Completely Wrong
解説放送を見てAC。包除原理で解ける。
Cを並び替えたもののうちk箇所が一致（C_i=G_iとなる箇所がk箇所）しているものを求めたい。
これを、各色ごとに求めて、それを合わせることにより求められる、と考えるのがポイント。具体的には、FFT（畳み込み）を使って計算できる。
最後に、包除原理を用いて、kが奇数のとき-1の係数をかけて足し合わせれば良い。（解説放送では-1を掛けるのをFFTする前にやっていたけど、最後にやってOKですね。その方が分かりやすいと思う）
0 件のコメント:
コメントを投稿