ARC119-Eを解いた. 問題 ×の赤青二色のグリッドが与えられる. 赤マスに対してそのマスを含む行又は列を全て白く塗れる. 白マスの数を最大化する操作を一つ構築せよ. 解法 赤であるマスについて、頂点 と頂点 の間に辺を張った二部グラフを考えると、完全に独…

AGC018-Dを解いた. 問題 頂点重み付き木が与えられる. の順列を選び、そのスコアをと定める(:=頂点と頂点の距離). スコアの最大値を出力せよ. 解説 まずスコアにを加えたものを考える. 主客転倒を考えればこの最大値は各辺について次の値を計算して足し合わ…