CODE FESTIVAL 2018 qual A C - 半分

• 問題

解法

関連した以下のような簡単な問題について考える.

• n個の0があり,K回だけ 0<=i < n なるa_i を+1 する操作を行う. 数列は何通りできるか.

これは以下のようなO(NK) の DPで解くことができる.(普通にコンビネーションでも解ける)
def : dp[i][j] := ( 前からi個取った数列 {a_0, .., a(i-1)} に対して j 回 操作を行った時のできる数列の数 )
初期化 : dp[0][0] = 1 , dp[0][k] = 0 (k>0)
漸化式 : dp[i+1][j] = sum(0<= k <= j)( dp[i][j] )

これに沿ってこの問題を考えてみると,以下のようになる

• 数列の各要素に対して以下の操作を合計K回行う. 数列は何通りできるか
• 操作は cnt_i = floor( log2( a_i) ) + 1 として, cnt回行うまでは毎回違う数に変化し, cnt回以降はずっと0.

この問題に対して先ほどと同じDPは使えない.
なぜなら a_i に対して cnt_i 回操作を行った場合とそれより多く操作を行った場合を複数回数え上げてしまうため.
なので, disjointに数え上げるために以下の制約を付け加える.

• a_i に対しては cnt_i 回までしか操作を行えないとする

この制約を付け加えた時点で,求める答えが変化することに注意する.

• 元々条件での答え
• : 合計K回操作を行った数列の数
• 制約を加えた時の答え
• : 合計K回操作を行った or 何回操作をやったかに関わらず1つでも0を含む数列の数 制約を加える前は 0 ができたら何回でも操作を稼げたが,制約でそれができなくなったからである.

またK<=10⁹だが, A_i <= 10¹⁸ < 2⁶⁰ より cnt_i < 60.
つまり 操作は 数列全体に対して 60N回もできないので K = min(K,60N) とすれば良い.

答えを数えるために,以下のようにおく.
dp1[i][j] := ({a_0, .. ,a(i-1)} が0を含まず,j回操作を行った時の組み合わせ)
dp2[i][j] := ({a_0, .. ,a(i-1)} が0を含み,j回操作を行った時の組み合わせ)

この時, a_i にk回操作をすると考えると漸化式が立てられる.
dp1[i+1][j] = sum(0 <= k < cnt_i ) dp1[i][j-k]
dp2[i+1][j] = sum(0 <= k <= cnt_i )(dp2[i][j-k]) + dp1[i][j-cnt_i]

答えはdp1,dp2が全てdisjointであることを考えれば
dp1[K][N] + sum_( 0<= j <= K ) dp2[i][j]
で求められる.

メモ

まあ解けなかったんだけど

コード