二部グラフの最大マッチング問題なのでフローを作り、最大流量を調べる。青と赤のカードのペアで gcd > 1 が取れるものに辺が引ける。

隣接リストを用いて拡張ダイクストラをする。 やりかた知ってれば書き下すだけだった。状態として 「前の位置」「現在位置」「到着時の速度」「経過時間」 を持つとよい。priority_queue に push する条件として制限速度を与えてやることに注意。

未解決 初めに洞穴のマップを作る。エラトステネスの篩を掛けて、マップのidと対応を見ると素数洞穴がわかる。 洞穴のマップがバグりそうならdx, dyを使わずに渦を1方向ずつforループを回して作ってみれば良い。これでまずバグらない。後はDPなのだが、私は…

二部グラフの最大マッチング問題なのでフローを作り、最大流量を調べる。青と赤のカードのペアで gcd > 1 が取れるものに辺が引ける。