ARC079 F: Namori Grundy

arc079.contest.atcoder.jp

解き方

  • 1つ閉路があり、残りはその閉路にぶらさがっているようなグラフ
  • 閉路とそれ以外にまず分ける
  • 閉路以外の部分は、根を0、その上を…としていくと一意に定まる
  • 閉路については、適当に1頂点にxを割り当てて、うまくいくか計算する。xは、0以上、その頂点の次元数+1 以下なので、そのパターンだけ試す。

ハマったところ

  • コンテスト中はここまで考察できていなかった
  • 閉路を見つける部分は、スタックを使いまわすような形式じゃないと辛い(stackにパスをpushしていくと多分O(n^2)。関数スタックをシミュレートするような実装のほうがこの場合効率が良い)
  • std::findO(n)なのでループの中では厳禁。メモリに余裕のあるケースのほうが多いので一度unordered_setに変換するべき

github.com