7K blog

猫でも分かる何か

順列全探索

ABC371C Make Isomorphic (300点)

https://atcoder.jp/contests/abc371/tasks/abc371_c

  • 計算量はビット全探索  O(2^n) より順列全探索  O(N!) のほうが少なくて済む
  • 辺の全探索の選択肢は(辺は頂点の端点でも表現できるので)辺か頂点か2種類
  • 愚直にやると辺を変更するかしないか  O(2^M)
  • 頂点の全探索なら辺より頂点のほうが少ない且つ要素数が不変  O(N!)
  • 辺の判定は対合写像ライブラリを使えば  O(M)
  • 2次元配列Aの添字は昇順なのでsort()する
  • 全体計算量は頂点全探索と辺の判定で  O(N!M)

https://atcoder.jp/contests/abc371/submissions/69288379