ABC 401-500/ABC413G - Big Banned Grid - 競技プログラミング用 知識集積所

---

問題

ABC413G

必要知識

B以下レベルの内容は省略

• 幅優先探索（未作成）または深さ優先探索（未作成）
• 双対性（未作成）

考え方

サイズがもう少し小さければ普通にC問題レベルの幅優先探索（未作成）問題。
しかし今回は、HWが10^10以上になるので、それができない。

そこで、双対性（未作成）を利用して、つまり

• 左上マスから障害物のないマスだけを縦横に移動して右下マスまで行けるか？
• 左辺か下辺から障害物のあるマスだけを縦横斜めに移動して上辺か右辺まで行けるか？

の答えが絶対に逆になることを利用する。

下側の問題は、通れるマスがkマスしかなく、毎回8方向全部見ても計算量的には余裕である。
問題は到達可能性を二重vector（未作成）で持てないこと。
仕方がないのでset（未作成）で障害物のある未到達マスを管理するように実装する。

解答例

解答例

注意点

別解