Codeforces #325 Div1 A. Gennady the Dentist

微妙な出来で反省。
http://codeforces.com/contest/585/problem/A

問題

歯医者の前で１列にN人の子供が並んでいる。
各子供は３つのパラメータがあり、それぞれV[i]:歯医者の診察でなく時の声、D[i]:列を抜け逃げるときの声、P[i]:耐久力である。

列の先頭から順に子供は診察を受け、その際V[i]の声で泣く。
すると列で並んでいる子供は先頭から順にV[i]、V[i]-1、V[i]-2…の分耐久力を失う。
その際耐久力が0になった子供jは、その瞬間列を抜け走り出す。
列を抜けた子供は泣きながら走るため、後ろの列の子供は皆D[j]の分耐久力を失う。

最終的に医者の診察を受ける子供を列挙せよ。

解法

特に難しいことはなく、問題文通り実装するだけ。
O(N^2)で間に合うので、愚直に処理すればよい。
列を抜ける処理のタイミングに気を付けよう。

int N;
ll V[5050],D[5050],P[5050];
int is[4040];
vector<int> R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>V[i]>>D[i]>>P[i],is[i]=1;
	
	FOR(i,N) if(is[i]) {
		R.push_back(i);
		for(j=i+1;j<N;j++) {
			if(is[j] && V[i]>0) P[j]-=V[i]--;
		}
		ll r=0;
		for(j=i+1;j<N;j++) {
			P[j]-=r;
			if(is[j]&&P[j]<0) {
				is[j]=0;
				r+=D[j];
			}
		}
	}
	
	_P("%d\n",R.size());
	FORR(r,R) _P("%d ",r+1);
	_P("\n");
	
}

まとめ

子供を並べ替えて、診察を受ける人数を最大化せよ、とかだと簡単に解けるのかなぁ…？