競技プログラミング用 知識集積所
ABC413G - Big Banned Grid
最終更新:
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
サイズがもう少し小さければ普通にC問題レベルの幅優先探索(未作成)問題。
しかし今回は、HWが10^10以上になるので、それができない。
しかし今回は、HWが10^10以上になるので、それができない。
そこで、双対性(未作成)を利用して、つまり
- 左上マスから障害物のないマスだけを縦横に移動して右下マスまで行けるか?
- 左辺か下辺から障害物のあるマスだけを縦横斜めに移動して上辺か右辺まで行けるか?
の答えが絶対に逆になることを利用する。
下側の問題は、通れるマスがkマスしかなく、毎回8方向全部見ても計算量的には余裕である。
問題は到達可能性を二重vector(未作成)で持てないこと。
仕方がないのでset(未作成)で障害物のある未到達マスを管理するように実装する。
問題は到達可能性を二重vector(未作成)で持てないこと。
仕方がないのでset(未作成)で障害物のある未到達マスを管理するように実装する。