aoj2176:For the Peace - らての精進日記

問題文

解法

ある時点において最も戦力が強い国をkとすると、国kの戦力を(可能なら)削ったほうがいいです。
厳密な証明とかはよくわからないのでアレですが、国k以外の国の戦力を何回か削る→国kの戦力を削る、
という一連の操作があったときに、国kの戦力を削る→国k以外の国の戦力を何回か削る、
という風に順序を変えることができることから、国kの戦力を真っ先に削りに行っても問題ないような気がします。

ここで問題となるのは、国kの戦力を削る際に、次になくすべきミサイルの強さをxとしたとき、x>Dだった場合です。
この場合、国kのミサイルを削ると条件を満たさなくなることがあります。

(例えば、N=3,D=4で、現在の各国の戦力が(6,5,2)だとして、次になくすべき国1のミサイルの強さが6だった場合です。
もしこのミサイルをなくしてしまうと、(0,5,2)となってアウトです。ここで、次になくすべき国2のミサイルの強さが3だったとすると、
(6,5,2)→(6,2,2)→(0,2,2)となって平和です)

上の例を見ればわかる通り、国kのミサイルが削れない原因は、国kの次に強い国の存在です。
国kのミサイルを削ると、国kは最弱の国になるので、国kの次に強い国が最強になります。
なので、国kの次に強い国が弱ければ弱いほど好都合です(この記事、全体的に日本語が終わっていて悲しい)

そこで、次のような方法をとります：
1.国kはそっとしておいて、国kの次に強い国の戦力を(可能ならば)削る。
2.まだ1が実行可能ならば、再び1を行う。そうでなければ3に行く。
3.国kの戦力を削れるなら、削って終了。そうでない場合は、不可能。

これでACしたので、たぶん正しいです。

コード

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,D;
vint A[100];

void solve(){
    rep(i,N)A[i].clear();
    rep(i,N){
        int m;
        scanf("%lld",&m);
        A[i].resize(m);
        rep(j,m)scanf("%lld",&A[i][j]);
    }

    priority_queue<pint>que;
    rep(i,N)que.push(pint(accumulate(all(A[i]),0ll),i));

    while(que.size()){
        int c,idx;
        tie(c,idx)=que.top();
        que.pop();
        if(c==0){
            puts("Yes");
            return;
        }
        if(A[idx].back()<=D){
            c-=A[idx].back();
            A[idx].pop_back();
            que.push(pint(c,idx));
            continue;
        }
        while(que.top().fi>D+c-A[idx].back()){
            int cc,jdx;
            tie(cc,jdx)=que.top();
            que.pop();
            cc-=A[jdx].back();
            A[jdx].pop_back();
            if(c-cc>D){
                puts("No");
                return;
            }
            que.push(pint(cc,jdx));
        }
        c-=A[idx].back();
        A[idx].pop_back();
        que.push(pint(c,idx));
    }
}

signed main(){
    while(scanf("%lld%lld",&N,&D),N||D)solve();
    return 0;
}