最頻値に関する問題
Codeforces
CodeforcesDIV1-D
CodeforcesR2600
CodeforcesR3000
Zero-Sum Ranges
色に関する問題
種類数
最頻値に関する問題
連続部分列を扱う問題
解空間:O(N^2)通りの選択肢
中間値の定理
ギリギリ
最適化テク:端点のみを考える
最適化テク:解を変形していく(最適性を失わずに)
平方分割
最適化テク:緩和しても良い
可視化テク:標高図を考える
場合分け
区間
平面走査
しゃくとり法
テク:総和がNになる整数組の種類数はO(√N)
O(√N)まで考えれば十分
数列
テク:26文字のアルファベット文字を個別に考える
ある量を固定して考える
区間の長さの最大値または最小値を求める
平方分割で解法を分岐する系の問題で、そのうちの片方の問題は Easy Version として D1 で出題されてた (Easy Version は R2600) 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数のみからなる 要素の数列 が与えられる。 数列の連続する区…
Codeforces
EducationalCodeforces
マージテク
木
グラフ
各kに対して
木DP
最頻値に関する問題
色に関する問題
最適解の数え上げ
CodeforcesR2300
【問題集】木DPのステップアップ
マージテク童貞を卒業した!!! 問題へのリンク 問題概要 頂点の根付き木が与えられる (根の番号は 1)。また各頂点 には色 が塗られている。色は整数値で表される。各頂点 について、以下の問いに答えよ。 その頂点を根とした部分木を考える その部分木で「…
AtCoder
AtCoder300点
ABC-C
バケット
最頻値に関する問題
数列
最適化テク:最適解の形を考える
コーナーケース
緑色diff
ARC-C
second best を管理する
for文
最小回数・最小個数を求める
操作
操作:1文字を変更する
集計処理
最適化問題
意外と罠にはまりやすい問題かもしれない!!! この手の問題は「最適解の形を考える」という意識で解くと良さそう。 そして、コーナーケースがサンプルにあるのが親切。 問題へのリンク 問題概要 長さ ( は偶数) の数列 が /\/\/\/ であるとは 任意の に対…
Mo のアルゴリズムの練習第二弾。 問題へのリンク 問題概要 要素の整数列 が与えられる。以下の 個のクエリに答えよ: 数列の区間 [ ) 内に最も多く登場する値が、何回登場しているかを答えよ 制約 考えたこと Mo の練習第二弾。 最頻値の頻度を求めるのは、…