WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
    }
};