n個からk個選んだものの最適化
今日の ABC 151 F で、「三分探索」とか「山登り法」とか聞いたので！！！ 問題へのリンク 問題概要 二次元平面上に 個の点が与えられる。 今、好きな位置に点を打って、その点から 個の点との距離のうち、大きい順に 個の総和をとる。 上手に点を打ったとき…
最初、罠に引っかかった 問題へのリンク 問題概要 長さ の数列 が与えられる。これらの連続する区間の総和を書き出していく ( 個ある)。 これらの中から 個選んで AND をとった値として考えられる最大値を求めよ。 制約 嘘貪欲 とりあえず なので、 個の整数…
二乗の木 DP の例題として、すごくいい感じ！！！ 問題へのリンク 問題概要 頂点のツリーが与えられて、各頂点 には 人がいる。いま、人を移動させて、各頂点の人数の最大値と最小値との差が 1 になるようにしたい。 1 人が辺 1 個分を移動するのに必要なコ…
AtCoder
AtCoder400点
ABC/ARC-D
二値パラメータ問題
最適解の形を考える
緩和しても良い
解を変形していく(最適性を失わずに)
データ構造
setの上手な使い方
差分更新
n個からk個選んだものの最適化
ある量を決めるとGreedy
ある量を固定して考える
Greedy
priority_queue
探索順序を工夫して解く
ソート
番兵法
学び多き問題。 僕にとっては後半のデータ構造パートが苦戦を強いられ、本当に勉強になった！ 問題へのリンク 問題概要 個の寿司があって、それぞれネタ と美味しさ をもっている。この中から 個の寿司を選びたい。選んだ寿司集合のスコアは 選んだ寿司の美…
ラグランジュ緩和か、、、なのん しかしこれ、ある特定の 1 頂点について次数が 以下であるような最小全域木を求める問題とみなせるわけだけど、こんなんが解けるのは面白いのんな。 全域最小木スライドにある通り、全頂点について次数が 以下となるような最…
