StarrySkyTree
Codeforces
二値パラメータ問題
セグメント木
StarrySkyTree
差分更新
ある量を固定して考える
二分探索
ソート
探索順序を工夫して解く
lower_bound
累積max
CodeforcesDIV1-C
CodeforcesR2000
セグ木を使って差分更新していく系、解けるけど実装が苦手すぎるので、こういうのをスパッと書けるようになりたい! 問題へのリンク 問題概要 個の武器と、 個の盾を持って、 体の敵に立ち向かう。あたなは武器の中から 1 個、盾の中から 1 個を選ぶ (初期状…
Codeforces
順列
操作
データ構造
セグメント木
遅延評価
StarrySkyTree
差分更新
ある量を固定して考える
in-place DP
DP
最小コスト
CodeforcesR2200
EducationalCodeforces
これを思い出して迷走してしまった (それでも通る解法には至ったけど恐ろしく煩雑なものとなってしまった)。 drken1215.hatenablog.com なぜもっとシンプルに考えられなかったのか... 問題へのリンク 問題概要 の順列 と、各要素 を動かすのに必要なコスト …
AtCoder
AtCoder600点
ABC-F
ソート
最小回数
操作
データ構造
セグメント木
遅延評価
StarrySkyTree
解を変形していく(最適性を失わずに)
端から順に決まって行くGreedy
Greedy
区間
操作:区間
二分探索
BIT
端点のみを考える
いもす法
累積和
イベントソート
しゃくとり法
queue
応用的な探索
水色diff
区間加算に対応したデータ構造の出番! 問題へのリンク 問題概要 体のモンスターがいて、それぞれ座標 にいて、HP は である。すべてのモンスターを倒したい。 1 回の魔法で、座標 を指定して、[ ] の範囲内にいるモンスターの HP をすべて ずつ減少すること…
Codeforces
二次元平面上に可視化する
二次元平面上のN点の問題
セグメント木
平面走査
遅延評価
StarrySkyTree
復元
区間
区間ソート
座標圧縮
データ構造
差分更新
EducationalCodeforces
CodeforcesR2500
「区間」と「二次元平面上の点」とはしばしば互いに行き来することで問題が解けたりする!!! 問題へのリンク 問題概要 二次元平面上の 点が与えられる (いずれも 座標が 0 以上の格子点)。各点にはスコア が与えられる。 対角線のうちの一つが 上にあるよ…