Educational DP contest P-S
いつの間にか土曜にBeginnerコンテストが追加されていた。
目標はパフォーマンス1500, rate1000載せ。ここまで順調なのでそろそろ失敗しそう。
ABCの3完は確保したい。
今日は3問 + 途中で終了。
EDPコンテストも後半になって１問１問が重くなってきた。
コンテストの設計として、序盤は200点ぐらい、終盤は800点ぐらいの感覚らしい。
J-Sushiあたりから明らかに難易度が上がっている。
Q問題のようにセグ木を要求するものや、Rのように繰り返し自乗法を要求するものなど、DP + αが必要な問題が出てきている。
S問題はまだ終わっていない。方針は立っているのだが、実装で混乱したまま。
桁dpはまだ練習量不足が否めない。
以下、解答メモ。
P - Independent Set
treeなので、特定のノードをルートとして考えて良い。
dfs順で見たときにあるノードを黒に塗ると、その先のノードは全て白で確定する。
あるノードを白に塗った場合は、その先は任意。
木が一直線であれば
dp[i][0] : i番目が黒のときのi番目までの塗り方
dp[i][1] : i番目が白のときの…
dp[i+1][0] = dp[i][1]
dp[i+1][1] = dp[i][0] + dp[i][1]
で良い。branchをどう処理するか。
葉から決めていったほうがいい。
dp[i][0, 1]を、iを根とする部分木の塗り方の総数とすれば、
dp[root][0] + dp[root][1]で解が得られる。
メモ化再帰によってこれを葉から決めていく。
漸化式は
dp[i][0] = Π dp[ children ][1]
dp[i][1] = Π( dp[ children ][0] + dp[ children ][1])
各部分木の塗り方の積で計算
探索済みフラグの処理が面倒。上位ノードが白の場合と黒の場合で２回探索が入る。
-> 部分木の探索を終えた段階で再びunusedにすれば良い。木なので不都合は生じない。
-> WA & TLE。WAは計算途中のint溢れ。TLEは、上でunusedにしてしまっているので当然だった、
結局探索済みの管理をどうするか。
木なので、自分の親に遷移しないという条件だけで十分。再帰関数に、部分木の根とその親をもたせる。-> AC
Q - Flowers
LISに似ているが、評価値が部分列の長さではない。
int 溢れに注意。
制約からして、どの花を残すかを考えるのは不可能。
i 本目までで作られる部分列でSUM(ai)最大のものが分かっているとき、
i+1本目が来たときにあり得るケースとしては、
・単純に部分列の右端に追加
・部分列の一部を削りh_{i+1}を入れる。
の2パターンがある。
LISの時を思い出すと、長さnの部分列のうちで最も右端の値の小さいものを配列に記録するするという方針。
この配列は必ず単調増加になるので、二分探索によってO(L log L)で更新できるという話だった。
dp[i][0] =index of rightmost, length i
dp[i][1] = sum of a, length i
としてみたらどうか？
新しいエントリーに対して取りうる操作は、単純に右に追加する or 一番右の要素を置き換える。
このままでは、各 i に対してlengthのループが回るのでO(N^2)。これを二分探索とかで減らしたい。
dpの更新が発生するのは、
a_i+1 - dp[k][0].a >= 0 かつ dp[k][0].h>= h_i+1のとき。
-> 各 i で最適にしようとすると、新しい i に対してO(N)の更新が必要になる。
-> わからん。
花の高さについてdpすると良いらしい。
「h <=N でh1…hNが全て異なる」という制約をもっと真剣に捉えるべきだった。
最も右端がh_iであるような部分列の最高値をdp[h_i]とすると、
dp[h_i] = a_i + max( dp[h_j] where h_j < h_i and j < i)
が成立する。これをiの小さい順に更新していけば良い。
maxを求める部分はセグメント木を使ったRMQで O(log N)にできる。
RMQ要求する問題はAtCoderでは初めて出会ったかも。
LISっぽいところに気づくのは良かったが、そもそもLISの解法を間違って覚えていた。
正しくは、dp[h] = 部分列の最大要素がhのときの最大部分列長
LISっぽい -> dp[h]かな？ -> でもa_iだから単調じゃなくて二分探索できない -> じゃあ気合でRMQ
という思考の流れができれば解ける問題。
セグメント木はスニペット化してあるのでそれを使ってAC。
R- Walk
Kの制約がバカでかい (K<=10^18)。
Nが小さい。O(N 2^(N/2))が回るぐらい。
とりあえず、始点についてのループは必須。
Kについてdpすることができない。
dpするにしても、まず全探索だとどうなるか考える。
Kが大きいときはひたすらループを回して稼ぐことになる。
ループを使わない場合の最大パス長はNなので、 K>=Nであればループの検出が重要になる。
Kそのままでは管理できない。仮にK = 2^nとしてみる。
dp[i][j][n]: 始点 i, 終点 j でパスの長さ 2^nの組み合わせとすると
dp[i][j][n+1]は、2^nのパスと2^nのパスの連結なので、
dp[i][j][n+1] = Σk dp[i][k][n] * dp[k][j][n]
という漸化式が書けそう。 ここまでは10^7ぐらいのループで回る。
上記が求まっていれば、Kのビット表示から計算できるはず。
たとえば、 K = 5 = 4 + 1は dp[0]とdp[2]から。
この場合、長さKで始点i, 終点jのパスの総数は、
Σ_k dp[i][k][0]*dp[k][j][2]
で与えられる。しかし、このままだと計算しきれない。
dp[i][k][n]を、i, kを足に持つ行列 M[n] と見ると、求める値は
M[n1] M[n2] … M[kn]
の全要素の和で(N^3)^kなので回らない。
-> いや、O(k N^3)だろ何言ってんだ。
そんなこんなで、時間はかかったが一発AC。行列積のコードをミスっていて気が滅入ったが。
bit DPを正しく着想できたところは非常に良かった。
解いてから冷静に見直してみると、入力行列をK乗して全要素の和を取ればパスの総数になるということ。
上で書いたDPはこれを繰り返し自乗法で処理することに相当している。
dpの漸化式を立てた段階で行列積の形であることをもっと意識すれば、後半でグダることはなかったはず。
これで18問。最初の頃に比べて明らかにコード長が長くなってきたが、
dpは方針さえ正しければバグでWAを出したりは起こりづらい印象がある。
(バグっている場合はたいてい入力例すら通らないので)
5時間で26問はDP力もそうだが精神力が試されてる気がする。
EDPコンテストは、序盤200点相当、終盤800点相当の設定らしい。今は600点相当ぐらいだろうか。
TDPコンテストの難易度が不安である。
少し休憩して今日はあと1問やろう。
S- Digit Sum
露骨な桁DP
Dの倍数という部分がややこしい。
桁和の取りうる範囲は、1-900000
桁和の値を保持しながらのDPは不可能。
まず、桁和がDそのものであるものを求める問題を考えてみる。
桁和がDジャストの場合の問題が解けていれば、2^20 > 900000なので、高々その20倍の計算時間で解ける。
dp[i][j][d]を、i桁目まで見た上でK以下のフラグがjのときに桁和の値がdであるような組の総数
とする。
jは、上位桁が全てKと同じときにfalse,それ以外ではtrueとなる。
桁和をなんにせよ確定させないといけないので、後ろから埋めていくDPになる。
Dを超えるものについて切りたい。dをmod Dで考えれば一度に計算できる？
Kの桁数をN。Kのi桁目までの桁和 mod DをS[N], i桁目の値をk[i]とする。
dp[N][true][S[N]] = (S[N] == 0 mod D) //// others 0
dp[N][false][x] = SUM_{i=0…9} (1 if x+i == 0 mod D) /// 最終桁で調整できる。Dは10以下もあるので、この時点で複数の可能性もある。
dp[N-1][true][S[N-1]] = dp[N][true][S[N]] + dp[N][false][S[N-1] … S[N-1] + 9] // others 0
dp[N-1][false][x] = dp[N][false][x … x + 9]
dp[i][true][S[i]] = dp[i+1][true][S[i+1]] + dp[i+1][false][S[i] … S[i]+9]
dp[i][false][S[i]] =dp[i+1][false][x … x+9]
これで、O(2*D*10000 * 10)になるはず。O(10^7)なので回りそう。
-> 全然合わない…。0の処理がよくわからない。
明日に持ち越し。
