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

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

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

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

ARC128-Dを解いた 問題 数列が与えられる。を満たすを削除する操作を好きなだけ行う。最終的なの数mod998244353を求める。 解法 まず、2つ以上同じ数が連続している部分について考える。ここに含まれる数は絶対に削除できない。 以後2つ以上連続している部分…

ARC168-Dを解いた 問題 個の白いマス目と個の操作が与えられる。個目の操作では、を満たすマス目を黒く塗る。ここで、操作前よりも操作後のほうが黒いマスが多くないといけない。最大操作回数は? 解法 区間]だけ考えた時の最大操作回数 としてDPする。とを合…

ARC136-Cを解いた 問題 円環状で要素がすべての数列の連続部分列にを加算する操作を何回か行う。所望の数列に一致させる最小操作回数は何回? 解法 から減算を繰り返して数列の要素をすべてにすることを考える。 、 (はとして) 、と置く。減算する区間の端に…

AGC054-Cを解いた 問題 順列について、隣接swapで各について自分より前のであるの数を以下に抑えたい。操作回数はなるべく小さく。操作後のはになる。元のとして考えられる順列の数をで求める。 解法(自分の) としてふさわしいものを考えると、以上以下の数…

AGC053-Bを解いた 問題 長さが偶数の非負整数列が与えられる。先手がから一つ選び、後手はの中央のindexの値を選ぶ。先手が選んだ要素の和を最大化する。 解法 、とする。先手はどちらかの数列の要素を一つ選び、後手は先手が選ばなかった方の数列の先頭を選…

ARC127-Dを解いた 問題 非負正整数列が与えられる。を求める。 解法 として、上位bitから見ていく。bit目を見た時にのbit目とのbit目が異なる整数組はとのどちらが小さいか定まる。等しい組に関しては、再帰的にbit目を見ていく。 考察 上位bitから見ていく…

ARC140-Dを解いた 問題 数列が与えられる間に辺を張っていく。の時はは自由に決めていい。あり得るすべてのグラフの連結成分数の総和を求める。 解法 であるについて先に辺を張ってみる。すると連結成分は全てなもりグラフか木。なもりグラフの連結成分には…

ARC146-Dを解いた 自分の考察 なるべく一番目の条件を満たすようにを埋めていきたい。しかし、で片方だけがの時に無理。が取りうる最小の値、として二番目以上の条件を選ぶことが確定した辺、三番目の条件を選ぶことが確定した辺を使ってを更新していく。こ…

ARC163-Dを解いた。 自分の考察 トーナメントグラフの性質をもとにいろいろ考えた。DPなんだろうな～とは思ってはいたが... もぐらいだから分け方全探索も考えたけど無理だった... 解法 あるトーナメントグラフでその強連結成分が個あるとき、頂点を二つの集…

AGC063-Cを解いた。 自分の考察 「全体にと足す」操作があるため(あとでmodを取るが)、要素間の差に注目しようとした。ある二項間の差をと置けばまたはに置き換わるから～と考えたが結局解けず。 解法 が昇順に並んでいるとすれば、上手くを選べばのみが減る…