ICPC模擬地区予選2009 B - For the Peace

問題文原文

問題概要

ミサイル保有国がn国ある．それぞれの国はm個のミサイルを保有している．各ミサイルはcapability cをもつ．

各国のミサイルのcapabilityの和の差をd以下に保ったまま，全てのミサイルを廃棄できるかを答えよ．

ただし，各国はミサイルを古いものから順に廃棄しなければならない．

解法概要

除去後のcapabilityの和が最大の国と最小の国の差がd以下になるようなミサイルを貪欲に削除していけばよい．削除できるミサイルがない場合はNo，全てのミサイルを削除できたらYes．

削除できるミサイルの候補が複数あったら，どのミサイルを削除してもよい．なぜなら，capabilityの和の最大は削除が進むにつれて減りこそすれ増えることはないので，一度削除可能になったミサイルが削除不可能になることはないためである．

ソースコード

#include<cstdio>
#include<vector>
#include<utility>
#include<climits>
#include<algorithm>
 
using namespace std;
 
typedef long long ll;
typedef pair<pair<long, long>, pair<int, int> > P;
 
int main(){
    int n,d;
    while(scanf("%d%d", &n, &d) && n){
        vector<ll> missile[n];
        int m;
        ll min_ = LLONG_MAX, max_ = 1LL;
        bool ans = true;
        for(int i=0;i<n;i++){
            scanf("%d", &m);
            ll c[m], total = 0;
            for(int j=0;j<m;j++){
                scanf("%lld", &c[j]);
                total += c[j];
            }
            missile[i].resize(m+1);
            missile[i][0] = total;
            for(int j=0;j<m;j++) missile[i][j+1] = missile[i][j] - c[m-1-j];
        }
 
        vector<ll> indexes(n, 0);
        while(max_){
            ll mindiff = INT_MAX, diff_i, mindiff_min;
            for(int i=0;i<n;i++){
                if(missile[i][indexes[i]] == 0) continue;
                min_ = INT_MAX;
                max_ = 0LL;
                for(int j=0;j<n;j++){
                    int jj = indexes[j] + ((j==i && missile[j][indexes[j]])?1:0);
                    min_ = min(min_, missile[j][jj]);
                    max_ = max(max_, missile[j][jj]);
                }
                if(max_ - min_ >= 0 && mindiff > max_ - min_){
                    mindiff = max_ - min_;
                    diff_i = i;
                    mindiff_min = min_;
                }
            }
 
            indexes[diff_i]++;
            min_ = mindiff_min;
            max_ = mindiff_min + mindiff;
            if(max_ - min_ > d){
                ans = false;
                break;
            }
        }
 
        printf("%s\n", ans?"Yes":"No");
    }
}

感想

国ごとのミサイルのcapabilityは古いものから順に並んでいるという誤読をしていてつらかった．逆だった．Input / Output もちゃんと全部読もう．

For the Peaceが解けなくてPeace of mindが乱されている
— Noimin (@noisy_noimin) June 25, 2018

あと，ブログの更新しなかったら実力の伸びが明らかに鈍った感じがする……雑だろうがなんだろうが更新頻度上げよう……．