Codeforces #939 : Div2 E2. Nene vs. Monsters (Hard Version)

これはわからなかった…。
https://codeforces.com/contest/1956/problem/E2

問題

N体のモンスターが円周上に並んでおり、それぞれの体力V[i]が与えられる。
各モンスター1番のモンスターから初めて以下を順次行う。

• i番のモンスターは、(i+1)番のモンスターの体力から、自身の体力分減算する。ただし減算結果が負となる場合は0にとどまる。

この処理を無限回行った場合、正の体力を残すモンスターを列挙せよ。

解法

O(max(V)^(1/3))だけ愚直に行うと、体力が正のモンスターの並びは3体以下となる。
よってあとは正の体力のモンスターの並びが3体以下の場合だけ考えればよい。
2体の場合は体力を奪われる側がいずれ体力0になるし、3体の場合は2体目と3体目どちらが先に0になるかを求めればよい。

int T;
int N,A[202020];
vector<int> ret;

void hoge(vector<pair<int,int>>& V) {
	if(V.empty()) return;
	ret.push_back(V[0].second);
	
	assert(V.size()<=3);
	
	if(V.size()==3) {
		ll turn=V[1].first/V[0].first;
		ll dam=V[1].first*turn - 1LL*V[0].first*turn*(turn+1)/2;
		if(dam<V[2].first) ret.push_back(V[2].second);
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>A[i];
		FOR(j,2001) {
			A[N]=A[0];
			FOR(i,N) if(A[i]) A[i+1]-=min(A[i+1],A[i]);
			A[0]=A[N];
		}

		int cur=0;
		while(1) {
			if(A[cur]==0) break;
			A[(cur+1)%N]-=min(A[cur],A[(cur+1)%N]);
			cur=(cur+1)%N;
		}
		ret.clear();
		vector<pair<int,int>> V;
		for(i=1;i<=N;i++) {
			if(A[(cur+i)%N]==0) {
				hoge(V);
				V.clear();
			}
			else {
				V.push_back({A[(cur+i)%N],(cur+i)%N});
			}
		}
		sort(ALL(ret));
		cout<<ret.size()<<endl;
		FORR(a,ret) cout<<a+1<<" ";
		cout<<endl;
	}
}

まとめ

計算量をちゃんと見積もっていけば解けるのか…。