Codeforces #573 Div1 A. Tokitsukaze and Discard Items

Hackで稼いでだいぶレートが上がった回。
http://codeforces.com/contest/1190/problem/A

問題

1～Nの整数が順に並んでいる。
これらは先頭からK個ごとに区切られ、各区切りはページとして扱われる。
このうち、消すべき数字M個が指定される。
消すときは以下の手順で消される。

• 消すべき数字のうち、まだ消されていない最小の数字を選択する。
• その数字と、同じ位置ページ内にある数字をまとめて消す。
• 空いた場所は詰める。ページの区切りも再調整される。

消すべき数字がすべて消えるまで、何手かかるか答えよ。

解法

消える順は常に小さい順である。
よって、これまで何個数字が消えたかを覚えておけば、次に消えるべき数字がわかるし、その数字のいるページも簡単に計算できるので、合わせて何個数字が消えるかもわかる。
あとは単純にシミュレーションを繰り返すだけ。
O(M)で解ける。

ll N,M,K;
ll P[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,M) {
		cin>>P[i];
		P[i]--;
	}
	int num=0;
	ll dis=0;
	int cur=0;
	while(cur<M) {
		ll page=(P[cur]-dis)/K;
		while(cur<M && (P[cur]-dis)/K==page) cur++;
		num++;
		dis=cur;
	}
	
	cout<<num<<endl;
	
}

まとめ

Codeforces書かなさすぎて3か月半もビハインドしてしまっている…。