AOJ 2597 Color the Map Extreme

解説PDFが閲覧できなくなっていたのと、ネットに自分の解法が落ちてなさそうだったので書きました。

とりあえずグラフを作る。4色定理があるので答えは4以下。

答えが1かどうか→グラフに辺があるかどうか

答えが2かどうか→グラフが二部グラフかどうか

なので、答えが3かどうかを調べる。

まず、色1,2,3があったときに、色3となる頂点が全て決まっている場合、これは残りの頂点を2色で塗る問題に帰着される。

そこで問題となるのが色3となる頂点の決め方に2^N通りあること。少し考えると、色3となる頂点の集合は極大独立集合であると仮定してよい。

ところでグラフの極大独立集合は O(1.618^N) で列挙できる。

具体的には、頂点を1から順に見ていったときに、次数0の頂点は独立集合に加えるしかないし、次数1以上の頂点はそれを独立集合に加えると頂点N-2以下のグラフとなるので、計算量がフィボナッチ数で抑えられる。

したがってO(N^2*1.618^N)でこの問題は解くことができる。

このままだと少し遅いので、お好みの枝刈りをどうぞ

(私の場合は、答えが3かどうかの判定の直前に次数2以下の頂点を順次削除しました。)

heno239’s blog