最大値と最小値の差の最小化
なんとなくできそうだけどできないみたいな問題だった。そうか、牛ゲーに帰着すれば明快だ... 問題へのリンク 問題概要 頂点数 、辺数 の連結グラフが与えられる。いくつかの辺は無向辺であり、いくつかの辺は有向辺である。 各頂点 に 0 以上の整数値 を割…
最適解の形を丁寧に場合分けして考える系 問題へのリンク 問題概要 の板チョコレートを 3 つの長方形に割りたい。そのときの 3 つの長方形の面積の最大値と最小値の差の最小値を求めよ。 制約 考えたこと まず思ったのは、 のうちの少なくとも一方が 3 の倍…
今の 300 点に比べると少し易しめで、でも 300 点っぽくていい感じだなと。 問題へのリンク 問題概要 個の整数 が与えられる。ここから 個の整数を選ぶ。 「選ばれた数の最大値と最小値の差」の最小値を求めよ。 制約 < 考えたこと すごく 300 点問題っぽく…
解き切りたかった 問題へのリンク 問題概要 オレンジが 個、みかんが 個ある。これを 人で分け合う ( が の倍数であることは保証される)。 それぞれの人 について、オレンジとみかんそれぞれ 1 個あたりの満足度が で与えられる。 うまく分けて、各人の満足…
かなり悩んだ 問題へのリンク 問題概要 (ARC 100 D / ABC 102 D) 長さ の整数列 を 3 箇所で切って、4 つの連続する数列に切り分ける。このとき、4 つの区間の値の和を とするとき、 の最小値を求めよ。 制約 考えたこと こういうの、 連続する区間が 4 個だ…
ARC 098 E Range Minimum Queries 問題概要 長さ N の数列 A と整数 K が与えられる。 この配列に、以下の操作を Q 回行います。 長さ K の連続する部分列を 1 つ選ぶ。 そして、選んだ部分列に含まれる K 個の要素のうち最小のもの（複数ある場合はその中で…
