ABC203 E White Pawn
$ (i + 1, j - 1)と$ (i + 1, j + 1)の移動(斜め移動)にのみ注目して考える.
まず, 黒のボーンを$ X_iの昇順にソートしておく. その際, $ (0, N)に黒のボーンが置かれていない場合, 番兵として置いておく. その後, 黒のボーンを行の順に見ていく. ある黒のボーンについて, 左上のマスに白のボーンが置かれている可能性がある, すなわちその列の最新の黒のボーンについて, 到達している可能性がある(これはmapを用いて実装できる)場合, 今見ている黒のボーンについても白のボーンが置かれている可能性がある. 右上のマスについても同様にして確かめられる.
そして到達できる場合, 今の行を$ i, そして今の列$ jについて黒のボーンの存在する行の最大値を$ kとして, $ i = kなら$ jをsetに追加する.
このようにした後, setのサイズが答えとなる. 計算量は$ O(M (\log M)^2)となり, ギリギリではあるが間に合う(工夫することで$ O(M \log M)に落とすこともできる).