ABC133 E - Virus Tree 2
解法
探索か何かをしつつ、今いる頂点について色を決ようとすると、その頂点から距離2以内で、すでに色が決まっている頂点がいくつあるかを調べる必要があり、とても大変です。
そこで、今いる頂点から行くことができる頂点について、色を決めることについて考えてみます。
上のような木について考えてみます。白い頂点が既に通過済みの色を塗られている頂点で、青い頂点が今いる頂点です(ここも色はすでに決まっています)。そして、クリーム色の頂点が、今から色を決める頂点になります。
3つのクリーム色の頂点に、順番に色を塗っていくことを考えると、
1番目の頂点には、2番目は
、3番目は
通りの塗り方が考えられます。
1番目の頂点は、白と青の頂点の分だけ色の選択肢がなくなり、2番目以降の頂点は、今塗ったクリーム色の頂点の色だけさらに選択肢が消えていきます。
同様のことがこの後も続きます。
例えば、先ほどの図から実はさらに頂点が存在していたとします。先ほど、青い頂点にいる際に、クリーム色の3つの頂点に色を塗りました。そして、今緑色の頂点に移動してきたとします。
緑色の頂点から行ける、親を除く頂点について色を塗ります(今回は水色の頂点になります)。
この場合も、水色から距離2以下の頂点のうち、すでに色が塗られているのは、今いる緑の頂点と、その親である青い頂点の2つのみになり、色塗り方は1番目の頂点が、2番目が
、3番目が
通りとなります。
ということで、
DFSか何かで頂点を探索しつつ、今いる頂点から次に行くことができる頂点について、
ただし
は
以上(次に行くことができる頂点数
)以下の任意の数字
をかけていけばよいです。
が、一番最初の根は通りであることと、そこから行ける頂点のみ、
であることに注意しなければなりません。
これを繰り返していけば、答えを求めることができます。
感想
この問題結構面白いと思いました。
コーナーケースに引っかからずに書けるようになりたいですね(今回はサンプルが合わないのでいいのですが…)
