SRM658 Div1 Medium "Mutalisk"
考えたこと
まず、サンプルを良く見る。
!!
Sample5で制約MAXでやってるやーん!
最大でも93回でいけるのか!(サンプルから重要な情報を拾うとは今日は冴えてるぜ俺)
・・・
うーん、DPかな?
dp[i][c9][c3][c1] := 最小の攻撃回数 i...どの基地? c9...9攻撃何回使った? c3...3攻撃何回使った? c1...1攻撃何回使った?
でもこれだと、状態数(20 * 100 * 100 * 100) * 更新数(7 * 20)で28億・・
無理や・・
事後
診断人さんという方の生放送見てて真似ただけなんですがね・・・
一応記録という事で・・
■考え方
攻撃回数を決め打ちする。
するとDPを以下のようにかける。
dp[i][c9][c3] := 1攻撃を最小で何回使う必要ある? i...どの基地? c9...9攻撃何回使った? c3...3攻撃何回使った?
基地の数をn、決め打ちした攻撃回数をcntとしたとき、9・3・1のどの攻撃もcnt以下しか使用することができない。よって、
c9 <= cnt かつ c3 <= cnt かつ dp[n][c9][c3] <= cnt
となるような状態があれば、cnt回の攻撃で全基地の破壊が可能となる。
■dpの更新方法
i番目の基地のヒットポイントをhpとして、これを壊すのに9攻撃をu9回、3攻撃をu3回使うとする。
1攻撃を何回使わなければならないかをu1とすると、
u1 = hp - (u9 * 9 + u3 * 3)となる。※ただし0以上
となる。
結局1攻撃の合計回数は
dp[i][c9][c3] + u1
更新先は
dp[i + 1][c9 + u9][c3 + u3]
となるので、こいつらで最小をとっていけばよい。
ここでポイントなのは、決め打ちした攻撃回数をcntとしたときに、
u1 + u3 + u9 <= cnt
を満たさなければならないということ。
1回の攻撃の中で、1つの基地に2回以上ダメージを与えられないのだ・・
■決め打ちの方法
攻撃回数の決め打ち方法だけど、想定解は2分探索なのかな?
それだと攻撃回数は高々93回なので、7回でいける。
計算量は状態数(20 * 100 * 100) * 更新数(7 * 20) * 決め打ち数(7)で2億弱
ただ2分探索を使わなくてもいけるようです。
まずダメージを全く無駄にしない、理想的な攻撃回数を出します。
基地のhpの総和 / (9 + 3 + 1)
当然これではいけない時もあるので、ここから決め打ち回数を1ずつインクリメントしていきます。
理想的な攻撃回数と実際の攻撃回数に最も差異が出るパターンは、基地が20個あって、hpが全て1の時かな?
そうだとしても、理想 = 2回 実際 = 7回なので大丈夫そう。
ソースコード
const int INF = 100; int n; vector <int> x; // dp[i][c9][c3] := 最小の1攻撃回数 // i番目までの基地を // c9回だけ9攻撃を使って // c3回だけ3攻撃を使ったとき int dp[22][122][122]; class Mutalisk { public: int minimalAttacks(vector <int> _x) { n = _x.size(); x = _x; // 基地の合計値をだす。 int sum = 0; for (int i = 0; i < n; i++) { sum += x[i]; } // 理想値から攻撃回数をインクリメントしていく for (int cnt = sum / (9 + 3 + 1); cnt <= 100; cnt++) { if (solve(cnt)) return cnt; } return INF; } // cnt回数で全基地破壊できるならture、そうでなければfalse bool solve(int cnt) { // dp初期化 for (int i = 0; i <= n; i++) { for (int c9 = 0; c9 <= 100; c9++) { for (int c3 = 0; c3 <= 100; c3++) { dp[i][c9][c3] = INF; } } } dp[0][0][0] = 0; // dp更新 for (int i = 0; i < n; i++) { for (int c9 = 0; c9 <= 100; c9++) { for (int c3 = 0; c3 <= 100; c3++) { for (int u9 = 0; u9 <= 7; u9++) { for (int u3 = 0; u3 <= 20; u3++) { // 1攻撃の必要回数 int u1 = max(x[i] - (u9 * 9 + u3 * 3), 0); // cntより多く1つの基地に攻撃できない! if (cnt < u9 + u3 + u1) continue; if (dp[i][c9][c3] + u1 < dp[i + 1][c9 + u9][c3 + u3]) { dp[i + 1][c9 + u9][c3 + u3] = dp[i][c9][c3] + u1; } } } } } } // 答え算出 for (int c9 = 0; c9 <= cnt; c9++) { for (int c3 = 0; c3 <= cnt; c3++) { if (dp[n][c9][c3] <= cnt) return true; } } return false; } };