2023-08-13から1日間の記事一覧
yukicoder
全部混ぜて解く
探索順序を工夫して解く
Greedy
Greedy:どちらも可なら厳しい方
マッチング
Greedyなマッチング
二部マッチング
Greedy:交換しても悪化しない
二値パラメータ問題
setの上手な使い方
平面走査
Hallの結婚定理
Monge性
anti-Monge性
天才のGreedy
難しいGreedy
非自明な比較関数でソートする
めっちゃいい Greedy 問題だった!! 問題へのリンク 問題概要 個の商品があり、 番目の商品は、一般客は 円で購入でき、MMA 部員は 円で購入できる。なお、MMA 部員が一般客と比べて得できる商品もあれ得て、損する商品もあり得る。 人がいて、 人目は「一…
Codeforces
DP
区間分割型ナップサックDP
区間
DP状態:state
負値が本質的に効く問題
絶対値やminを扱う問題
最大値の最大化
最適化テク:「最大値の最大化」に基づく緩和
DP高速化
DP高速化:直前との比較のみでよい
DP状態:長さの総和
数列
二値パラメータ問題
テク:|x|=max(-x,x)
DP状態:ビット
最大スコア
マルチテストケース問題
ナップサックDP
区間分割の仕方を走査する問題
最適化問題
つい最近 CodeQUEEN 決勝 E 問題でも出てきた「最大値の最大化」典型テクニック!!!! 問題へのリンク 問題概要 長さ の 2 つの数列 と が与えられる。今、互いに disjoint な区間群 をとる ( は自由)。ただし、区間の長さの総和がちょうど となるようにす…
Codeforces
区間
区間ソート
最適化テク:緩和しても良い
区間の交差
「次の要素」へのポインタを求める
DP
点が移動していく問題
クエリ処理問題
マルチテストケース問題
操作の流れを単純化する
区間を整理する考え方が楽しかった。 問題へのリンク 問題概要 下図のように 組の「黒い区間」と「赤い区間」がある。赤い区間は黒い区間に完全に包含されている。 この区間上でコマを動かしていく。コマが 番目の黒い区間の内部にあるとき、 番目の赤い区間…