Codeforces Round #611 (Div. 3) - E. New Year Parties
概要
nが与えられる。[1, n]の区間に、n人の人が立っている。彼らの座標は、重複しうる。
それぞれの人は、その場にとどまるor座標を-1するor座標を+1することができる。x=1にいる人はx=0に、x=nにいる人は、x=n+1に行くこともできる。これらの行動のいずれかを1回だけ取れる。
すべての人が行動を終えた時、人がいる座標の数の最大値、最小値を答えよ。
制約：1 <= n <= 2*10^5
ACするまで
1. 最小値は、簡単な証明で貪欲にやればいいとわかる。
2. 最大値を考える。できるだけ左に寄せてみる->WA
3. コンテスト時間TLE
4. 人が連続的に並んでる区間を考えてみる。その区間[l, r]に入ってる余分な人間の数次第で[l, r]から最大サイズ2つ広がる。
5. 広がる条件をよく考えてみると、貪欲的にやれる。
6. AC
考察
最小値に関しては、直感的ではあるが、「左から見て座標iに人がいたら、i, i + 1, i + 2にいる人は全部i + 1に集合させる」ことで最小値が求まる。
証明として、左から見て、座標iに人がいたら、その人をi+1に移動させる方が、その場にとどまるより人のいる座標を減らせる可能があるとわかる。(iにi+1の人が来るのも可能だが、i+2に人がいると不適な上、いないとしても最終的にこの方法と同じように人のいる座標を1つ減らしてる結果になる)この時、i+2にいる人もi+1に移動させるのが最善である。座標iにいる人を一番人のいる座標の数を減らすように動かすとき、i+1に集合させるのが最適であるとわかる。
最大値に関しては、手で実践してみると、
連続して人がいる座標の区間ごとに考えて、(区間における人の数)-(区間の長さを)＝Xとすると、
- X==0 -> この区間の人が区間内の座標に連続して人がいるという条件を満たして、区間を伸ばすことができない。
- X==1 -> この区間の人が区間内の座標に連続して人がいるという条件を満たして、区間を[l, r]とすると、[l - 1, r] or [l, r + 1]に伸ばすことが可能である。
- X>= 2 -> この区間の人が区間内の座標に連続して人がいるという条件を満たして、区間を[l, r]とすると、[l - 1, r + 1]に伸ばすことが可能である。
X==1の時、[l - 1, r]にするのか[l, r + 1]にするのかに関しては、左から見る際にx=l-1を区間に入れられるのは今の連続区間を見てる時にしかできないが、x=r+1は次の連続区間でもできるかもしれないので、[l - 1, r]を優先する。
一言
連続区間がキーなのを見つけるのに時間がかかりすぎた。
