問題 それぞれの頂点の次数が3以下の無向グラフが与えられる。 このグラフの頂点を0か1の色に塗り分けて、 すべての頂点について、その頂点につながる同じ色の頂点の数を1つ以下にしたい。 そのような塗り方を具体的に一つ求めよ。 不可能な場合は-1を返せ。…

問題 木が与えられる。 この木のそれぞれのノードを、1/2の確率で赤、1/2の確率で白に塗る。 塗り終えた後で、同じ色のノードを全て連結にするために、自由に辺を足す。 ただし、それぞれのノードに新たに追加できる辺は、 1本目は無料で、2本目以降は1ずつ…