Dilworth の定理から、DAG の最小パス被覆！！ かつて流行った高度典型。 問題へのリンク 問題概要 個の文字列 が与えられる。各文字列には重み がついている。 これらの文字列から「どの 2 つの文字列も互いに他を部分文字列として含まない」という条件を満…

いわゆる「木上の最大安定集合問題」です！ 超典型問題です。 問題へのリンク 問題概要 頂点数 の木が与えられます。木からいくつかの頂点を選んで削除します。その結果、木はいくつかの連結成分に分かれます。 分かれた連結成分の個数の最大値を求めてくだ…

二部マッチングの復元にてこずって、間に合わなかった... 問題へのリンク editorial 問題概要 個の正の整数 の部分集合であって、以下の条件を満たすもののうち、要素数が最大のものを 1 つ求めよ。 どの要素も 6 で割ったあまりが 1 ではない どの要素も約…

TLE が厳しかった... 問題へのリンク editorial 問題概要 頂点数 の単純無向グラフ が与えられる (連結とは限らない)。各頂点 には重み がついている。 頂点 1 を含む の安定集合をすべて考えたときの、安定集合中の頂点の重もの総和の最大値を求めよ。 制約…

アルファベットは 26 文字！26 は偶数！ 問題へのリンク 問題概要 (意訳) 頂点数 、辺数 の無向単純グラフ が与えられる。各頂点 には、1 文字の英小文字 が振られている。ここで正の整数 が与えられ、改めて次のように定義されるグラフ を考える の頂点集合…

「二部グラフの最大安定集合問題」について知っていれば典型問題ですね。 問題へのリンク 問題概要 のグリッドがあります。各マスは白黒に塗られています。今、白いマスにできるだけ多くのコマを置きたいものとします。 各マスに 1 個のみコマを置ける コマ…

本番フローで無理矢理解いた！！！ でも DP が本筋だね。 問題へのリンク 問題概要 の順列 が与えらえる。これを 整数 を選んで区間 [ ) を左シフトする、すなわち をそれぞれ へ置き換える、これにコスト がかかる 整数 を選んで区間 [ ) を右シフトする、…

ARC 099 E - Independence の類題という感じ。具体的には「補グラフをとって二部グラフを考えて...」みたいなところのが似てる。 問題へのリンク 問題概要 人の女の子と、 人の男の子がいて、「女の子同士」「男の子同士」はすべて互いに知り合いである。 そ…