mayoko’s diary

プロコンとかいろいろ。

AOJ 2176 For The Peace


問題

For the Peace | Aizu Online Judge

n 個の国がある。各国はいくつかのミサイルを持っているが, これを以下の条件を満たすようにすべて捨てたい。目的を達成できるか判定せよ。

  • 各国は, 古い順にミサイルを捨てなければならない。
  • ある時点で, 軍事力の最大の国と最小の国で差が d より大きくなってはいけない。(ただし, 軍事力はミサイルの戦闘力の総和)

ミサイルは古い順に捨てなきゃいけないくせに入力は新しい順に書いてあることに注意です(これでキレてた)。

解法

実は 「valid なものがあったらそれを選択」という超単純なアルゴリズムで通ります。

はじめ, 「valid な動きの中で, 軍事力が最小になるようなものを選ぶ貪欲」というのを考えていたのですが, これは遷移の仕方として損をしない(最小のものが減少しても, 最大の軍事力の国が軍事力を下げやすくなるだけなのでうれしい)ので妥当です。

ただ, これをもう少し考えると, 適当にやっていればいずれ valid な動きが「最小なものを更新してからほかのをもっと下げる」というのしかなくなりそうなので, 順番はどうでも良さそうなことがわかります。

const int MAXN = 111;
int M[MAXN];
int sum[MAXN];
vi C[MAXN];
int now[MAXN];

string solve(int n, int d) {
    memset(sum, 0, sizeof(sum));
    memset(now, 0, sizeof(now));
    int need = 0;
    for (int i = 0; i < n; i++) {
        C[i].clear();
        cin >> M[i];
        need += M[i];
        C[i].resize(M[i]);
        for (int j = 0; j < M[i]; j++) {
            cin >> C[i][j];
            sum[i] += C[i][j];
        }
        reverse(C[i].begin(), C[i].end());
    }
    for (int t = 0; t < need; t++) {
        int index = -1;
        for (int i = 0; i < n; i++) {
            if (now[i] == M[i]) continue;
            sum[i] -= C[i][now[i]];
            if ((*max_element(sum, sum+n)) - d <= sum[i]) {
                mini = sum[i];
                index = i;
            }
            sum[i] += C[i][now[i]];
        }
        if (index == -1) return "No";
        sum[index] -= C[index][now[index]++];
    }
    return "Yes";
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, d;
    while (cin >> n >> d) {
        if (n==0 &&d==0) break;
        cout << solve(n, d) << endl;
    }
    return 0;
}