各アルファベットごとに考える
Codeforces
CodeforcesDIV1-D
CodeforcesR2600
CodeforcesR3000
Zero-Sum Ranges
色に関する問題
種類数
最頻値
連続部分列を扱う問題
O(N^2)個のものを考える問題
中間値の定理
ギリギリ
端点のみを考える
解を変形していく(最適性を失わずに)
ヒストグラム
平方分割
緩和しても良い
標高図を考える
場合分け
区間
平面走査
しゃくとり法
総和がNになる整数組の種類数はO(√N)
O(√N)まで考えれば十分
数列
各アルファベットごとに考える
ある量を固定して考える
平方分割で解法を分岐する系の問題で、そのうちの片方の問題は Easy Version として D1 で出題されてた (Easy Version は R2600) 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数のみからなる 要素の数列 が与えられる。 数列の連続する区…
AtCoder
AtCoder400点
ARC-D
ABC-D
水色diff
条件の言い換え
区間
O(N^2)個のものを考える問題
文字列問題
復元
連続部分列を扱う問題
必要条件を列挙したら十分条件になる
各アルファベットごとに考える
個別の要素の動きに注目する
面白かった 問題へのリンク 問題概要 文字列 がアンバランスであるとは、 の中の文字のうち、過半数が同じ文字 であることを指すものとする。長さ の文字列 が与えられたとき、 の連続する部分文字列であって、アンバランスなものがあるかどうかを判定せよ。…
AtCoder
AtCoder500点
クエリ処理問題
変化・遷移が限られる
文字列問題
種類数
BIT
セグメント木
setの上手な使い方
ABC-E
水色diff
各アルファベットごとに考える
色に関する問題
一瞬、「更新がある」「種類数」ということで、Wavelet Matrix が必要かとびびった 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の 個のクエリに答えよ タイプ 1： の 文字目を に変更する タイプ 2： の区間 に含まれる文字の種類数を答える …
AtCoder
AtCoder700点
DP
DP高速化
変化・遷移が限られる
区間
区間分割型ナップサックDP
回文
パリティ
DP高速化:累積和
累積和
bitDP
黄色diff
AGC-like
スライドbitDP
Zero-Sum Ranges
各アルファベットごとに考える
遷移先を絞れる系の DP 問題へのリンク 問題概要 長さ の文字列 が与えられる。これを以下の条件を満たすように最小個数の区間に分割したい。最小個数を求めよ。 どの区間についても、区間内の文字を適切に並び替えると回文になる 制約 考えたこと まず「文…
