htkb-proconの日記

初心者がPythonで問題解いた記録

CODE THANKS FESTIVAL 2018 E - Union

E - Union

解説見てもDPの回し方にしばらく悩んだのでメモ。

dp[i][j] := 整数i-1まで余りなく処理したとき、iにj個持ち越した場合の数

って感じの流れは思いつけたんだけど、なーーーーんでか各iを1個残した場合と全部使い切って次に回す場合の場合分けってどうするの??とか意味不明なことを悩んでいたんだけど、*自明*な事実として、数列の中で最大ではないある数を1個だけ残し、それ以上の数をなんとか処理して0個にすることは不可能なので、最後に残る1数は元の集合に含まれる最大の数以上に限られる。よってDPの遷移は常に今見ている数を使い切るように回し、その上で各iが数列の最大になるケースを考え、

dp[i][0] -> i-1まで全て処理できていてiへの持ち越しも無い。
            よってai >= 1ならばiに1を取ることで条件を満たせる
dp[i][1] -> i-1まで全て処理できていてiへの持ち越しが1個。
            よってiに0を取ることで常に条件を満たせる
dp[i][2以上] -> i+1に持ち越さずにiを1個にすることは不可能

みたいな感じなのでdp[i][0] (ai >= 1)dp[i][1]を答えに加算していく感じ。T以降も重ねた分を処理しなきゃならないのでT+10くらいまで(log2 300 < 9)DPを取って、aT以上は0扱いにしてDPを回す。

あとはiを重ねてi+1に持ち越すとき、iを余らせない場合の数だけ数えるのでiが偶数になるケースだけ考えるんだけど、(iに持ち越した数+iの数)//2(切り捨て)とかしちゃうと(1+0)//2 = 0みたいな1個持ち越し分を捨てるような遷移を数えちゃったりするので注意(説明力の限界)。

Submission #3680749 - CODE THANKS FESTIVAL 2018(Parallel)