Codeforces #187 Div2 C "Sereja and Contest"
問題
http://codeforces.com/contest/315/problem/C
訳
この前のセレジャの"Codesecrof"のプログラミングコンテストは、長時間サーバーがクラッシュしたので何人かの参加者をunratedにすることを決定した。
コンテストの参加人数をnとする。そして、最初の参加者のレーティングをa_1、2番目の参加者のレーティングをa2, ... n番目の参加者のレーティングをa_nとしよう。それから"Codesecrof"では以下のような式を計算してレーティングが変更する。
TODO
ラウンドが完了した後、Codesecrof運営者は参加者の成績(結果テーブル)を公開する。彼はd_i < kである参加者は、当該ラウンドにおいて、uprateにすることに決めていた。しかし、結果テーブルは動的であることが判明したときは、運営者は驚いた事だろう。言い換えれば、ある参加者が除外(unrate)になると、結果テーブルからも彼の情報が除外され、新しい結果テーブルを元にして、再度レーティング変更の計算が行われる。そしてもちろん、レーティング変更のためのアプリケーションは最新のテーブルを参照する。
- 略 -
何番目の参加者が除外されるのか出力せよ
制約
1 <= n <= 2 * 10^5
-10^9 <= k <= 0
考えた事
問題を推理して、正確に実装できるかと言う問題。
計算量を多く見積もらせようとしてるのか、問題文が・・・
訳すの諦めた
事後
intでオーバーフロー
もーなんなんだよ!!
ソースコード
int n, k; // 参加者数, k int e; // 除外者数 long long sum; // 残っている人のポイント int main() { e = 0; sum = 0; cin >> n >> k; for( int i = 1; i <= n; i++ ){ long long rate; cin >> rate; if( i == 1 ) continue; long long dif = rate * ( n - i ) * ( i - 1 - e ); long long d = sum - dif; if( d < k ){ e++; // 除外! printf( "%d ", i ); }else{ sum += (i - e - 1) * rate; } } }