緩和しても良い
AtCoder
AtCoder500点
ABC-E
DP
操作
n個からk個選んだものの最適化
ある量を固定して考える
ある量を決めるとGreedy
シーケンシャルDP
緩和しても良い
絶対値に関する問題
順列
順列の最適化
Greedy
個数のみわかれば遷移が作れるDP
最大値や最小値に着目する
解を変形していく(最適性を失わずに)
ソート
探索順序を工夫して解く
探索順序を上手に決めると、普通の DP になる系！！！ EDPC の Zubton なんかもそうやね！ 問題へのリンク 問題概要 個の正の整数 が与えられる。これらを並び替える。並び替えのスコアは以下のようにして決まる。 各 に対して、 の index が に移動するとき…
Codeforces
最大公約数
ある量を固定して考える
O(N^2)個の区間を考える問題
数列
整数問題
緩和しても良い
互いに素
バケット
調和級数
包除原理
約数系包除
ソート
Greedy
枝刈り
stack
データ構造
エラトステネスの篩
メビウス関数
ならし計算量解析
約数
前処理
数値に10^5以下制約
最大公約数の値を固定して考える
勉強になった...けど、これ知らずにできるもんなの！？ 問題へのリンク あと、LCM の最小値バージョンもある！ drken1215.hatenablog.com 問題概要 個の正の整数 が与えられる。これらから 2 個選んで LCM をとってできる 個の整数の最大値を求めよ。 制約 …
AtCoder
AtCoder600点
ABC-F
幾何
端点のみを考える
探索候補を絞る
全探索
三角形
三角形の五心
緩和しても良い
解を変形していく(最適性を失わずに)
三分探索
山登り法
凸関数
連続最適化
最小包含円
幾何だ！！！！！ そして、こういうので「ギリギリを考える」というのは典型な感じ。 なお、僕は最小包含円のことを知らず、アドホックに解いたけど、ライブラリ貼るだけだったらしい... (その方が計算量も少ない) 他にも、三分探索でも解ける！！！ 問題へ…
AtCoder
AtCoder400点
ABC/ARC-D
二値パラメータ問題
最適解の形を考える
緩和しても良い
解を変形していく(最適性を失わずに)
データ構造
setの上手な使い方
差分更新
n個からk個選んだものの最適化
ある量を決めるとGreedy
ある量を固定して考える
Greedy
priority_queue
探索順序を工夫して解く
ソート
番兵法
学び多き問題。 僕にとっては後半のデータ構造パートが苦戦を強いられ、本当に勉強になった！ 問題へのリンク 問題概要 個の寿司があって、それぞれネタ と美味しさ をもっている。この中から 個の寿司を選びたい。選んだ寿司集合のスコアは 選んだ寿司の美…
Codeforces
調和級数
整数問題
バケット
ある量を固定して考える
ある量を決めるとGreedy
緩和しても良い
最大公約数
Greedy
復元
構築
数列
数値に10^5以下制約
最大公約数の値を固定して考える
天才か！！！ 問題へのリンク 問題概要 個の整数 が与えられる。 < となる であって、LCM() が最小となるものを求めよ。 制約 考えたこと という制約がいかにも怪しい。この制約が意味するのは 配列 a をバケットで表せる。すなわち a = (2, 3, 5) みたいな…
