区間の交差
これ、「重なるものを数える」という風に考えれば、縦方向と横方向を独立に考えれば良いことに気付けるかが結構ポイントっぽい 問題へのリンク 問題概要 整数 が与えられます。 辺の長さが の白い正方形を座標平面の に 4 頂点が重なるように置きます。 次に…
Codeforces
EducationalCodeforces
in-place DP
DP
区間
区間ソート
DP高速化
DP高速化:累積和
累積和
前処理
各桁ごとに見る
各要素ごとに独立
区間の交差
区間の包含関係を除去できる
0と1の問題
数え上げ問題
いもす法
DP状態:その状態がどこまで続くのかを添字にもつ
DP高速化:オンラインオフライン変換
操作の流れを単純化する
CodeforcesR2500
実家 DP 苦手すぎる。今回は解法を簡単なものにするにあたって、「区間の左端も右端も単調増加と思って良い」というのが、割と効いてる気がする。 問題へのリンク 問題概要 長さ の数列であって、各要素の値が 以上 未満であるもののうち、以下の 個の条件を…
条件反射でいもす法をしたけれど、もっと楽にできた 問題へのリンク そして手前味噌ながら類題 atcoder.jp 問題概要 個の区間 があたえられる。 を満たしている。 この区間が 重に交わっている部分の長さを求めよ。 制約 解法 1：区間の交差 区間 と の交差…
