ギリギリ
区間に含まれる点の重みの最大値を求める
区間
固定長区間が制約条件を持ちながら左右に移動する問題
そのまま覚えたい典型問題
二分探索:lower_bound
二分探索
ギリギリ
最適化テク:端点のみを考える
最大スコア
ソート
まずソートして考える
一直線上のN点の問題
AtCoder
AtCoder300点
灰色diff
ABC-C
最適化テク:探索候補を絞る
【問題集】二分探索の入門
【問題集】累積和・二分探索法・しゃくとり法
lower_bound() 系の教育的問題 問題へのリンク 問題概要 一直線上に 個の点がある。点 の座標は である。 この直線上で幅 の区間を配置する。左端の座標を とするとき、 を満たす の個数をスコアとする。最大スコアを求めよ。 制約 考えたこと まず重要な考…
AtCoder
ABC-F
黄色diff
ギリギリ
最適化テク:探索候補を絞る
最適化テク:端点のみを考える
一直線上のN点の問題
数え上げ問題
座標圧縮
平面走査
Greedy
マッチング
二部マッチング
区間
固定長区間が制約条件を持ちながら左右に移動する問題
AtCoder575点
高速な解法もあるっぽいけど、愚直に解いた。 問題へのリンク 問題概要 一直線上に 個の宝が座標 に配置されている。一方、長さが である 本の棒がある。次の条件を満たす整数 の個数を求めよ。 各 に対して、座標 の点を始点とするように棒を置いたとき、棒…
AtCoder
AtCoder400点
ABC-D
水色diff
ギリギリ
最適化テク:端点のみを考える
最適化テク:解を変形していく(最適性を失わずに)
二次元平面上のN点の問題
二次元累積和
全探索
制約条件:長方形領域
最適化テク:探索候補を絞る
計算幾何
WaveletMatrix
区間の長さの最大値または最小値を求める
古き良き全探索問題！！ 問題へのリンク 問題概要 二次元平面上に 個の点があります。 番目の点の座標を とします。 この二次元平面上で各辺が X 軸・Y 軸に平行であるような長方形であって、 個の点のうち 個以上の点を内部および周に含むようなものを考え…
Codeforces
CodeforcesDIV1-D
CodeforcesR2600
CodeforcesR3000
Zero-Sum Ranges
色に関する問題
種類数
最頻値に関する問題
連続部分列を扱う問題
解空間:O(N^2)通りの選択肢
中間値の定理
ギリギリ
最適化テク:端点のみを考える
最適化テク:解を変形していく(最適性を失わずに)
平方分割
最適化テク:緩和しても良い
可視化テク:標高図を考える
場合分け
区間
平面走査
しゃくとり法
テク:総和がNになる整数組の種類数はO(√N)
O(√N)まで考えれば十分
数列
テク:26文字のアルファベット文字を個別に考える
ある量を固定して考える
区間の長さの最大値または最小値を求める
平方分割で解法を分岐する系の問題で、そのうちの片方の問題は Easy Version として D1 で出題されてた (Easy Version は R2600) 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数のみからなる 要素の数列 が与えられる。 数列の連続する区…
