ARC079 F Namori Grundy
問題ページ
F - Namori Grundy
解法
0以上a[i]未満の整数xが頂点iから辺が伸びている頂点jの値a[j]として全て使われているようなa[i]の決め方をする。
すなわち、a[i]から辺が伸びている頂点jの値として使われていない最も小さい値がa[i]の値となる。
サイクル以外の頂点の値a[i]は葉から順番に見ていくことで簡単に決められる。
サイクル上の適当な頂点を一点取ったとき、その頂点が取りうる値は、
- その頂点に辺が入る頂点の値として使われていない最も小さい値
- その頂点に辺が入る頂点の値として使われていない二番目に小さい値(サイクル上で頂点iに入る辺を持つ頂点jが最も小さい値を取る場合)
の2つしかありえない。
サイクル上の1頂点の値が決まればサイクル上の残りの頂点の値も順に決まっていく。この2パターンで成立するものがあれば"POSSIBLE"、なければ"IMPOSSIBLE"となる。
学んだこと
なもりグラフでサイクル外の頂点だけを探索する方法
grundy数の定義
