なんとなくできそうだけどできないみたいな問題だった。そうか、牛ゲーに帰着すれば明快だ... 問題へのリンク 問題概要 頂点数 、辺数 の連結グラフが与えられる。いくつかの辺は無向辺であり、いくつかの辺は有向辺である。 各頂点 に 0 以上の整数値 を割…

テスターだった。 簡単枠の Easy ヴァージョンに対して「制約あげられるね」と提案して、正式に問題セットになった！ 問題へのリンク editorial 問題概要 のグリッドがあって、各マスは '.' か 'B' から成っている。'B' マス間のマンハッタン距離として考え…

DP 復元非本質＞＜ 問題へのリンク 問題概要 人のコンテスタントを 3 人以上を 1 チームとしたいくつかのチームに分割したい。コンテスタント のスキルは である。 チーム分けの良さを、各チームごとの「メンバーのスキルの最大値と最小値の差」の合計値とす…

最適解の形を丁寧に場合分けして考える系 問題へのリンク 問題概要 の板チョコレートを 3 つの長方形に割りたい。そのときの 3 つの長方形の面積の最大値と最小値の差の最小値を求めよ。 制約 考えたこと まず思ったのは、 のうちの少なくとも一方が 3 の倍…

こういう系の「個別要素に分解して考える」という問題が三連発だ！！！！！ これもあれも！ drken1215.hatenablog.com drken1215.hatenablog.com 問題へのリンク 問題概要 個の整数 が与えられる。これらから 個を選ぶ 通りの方法についての 「選んだ 個の整…

今の 300 点に比べると少し易しめで、でも 300 点っぽくていい感じだなと。 問題へのリンク 問題概要 個の整数 が与えられる。ここから 個の整数を選ぶ。 「選ばれた数の最大値と最小値の差」の最小値を求めよ。 制約 < 考えたこと すごく 300 点問題っぽく…

解き切りたかった 問題へのリンク 問題概要 オレンジが 個、みかんが 個ある。これを 人で分け合う ( が の倍数であることは保証される)。 それぞれの人 について、オレンジとみかんそれぞれ 1 個あたりの満足度が で与えられる。 うまく分けて、各人の満足…

かなり悩んだ 問題へのリンク 問題概要 長さ の整数列 を 3 箇所で切って、4 つの連続する数列に切り分ける。このとき、4 つの区間の値の和を とするとき、 の最小値を求めよ。 制約 考えたこと こういうの、 連続する区間が 4 個だけであることを活かす解法…

ARC 098 E Range Minimum Queries 問題概要 長さ N の数列 A と整数 K が与えられる。 この配列に、以下の操作を Q 回行います。 長さ K の連続する部分列を 1 つ選ぶ。 そして、選んだ部分列に含まれる K 個の要素のうち最小のもの（複数ある場合はその中で…