問題原文 atcoder.jp 問題要旨 . と # から構成されるグリッドが与えられる。 . の場所を１つ指定して、「そのマスと、そのマスから上下左右に # にぶつかるまで . を塗る」とき、塗られるマスの数を最大化せよ。 解法 にしたい。 各マスを指定したパターン…

問題原文 atcoder.jp 問題要旨 木の頂点を、「同色で塗られた任意の２頂点間の距離が偶数」となるように、２色で塗り分けよ。 解法１：LCAを考える LCAの考え方の利用 図より、 この式の第３項は偶数なので、 が偶数の時のみ、 頂点 と 頂点 は同色で塗られ…

問題原文 atcoder.jp 問題要旨 木の上で高橋くんと青木くんが鬼ごっこをする。高橋くんは逃げる側、青木くんは逃げる側。 高橋くんから、「相手と同じ頂点にいたらゲーム終了。そうでなければ１手移動。」を繰り返す。 高橋くんは出来るだけ捕まらないように…

問題原文 E - Travel by Car 問題要旨 町と道が重み付き無向連結グラフの形で与えられ、この町の間を容量Lリットルの燃料タンクを持つ車で移動することを考える。移動距離１につき、燃料を１消費し、燃料が０になればそれ以上は進めない。また、各町で燃料を…

問題原文 D - Coloring Edges on Tree 問題要旨 頂点の木の各辺を塗り分けることを考えます。このとき、各頂点について、その頂点から伸びる辺の色がすべて異なるようにしたいです。 この条件を満たす塗り分けの中で、使用する色の数が最小であるようなもの…