AGC050-Bを解いた 問題 重み付きの木(辺が結んでいるのは頂点と、重みは)が与えられる。どれか一つ辺を選んでその辺と頂点を一つ共有するすべての辺について重みを選んだ辺の重みとの排他的論理和に置き換える。目標の重み()を達成するのは可能か? 解法 辺に…

AGC050-Cを解いた。 問題 無限に続く一列のマス目上で次のゲームを行う。文字列があって、S の時、Snuke君が1マス隣の空きマスに動くか、何もせずとどまる。B の時、あなたは任意のマスを一つ選び通行不可にする。Snukeの両脇が通行不可である状態になったら…

ARC115-Dを解いた問題 無向グラフが与えられて、いくつか辺を削除できるとき奇点の数が 個 となるものの通り数 mod998を求める。 解法 連結成分ごとに独立に考えられる。グラフの全域木を取って、に含まれない辺を消すかどうか適当に選んだ後にに含まれる辺…

ARC111を解いた 問題 頂点から到達できる頂点が個になるように、無向グラフの各辺に向きを付ける。解が存在する入力のみ与えられる。 解法 各辺について、であるものは向きが明らかで、そうでないものは閉路に用いられている辺となる。解が必ず存在すること…