AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

グラフ

ABC129 D - Lamp

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

ABC126 D - Even Relation

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

ABC148 F - Playing Tag on Tree

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

ABC143 E - Travel by Car

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

ABC146 D - Coloring Edges on Tree

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