Description:
多角形領域が複数する。
この領域は、必ずどこかの国に属し、領域同士が接する事はあるが、重なりはない。
この地図に色を塗りたいのだが、次の条件を満たしたい。
1. 同じ国に属する領域は同じ色で塗る。
2. 異なる国同士の領域が接する場合、必ず異なる色で塗る。
複数の国に同じ色を使っても構わないので、使う色の数を最小化したい。
何色必要か?
国の数は10以下、領域の数は100以下、領域を構成する点の数は100以下。
Answer:
まず、全多角形間の線分について調べ、どの国とどの国が同じ色になってはいけないかを調べる。
その後は10!通り、色の組み合わせを試してしまえばよい。
Source: