TopCoder SRM 809 : Div1 Easy Div2 Hard LunchLine

レート相応の順位でレート増減1桁。
(URL未定)

問題

初期状態で、0～(N-1)番の番号を持つN人の人が順に並んでいる。
ここでM個のイベントが与えられる。
各イベントiでは、人の番号K[i]が指定され、その人が列の最後尾に移動する。

最終的にi番の人が列のF[i]番目に並んだとする。
i*F[i]の総和を求めよ。

解法

T[i] := i番の人が最後に列の末尾に並んだタイミング
とする。
初期状態でT[i]=iとしておき、j番目のイベントに対しT[K[j]]=N+jでタイミングを更新しよう。

最終的な列の状態は、T[i]が昇順に並ぶようなiの順で定まる。
T[i]を昇順にソートしてもよいし、イベントを逆順にたどっても良い。
合わせてO(NlogN+M)で解ける。

ll K[303030];
int O[303030];
class LunchLine {
	public:
	long long simulate(int N, int M, int A, int B, int C, int D, int E) {
		K[0]=A;
		K[1]=B;
		int i,j,x,y;
		for(i=2;i<M;i++) K[i]=(C*K[i-1]+D*K[i-2]+E)%N;
		FOR(i,N) O[i]=i;
		FOR(i,M) O[K[i]]=N+i;
		
		vector<pair<int,int>> V;
		FOR(i,N) V.push_back({O[i],i});
		ll ret=0;
		sort(ALL(V));
		FOR(i,N) ret+=1LL*i*V[i].second;
		return ret;
		
	}
}

まとめ

Div1 Easyにしても簡単な問題な気がする。225ptでいいんじゃ。
実際Div2 Hardだと900ptだしね。