ABC203 E - White Pawn (500)
チェスのポーンと同じような動きをする
黒のポーン経由でしか左右には動けないので$ Nの左右$ M列にしか移動できない
移動可能かもしれない範囲について以下を行う
その列にポーンがなければ移動不可能
$ N列目だけは移動可能
あればそのポーンの位置に移動して上へ探索していく
既に訪れたポーンならその結果を返す
左右の列で以下を確認する
ポーンがそれより上になくて$ N列目なら到達可能
今見ているポーンに$ N列目から移動可能なため
ポーンがありそのポーンが到達可能なら到達可能
上で到達可能にならなければ到達不可能
$ \mathcal{O}(M \log M)に見える
実際には2206ms, 2005ms, 1971msなどを取るので何回か提出すると通った