2015年5月6日水曜日

SRM 658 Div1 Med : Mutalisk

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13761
n個の箱があってそれぞれの箱にx[i]個の玉が入っている。
1ステップで3つの箱を選択し、
最初に選択した箱から9個以下
2番目に選択した箱から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みたいなことをすれば良い。

0 件のコメント:

コメントを投稿

解の個数を減らす帰着 (Valiant--Vaziraniの定理)

2月に 冬のLA に参加してこれまで5,6年くらい常に取り組みようやく身を結んだ共同研究を発表してきました. 2月のLAではD2辺りからずっと取り組んでいた個人的未解決問題がある程度解決できたことについて発表させていただきます。 — Nobutaka Shimizu (@kn...