SRM 658 Div1 Med : Mutalisk

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13761
n個の箱があってそれぞれの箱にx[i]個の玉が入っている。
１ステップで3つの箱を選択し、
最初に選択した箱から9個以下
２番目に選択した箱から3個以下
最後に選択した箱から1個以下
の玉を取り出すことが出来る。( 例えば玉が6個しかなくても最初に選択して6個取り除いても良い)
全ての箱から玉を取り出すには最小で何ステップ必要かを求める問題。

解法(Div1)

(heekyuさんのコードを参考にしました。とてもシンプルで分かりやすいコードです)
二分探索+DP.
r回で全部なくすことが出来るかどうかをDPで判定する。
dp[f][i][j][k] = x[0]~x[f]までを1をi回,3をj回,9をk回使って全て0以下にすることが出来るかどうか
とすると、
仮に9をa個、3をb個使うとするとx[f]を0にするためには1は x[f] - 9*a - 3*b 個必要になる。この値をneedOneとしてdp[f+1][i-needOne][j-b][k-a]を調べれば良い。
このとき{60}みたいな入力に対しては1と3と9を同時に使おうとして実際の答えは60/9+1 = 7なのに60/(1+3+9)+1 = 5ってなっちゃうのでそこを注意する。
具体的には a+b+needOne <= rかどうかで判定すれば良い
たとえば{60}の例だと
1が5個、3が5個、9が5個で合計15個 > 5=r →はじかれる
1が0個、3が0個、9が7個で合計7個 <= 7=r   →はじかれない

解法(Div2 Med)

Div2Medだとn=3と固定されているので,
dp[i][j][k] = x[0]にi個、x[1]にj個、x[2]にk個入っているときの最小ステップ数
とすれば、1,3,9は3!=6通りの並べ方があるのでそれぞれに対してdp[i-1][j-3][k-9]+1みたいなことをすれば良い。