技術室奥プログラミングコンテスト#6 Day1

 　EまでとH、Jの七完。

コンテストへのリンク

F - Frog and Tadpole

　自力AC。

　xマスにいたカエルがyマスへジャンプするとする。このとき、x+1～y-1にあるマスは、白マスでも黒マスでも良い。

　なので、マスiまでたどりつく場合の数をDP[i]とする（つまりDP[N]が答え）と、

・DP[y]=DP[y-1]+2*DP[y-2]+...2^(y-x-1)*DP[x]

　となる。

　このままだと二乗の計算量だが、累積和を使って高速化すると間に合う。

G - At Most Two

　最長共通部分列 (LCS)は二次元DPにより求められる（たとえば、この解説）。

　だが、実質的に値が変わるのは、A[i]とB[j]で同じ値が含まれる箇所のみ。

　B[j]と一致するのがA[k]とA[l]のとき、

　DP[k][j]=DP[k-1][j-1]+1, DP[k][l]=DP[k-1][l-1]+1

　と変更されうるのは二か所のみ。

　他のxについて、DP[x][j]は、DP[x][j-1]と一致している。

　なので、区間最大値を取得できるセグメント木を使ったDPで更新していける。

　……と、文字で書くとこんな感じだけど、二次元の絵を描かないと分からないと思う。LCSは二次元DPだから、今回もとりあえずその絵を描いてみる、というのが重要。

I - 1<->k

　解説AC。

　コンテスト中なら、実験エスパーを目指すのが最善だろうけど、なぜか実験していなかったよう。

　解説二行目、「中国剰余定理よりf(n)は乗法的関数」というところがなかなか理解できなかったので、そこを埋めておきます。

　中国剰余定理（参考）は、

　p, qを互いに素な生整数としたとき、任意のa, bについて、

・x=a (mod p)

・x=b (mod q)

　を満たす整数xが[0, p*q)　にただ一つ存在する。

　というもの。

　この定理で、a=b=1の場合を考えると、x=1は「x=1 (mod p), x=1(mod q)」を満たすので、

・x=1 (mod p), x=1(mod q)　を満たすのはmod p*qでは x=1 のみ（*）

　と分かります。

　ここで、

・y^2=1 (mod p)

・z^2=1 (mod q)

　となるy, zを考えます。中国剰余定理を使うと、

・x=y (mod p)

・x=z (mod q)

　となるxが[0, p*q)　にただ一つ存在しますが、x^2=1 (mod p)、x^2=1 (mod q)なので、（*）より、x^2=1 (mod p*q)　と分かります。

　長くなってしまったけど、こんな感じで良いはず。ここを乗り越えれば、その後の解説は追えるはずです。

K - Dial Key

　解説AC。

　自分では、

　各要素について、「区間に+1/-1」した後、「ある要素に+1/-1」を用いて調整するしかない。ので、一つ前の要素について「区間に+1/-1」でいくつへ変更したか？　を持ってDPすれば良い。

　……みたいなことを考えていたが、これではダメ。先の方まで区間を使った後、前の部分を処理することがある。

　正しくは、「区間へ+1する処理」→「区間の前と後の二か所で差が変わる」と考えるのがポイント。これは典型の一つなのに思いつかなかった。反省。

　ただ、その後貪欲にやって良いというのもピンと来なかったので、自力ACは結構遠かったかな。