Codeforces #1102 : Div2. G. Stripe, Token and Two Players

うーん、必要な知識は持ってたなぁ。
https://codeforces.com/contest/2234/problem/G

問題

1～(N+1)のセルからなる2人のターン制ゲームを考える。
各セルiには整数A[i]が書かれている。
初期状態で駒はセル1にあり、パワーは1である。
各自の手番で、共有の駒を交互に動かす。パワーの値も共有である。
その際、以下の手順を取る。

• パワーに、現在いるセルの整数値A[i]以下の非負整数選び加算する。
• その後、駒を、1～現行パワーの範囲で進める。

自分の手番で(N+1)マス目に到達したら勝利である。
最適手を取るとき、勝者はどちらか。

解法

f(n,p) := n番のセルでパワーpの状態で自分の手番が来た時、勝てるかどうか

遷移先のセルのバリエーションが多いため、f(n,p)はほぼ勝ちである。
よって勝てない状況を列挙していこう。

f(n,p)が負けとなるのは、そこから遷移できる範囲、すなわちf(n+1,p)-f(n+p,p)-f(n+1,A[n]+p)-f(n+A[n]+p,A[n]+p)が成す台形の区間に、必敗の状態が無いことである。
nの大きい順にf(n,p)を列挙していこう。
f(*,p)について、今確定している中でf(m,p)=falseとなる最小値mがわかっているとき、f(n,p)がfalseになるには少なくともn＜m-pでなければならない。
この情報を、pごとに持っておこう。連続する(A[n]+1)個のパワーの区間で、条件を満たすnがあれば、初めてそこでf(n,p)がfalseになる。

条件を満たすpの集合と、そのようなpの連続長をsetで管理していこう。

int T,N,A[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>A[i+1];
		}
		set<pair<int,int>> fail;
		set<pair<int,int>> add;
		set<pair<int,int>> range;
		set<pair<int,int>> len;
		for(i=1;i<=N;i++) {
			fail.insert({N+1,i});
			add.insert({N+1-i-1,i});
		}
		for(i=N;i>=1;i--) {
			while(add.size()&&add.rbegin()->first>=i) {
				x=add.rbegin()->second;
				add.erase(*add.rbegin());
				range.insert({x,x+1});
				len.insert({1,x});
				auto it=range.lower_bound({x,0});
				if(next(it)!=range.end()&&next(it)->first==x+1) {
					auto p=*it;
					auto q=*next(it);
					range.erase(p);
					range.erase(q);
					len.erase({1,p.first});
					len.erase({q.second-q.first,q.first});
					p.second=q.second;
					range.insert(p);
					len.insert({p.second-p.first,p.first});
				}
				it=range.lower_bound({x,0});
				if(it!=range.begin()&&prev(it)->second==it->first) {
					auto p=*prev(it);
					auto q=*it;
					range.erase(p);
					range.erase(q);
					len.erase({p.second-p.first,p.first});
					len.erase({q.second-q.first,q.first});
					p.second=q.second;
					range.insert(p);
					len.insert({p.second-p.first,p.first});
				}
			}
			while(len.size()&&len.rbegin()->first>=A[i]+1) {
				x=len.rbegin()->second;
				y=x+len.rbegin()->first;
				len.erase(*len.rbegin());
				range.erase({x,y});
				while(y-x>A[i]) {
					fail.insert({i,x});
					add.insert({i-x-1,x});
					x++;
				}
				if(x<y) {
					range.insert({x,y});
					len.insert({y-x,x});
				}
			}
		}
		
		cout<<(fail.count({1,1})+1)<<endl;
		
		
	}
}

まとめ

setで区間の集合を管理するのは何度もやってるけど、その際に長さも別途管理するの忘れてた…。