本番中に詰め切れて良かったね。
https://atcoder.jp/contests/arc174/tasks/arc174_f
問題
初期状態でC個の石があるとする。
これを用いて2人で二人対戦ゲームを行う。
2人交互にターンがやってきて、iターン目ではL[i]個以上R[i]個以下の石を取り除くことができる。
所定の数取り除けない側は負けとなる。
クエリとして初期状態Cの値が与えられる。
それぞれ両者最適手を取るときどちらが勝者になるか求めよ。
解法
現ターンで何個石が残っていたら、先手・後手どちらが勝つか、というのを後退解析を処理する。
ある程度以上石があると引き分けになり、それ以外の場合、先手が勝つ区間と後手が勝つ区間が交互に来る。
後退解析を行うと、それぞれの区間が伸び縮みする。
その際、自分が勝つ2つの区間が伸びた結果、間にある相手が勝つ区間を覆ってしまう(=自分がかつ2つの区間が連結する)ことがある。
区間加算・区間最小値を取れるSegTreeを用いて、このような区間の連結をシミュレートしていこう。
int N; ll L[303030],R[303030]; int Q; ll C[303030]; template<class V,int NV> class SegTree_3 { public: vector<V> val; vector<pair<V,int>> ma; SegTree_3(){ int i; val.resize(NV*2); ma.resize(NV*2); FOR(i,NV) val[i+NV]=0, ma[i+NV]={0,i}; for(i=NV-1;i>=1;i--) ma[i]=min(ma[2*i],ma[2*i+1]); }; pair<V,int> getval(int x,int y,int l=0,int r=NV,int k=1) { if(r<=x || y<=l) return {1LL<<60,0}; if(x<=l && r<=y) return ma[k]; auto a=min(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1)); a.first+=val[k]; return a; } void update(int x,int y, V v,int l=0,int r=NV,int k=1) { if(l>=r) return; if(x<=l && r<=y) { val[k]+=v; ma[k].first+=v; } else if(l < y && x < r) { update(x,y,v,l,(l+r)/2,k*2); update(x,y,v,(l+r)/2,r,k*2+1); ma[k]=min(ma[k*2],ma[k*2+1]); ma[k].first+=val[k]; } } }; SegTree_3<ll,1<<20> st[2]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>L[i]>>R[i]; set<int> alive[2]; for(i=N;i<=3*N;i++) { x=i/2; y=i%2; st[y].update(x,x+1,1LL<<60); } for(i=N-1;i>=0;i--) { x=i/2; y=i%2; st[y].update(x,x+1,L[i]); int nx=x; if(y==1) nx++; st[y^1].update(nx,N+1,R[i]-L[i]); alive[y].insert(i); st[y].update(x+1,N+1,-(R[i]-L[i])); while(1) { auto p=st[y].getval(x+1,N+1); if(p.first>0) break; ll dif=p.first; j=p.second*2+y; alive[y].erase(j); st[y].update(p.second,p.second+1,1LL<<60); auto it=alive[y^1].lower_bound(j); if(it!=alive[y^1].end()&&it!=alive[y^1].begin()) { int a=*it; int b=*prev(it); alive[y^1].erase(b); ll v=st[y^1].getval(b/2,b/2+1).first; st[y^1].update(a/2,a/2+1,v+dif); st[y^1].update(b/2,b/2+1,1LL<<60); } } } ll sum=-1; vector<ll> V; FOR(i,N) { if(alive[i%2].count(i)) { sum+=st[i%2].getval(i/2,i/2+1).first; V.push_back(sum); } } cin>>Q; while(Q--) { ll C; cin>>C; x=lower_bound(ALL(V),C)-V.begin(); if(x==V.size()) { cout<<"Draw"<<endl; } else if(x%2==0) { cout<<"Bob"<<endl; } else { cout<<"Alice"<<endl; } } }
まとめ
Eまであまりペース良くなかったので助かった。