ARC040C

https://gyazo.com/766026735d7179c0d4a11f824e20f5e9

考えたこと

床は1次元配列に展開して長さN+1の範囲を塗ると解釈できる

最小の回数って、端から順に塗るので良いのかな、良さそうだけど証明したい

まだ塗られてない最小のマスを始点とする区間で塗った場合、もっと左から塗った場合と比べて残りマスがイコールもしくは少ない

もっと右から塗った場合、塗り残しができるのでそれを塗るためにそれよりも左から改めて塗らないといけない

OK

整理すると

手数最小の塗り方をする時に、最も左から塗る手が一つ存在する。これが最も左のまだ塗られてないマスを始点とするものであるような最小手数塗りが存在することを示す。

始点がより左である時、その塗りを行った後の「塗られてないマス」は非減少なので、より手数の少ない塗り方である可能性はない

始点がより右である時、注目しているマスが塗り残されるので、別途それを覆う塗りをする必要がある。これは「もっと左から塗る手」であることと矛盾する

よって最も左の塗られてないマスを始点とする塗り方で最初手数になることが示された

公式解説

OK