コンテスト後のツイート
D xとyでかぶった色がない場合、indexの近い別の色のものを二分探索で探し、そこを経由した行き方が答え。
— titia (@titia_til) August 15, 2024
E 実験したらGrundy数がエラトステネスの篩で求まると分かった。
F. Make a Palindrome
解法ツイートを参考にAC。
コンテスト中に三乗で解く解法は思いついていた。
配列Aにおける値は、
・配列Aの左端右端の要素が同じなら消す。違うなら、小さい方を合体させて答えを一つ増やす。これでO(配列の長さ)で求まる。
で求められる。
この計算量を落とす方法が分からなかったが、累積和を使って特徴づけできる。
「両端の要素が同じなら消す」という操作をできるだけ増やしたい。a, b, c, dをindexとして、(a, b)から両端を消すことで(c, d)へもっていくことにすると、累積和Sについて、
・S[b]-S[a]=S[d]-S[c]
が成り立つ。これを変形して、
・S[a]+S[d]=S[b]+S[c]
なので、二つの累積和の和が同じ物を集め、index i, jについてj-iが小さい方から見ていくと、(z, w)の後に(x, y)がきた（S[x]+S[y]=S[z]+S[w]が成り立っている）なら、DP[x][y]=DP[z][w]=(z-x-1)+(y-w-1)のようにして全ての値を求めることができる。
0 件のコメント:
コメントを投稿