テク:区間をsetで管理する
AtCoder
JOI
JOI難易度8
JOIG
JOIG春合宿
テク:区間をsetで管理する
Greedy
Greedy:交換しても悪化しない
Greedy:今が良いほど未来も良い
区間
区間ソート
N個の区間の問題
disjointな区間の集合を管理する問題
探索順序を工夫して解く
priority_queue
区間スケジューリング
各区間から1点ずつとってくる問題
ならし計算量解析
被覆
最大スコア
最適化テク:解を変形していく(最適性を失わずに)
座標圧縮
最適化問題
JOI ではお馴染みの「 個の区間を扱う問題」。ただし実装がしんどかった。僕は区間を set で管理する方法で実装した。 問題へのリンク editorials 問題概要 制約 考えたこと いかにも貪欲法の香りが漂っている問題ですね。この手の問題では、 個の区間を終端…
AtCoder
AtCoder475点
ABC-E
緑色diff
setの上手な使い方
連想配列(setやmap)
遅延評価セグメント木
セグメント木上の二分探索
mex
補集合を考える
見積り大事
テク:区間をsetで管理する
数列
クエリ処理問題
クエリ:更新
削除可能priority_queue
クエリ:削除
クエリ:最大値・最小値の取得
データ構造をいい感じに設計する地力が問われる! 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対する以下の 個のクエリに答えよ。 各クエリでは整数 が与えられる を に置き換える 置き換えたあとの数列 の mex を出力せよ 制約 考えたこ…