ABC255 G. Constrained Nim
Difficulty:2734
問題
$ N個の山があって、各山には$ A_i個の石がある。Nimゲームを行う。先手は高橋君。
取り除く石の数は基本的にいくつでも良いが、現在$ X_i個ある山から$ Y_i個取り除く操作が禁止されている。
勝敗を判定せよ。
解法
複数個の山があるNimゲームは、Grundy数のxorで勝敗が判定できることが良く知られている。この問題でも各山についてGrundy数を求めることを考える。
Grundy数は「到達可能な状態すべてのGrundy数のmex」である。
まず、制約条件がなかった場合、当たり前だが石が$ i個ある山のGrundy数は$ iである。
制約条件を追加して、例えば石が1個の山のGrundy数が1ではなく0になった場合、それ以降のすべてのGrundy数から1が引かれる。
この辺をいい感じに処理するとGrundy数が求められる。「それ以降のすべてのGrundy数から1が引かれる」ような石の数たちをvectorに載せておき、石$ x個のときのGrundy数を求めたいときは、$ x未満の数の中で「それ以降のすべてのGrundy数から1が引かれる」ような数がいくつあるかを求めてxから引けばよい。
ただし、制約条件があるのに結局変わらないこともある。制約条件によってあるiについて到達不可能になるが、ほかの方法でiに到達可能であるパターンである。これは、基本的に各Grundy数は上の方法で求めたGrundy数以下が1つ以上それぞれあるが、制約条件によって2つ以上になっているものが存在するため、それをmapで保存しておけばよい。
実装
code:cpp
bool solve(){
LL(n,m);
vector<ll>a(n);cin >> a;
vector<pair<ll,ll>>v;
map<ll,vector<ll>>g;
rep(i,m){
LL(x,y);
}
vector<ll>s;
map<ll,ll>mp;
map<ll,ll>mp2;
if(mp.count(x))return mpx; else{
ll ret{x};
ret -= (lower_bound(ALL(s),x))-s.begin();
// deb(x,ret,"fx");
return ret;
}
};
ll tmp = l - s.size();
//基本的にはtmpになるはず
//なぜならtmp未満が1つ以上ずつ存在するから。
//2つ以上存在するものを管理しておく
map<ll,ll>mp3;
for(auto&&x:r){
}
deb(l,x,y,"!");
if(!mp2.count(x)){
chmin(tmp,x);
}
else{
chmin(tmp,x);
}
}
}
if(tmp not_eq l-s.size()){
s.push_back(l);
}
}
rep(i,10){
deb(f(i));
}
ll ans{};
for(auto i:a)ans^= f(i);
if(ans==0)O("Aoki");
else O("Takahashi");
return true;
}