解法
まずは全探索を考えたくなる。
マス(1, 1)から(N, N)までの経路を全探索しようとすると、 通りになってしまい、
のときには実行制限時間に間に合わない。
この問題では「半分全列挙」を行うことで高速化することができる。
上図のように、一番左上のマスから対角線のマスまでの経路、一番右下のマスから対角線のマスまでの経路を考えると、それぞれの経路は 通りになる。
これならば実行制限時間内で対角線上のマスに入る直前のXORの列挙が可能である。
後は、上で列挙したXORと対角線上のマスに書かれた値を用いてこの問題を解くことができる。
std::map(平衡二分探索木)などを用いて実装できる。 提出コード
