- 考えたこと
- 床は1次元配列に展開して長さN+1の範囲を塗ると解釈できる
- 地図読み込み時に番兵をつけるの番兵がないパターン
- 最小の回数って、端から順に塗るので良いのかな、良さそうだけど証明したい
- まだ塗られてない最小のマスを始点とする区間で塗った場合、もっと左から塗った場合と比べて残りマスがイコールもしくは少ない
- もっと右から塗った場合、塗り残しができるのでそれを塗るためにそれよりも左から改めて塗らないといけない
- OK
- 整理すると
- 手数最小の塗り方をする時に、最も左から塗る手が一つ存在する。これが最も左のまだ塗られてないマスを始点とするものであるような最小手数塗りが存在することを示す。
- 始点がより左である時、その塗りを行った後の「塗られてないマス」は非減少なので、より手数の少ない塗り方である可能性はない
- 始点がより右である時、注目しているマスが塗り残されるので、別途それを覆う塗りをする必要がある。これは「もっと左から塗る手」であることと矛盾する
- よって最も左の塗られてないマスを始点とする塗り方で最初手数になることが示された
- 床は1次元配列に展開して長さN+1の範囲を塗ると解釈できる
- 公式解説
- OK
