SRM 658 div1 med: Mutalisk - mayoko’s diary

考えていた方針は途中までは間違ってなかったらしい。

問題

解法

基本的な方針は二分探索。x回でSCVsを全滅させることができるかどうかを判定し,全滅できる数のうち最小のものを求めれば良い。

難しいのはその判定法。まず条件を書き連ねると,

・i個目のSCVはx回より多い回数攻撃してはならない
・9,3,1のダメージを与える回数はそれぞれx回より多くなってはならない
・それぞれのSCVに対して,そのヒットポイント以上のダメージを与えなければならない

これが条件になる。これをどう判定するかというと,dpを使う。

dp[cur][n9][n3] := (9ダメージ与える攻撃をn9回残していて3ダメージ与える攻撃をn3回残していて,cur未満のSCVを全滅させた時,1ダメージ与える攻撃の残り回数の最大値)
として,上の条件を満たすように状態を遷移させていく。

以下ソースコード

vector<int> hp;
int dp[22][140][140];
int n;

bool ok(int limit) {
    memset(dp, -1, sizeof(dp));
    dp[0][limit][limit] = limit;
    for (int i = 0; i < n; i++) {
        for (int n9 = 0; n9 <= limit; n9++) {
            for (int n3 = 0; n3 <= limit; n3++) {
                if (dp[i][n9][n3] == -1) continue;
                int n1 = dp[i][n9][n3];
                for (int nn9 = 0; nn9 <= n9; nn9++) {
                    if ((nn9-1)*9 >= hp[i]) break;
                    for (int nn3 = 0; nn3 <= n3; nn3++) {
                        if (nn3 > 0 && nn9*9+(nn3-1)*3 >= hp[i]) break;

                        int nn1 = max(0, hp[i] - (nn9*9+nn3*3));
                        if (nn1+nn3+nn9 > limit) continue;
                        if (nn1 > n1) continue;

                        dp[i+1][n9-nn9][n3-nn3] = max(dp[i+1][n9-nn9][n3-nn3], n1-nn1);
                        if (i+1 == n) return true;
                    }
                }
            }
        }
    }
    return false;
}

class Mutalisk {
public:
    int minimalAttacks(vector <int> X) {
        hp = X;
        n = hp.size();
        int low = 0, high = 140;
        while (high - low > 1) {
            int med = (high+low) / 2;
            if (!ok(med)) low = med;
            else high = med;
        }
        return high;
    }
};

すごく良い問題だと思います。