Codeforces #187 Div1. A. Sereja and Contest

CF187、本番はAだけ解けてBはTLE、C以降は解けずだった。
http://codeforces.com/contest/314/problem/A

問題

N人の初期レートのテーブルはA[i]で与えられる。
以後、数値Kが与えられたとき、以下の手順でテーブルから人を抜いていく。

• テーブル中i番目のランクD[i]は、で計算できる
• ランク中K未満の人がいれば、その中で最もランクが高い人がテーブルから1人抜ける
• 人を抜いた後で上記処理を繰り返す

解法

i番目の人のランクは1～(i-1)番目の人のランクで決まり、かつ前の人が抜けるほどランクが下がる。
よって、「その中で最もランクが高い人」は無視して、ランクがK未満になるならどんどん抜いてしまってよい。
もっとランクの高い人がi+1以降にいても、いずれi番目の人は抜ける。

int N,K;
ll A[200001];
void solve() {
	int f,r,i,j,k,l, x,y;

	cin>>N>>K;
	FOR(i,N) A[i]=GETi();

	ll d=0,t=0;
	j=0;
	for(i=0;i<N;i++) {
		t = j*(ll)(N-(i+1))*A[i];
		if(d-t<K) {
			_P("%d\n",i+1);
		}
		else {
			d += j*A[i];
			j++;
		}
	}
	return;
}

まとめ

問題設定が無理やりなので、あまり面白くないな…。