ABC140-D "Face Produces Unhappiness"

普段見ないかんじの問題でだいぶ苦戦しました．

提出コード

考察

まず一番大事なのは， $(l, r)$ を指定して操作を行ったとき，両端を除く $(r-l-1)$ 人の内部では幸福な人の数は変わらないという点です．

両端を除けば自分の目の前にいた人と自分の向きが同じか違うかというのは操作後でも保たれるためです．

つまり，1回の操作では高々2人までしか幸福な人は増えません．

そこで，次のように連続する'L'または'R'の区切りを考えます．

LLRLRLLRRRRL $\to$ LL / R / L / R / LL / RRRR / L

このように区切り，この塊ごとに操作を施すと見なします．

すると，両端を除く塊に対して操作を施したときは幸福な人は確定で2人増えることになります．

一見'LL'や'RRRR'に操作を施すのが最適に見えますが，どこに操作をを施しても幸福な人は確定で2人増えるので実は操作を施す場所に最適な順序はありません．

まずは連続する'LL'や'RR'を数えておきます(numとする)．これは冒頭でも話したように，操作をしたところで不変の値です．

次に，境目の数を数えます．(上の例の/で区切った数でopeとする)

このnumと $K$ の小さい数だけ操作をすることができて，その都度幸福な人は2人増えていきます．

よって答えは ${\rm num}+2\times {\rm min(ope}, K)$ です．

ただし，これが $N-1$ を超えてはいけないので上の数値と $N-1$ でminを取ります．

この最後の詰めはあんまりよくわかってない()

将来的に理解したいですね...

この解法を昔チラッと聞いたので解けたけどノーヒントだったらどうなっていたことやら...

改めてratingが上の人たちの化け物っぷりを感じますね．