ABC140 D - Face Produces Unhappiness
めっちゃ詰まった
本当に緑diffか？と思いながら解いてたけど、確かに緑diffレベルかもしれない
https://atcoder.jp/contests/abc140/tasks/abc140_d
問題概要
人の人が並んでおり、それぞれの人は左か右を向いている。どの人も目の前の人が自分と同じ向きを向いていたら幸福である。以下の操作を
回まで行えるとき、幸福である人は最大で何人にできるか。
解説
最大値を求めたいので、典型である二分探索や DP に想いを馳せるが、どれもうまく使えない。
操作について考察してみる。操作した区間から遠く離れた場所では当然幸福である人は変わらない。また、操作した区間の中でも、端点を除いて幸福である人は変わらない。よって、操作をすることで幸福であるかどうかが変わる人は、区間の端点付近の人たち。少し考えると、 回の操作では高々
人しか幸福である人は増えない。
また、LLLRRRRRLLLL や RRRLLLLLRRR のように、挟まれた区間（？）を選ぶと、幸福である人を 人増やせる。
人のうち幸福である人は最大でも
人である。
よって、最初に幸福であった人の数を をとして、
が答えである。
反省
度回転を考えるとか不可能じゃん！！！になってしまい、本質部分まで辿り着けなかったので反省。
上界がこれで、その上界は必ず達成できるので、解けました、みたいな流れ本当によくみる。疑えるようにしたい。
実際に解いたときはもう少し遠回りの解法を通ってしまった。この考え方の方が実装も簡単なので身につけたい。
