ABC161 - E - Yutori - Senの競技プログラミング備忘録

概要

Senくんのスケジュールが記された、長さNの文字列によってあらわされるスケジュール表が与えられる。i文字目が'o'なら働ける日、'x'なら働けない日である。
"ooxox"ならば、1, 2, 4日目にだけ働ける。
Senくんは怠惰なので、1日働いたら次に働けるのはC日後になってしまう。
与えられたスケジュール表のうち、K日は最低でも働けることが分かっている。このうちのK日の働き方で、どんな働く日にちの選び方でも必ず選んでしまう日を列挙せよ。

制約：　1 <= N <= 2 * 10^5, KとCは最低K日働けるように与えられる。

ACするまで

1. 日程は基本的に前詰めすれば、後ろに適宜ずらせるときがある。
2. 適宜ずらせる日程は確定しない。じゃあ適宜ずらせない日程とは？
3. 適宜ずらせない日にちは、「後ろから詰めても、同じ日数目で働く日」
4. これを実装してAC!　C == 0の場合に、実装によっては注意

考察

少し考えると、日程はできるだけ前詰めして、いわゆる日数の下限を求めて、この下限からそれぞれ適宜ずらせるかどうか？を考えればいいとわかる。

では、ずらせる日とずらせない日の違いとは何だろうか？

いわゆる、ずらせない日というのは、

許容日程の下限と上限が一致する日。

である。

数学の証明でもよく使われる論法として、pとqが完全に等しいのを示すのに、p>=qとp<=qの両方を示して、p==qしかないという手法がある。これを知ってるとわかりやすいかも。僕はコンテスト終了後に考えてわかりました。

では、日程の下限と上限はどう求めればよいのだろうか？
下限に関しては、日程を前詰めで考えて、
Llimit[i] := i回目の労働日はLlimit[i]から始められる。
上限に関しては、同じように、後ろ詰めで考えて、
Rlimit[i] := i回目の労働日はRlimit[i]までに終えないといけない。

これでLlimit[i] == Rlimit[i]となる日は、上限と下限が同じなので、その日でなければいけないということになる。

ちなみに、不可能判定もこれで簡単に行えて、Llimit[i] > Rlimit[i]ならばi日目の労働は無理ということにもなる。

以下自分向け

実装だが、次のようにbef(前の働いた日の日数)を持たせてやると楽。だけどbefの初期値にCの数倍とかにすると、

5 4 0
ooooo

C==0の場合(上記の例など)で落ちるので、Cの数倍ではなく、

int bef = -2 * C - 1;

とかにしよう。

int bef = - 2 * C - 1;
int cnt = 0;
for (int i = 0; i < N && cnt < K; i++) {
	if (s[i] == 'o') {
		if (i - bef > C) {
			Llimit[cnt] = i + 1;
			cnt++, bef = i;
		}
	}
}

ACソースコード：
Submission #11578229 - AtCoder Beginner Contest 161

Rlimit[]の実装の添え字が解説と順序真逆である。

一言

千里之堤溃于蚁穴。