https://atcoder.jp/contests/agc029/tasks/agc029_d
高橋くんと青木くんが$H$行$W$列のマス目を使ってゲームをする。いくつかのマスには障害物があり、高橋くんは下に、青木くんは右にだけ1マスずつ進むことができる。パスも可能だが、2人が連続でパスをするとゲームが終了する。高橋くんはできるだけ多くの行動(パスを含む)で、青木くんはできるだけ少ない行動でゲームを終了させたい。高橋くんが行う行動の回数を求めよ。
青木くんはできるだけ少ない行動でゲームを終了させることが目的なので、高橋くんがパスした瞬間にパスをすれば即座にゲームを終了させることができる。よって、高橋くんはパスをするという選択肢がなく、常に下に移動し続けなくてはならないことになる。
青木くんは右に動くかパスをするかを選べるので、到達可能な一番右の列だけを保持しておけばそれより左の列には必ず到達できる。1ターン毎に到達可能な列は1つずつ右にずれるが、障害物にぶつかってしまう場合はその限りではない。すでに到達可能になっている列に障害物がある場合は、そこにコマをぶつけることで高橋くんは次のターンパスをするしかなくなりゲームが終了する。一度も障害物にぶつからない場合は盤面の高さを出力すればよい。
残り時間が少なくてもきちんと考察しましょう。