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

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

cf div1 694-Dを解いた. 問題 頂点辺の無向グラフが与えられる.最初、全ての頂点が白で、次の条件を満たすようにいくつかの頂点を黒く塗ることを考える. 1. 両端が黒い辺が存在しない. 2. 全ての頂点の組について、片端が黒い辺のみを通って移動できる. この…

cf div1 692-B 問題 からなる文字列が与えられる.中のを全てに書き換えて得られる文字列に対して、(連続とは限らない)部分列が現れたらコスト、が現れたらコストがかかる.コストの最小値を求めよ. 解法 として一般性を失わない(そうでない場合、をswap,中の…

ARC105-Eを解いた, 問題 与えられた頂点辺のグラフに対して先手と後手が辺を追加していく.しかし、頂点と頂点を連結にするような辺は追加できない.操作できなくなったら敗北、敗北しなかった方の勝利. 両者が最適に行動したときに勝利するのはどちらか. 解法…

ABC201-Fを解いた 問題 順列に対して、次の操作を繰り返しを狭義単調増加にする。コストの最小値は? - を満たすを選択し、を好きな位置に移動させる。 - を満たすを選択し、を左端に移動させる。 - を満たすを選択し、を右端に移動させる。 かかるコストは上…

AGC037-Eを解いた。 問題 整数、文字列が与えられる。 ← ( + )の長さの連続部分列 という操作を回行う。操作後のとして考えられるもののうち、辞書順最小のものは? 解法 内の最小文字 と置く。前からできるだけを連続させることを考えると 個だけ連続させる…