K飛ばしで累積和
個置きに累積和をとるの、3 ヶ月前の僕だったら思いつかなかったかもしれない。 問題へのリンク 問題概要 整数 が与えられる。また、長さ の 0 と 1 のみからなる文字列 が与えられる。文字列 に対して以下の操作を行うことができる。 文字列 中の文字 "0" …
AtCoder
AtCoder1000点
AGC-D
橙色diff
数え上げ問題
DP
DP高速化
戻すDP
前処理
数列
グラフ・盤面・数列の個数の数え上げ
操作:区間に等差数列を足す
変数変換して扱いやすい同型な問題を見出す
個数重複も考慮したナップサックDP
ナップサックDP
左右両端からの結果を前処理
入力が定数個
平方分割
総和がNになる整数組の種類数はO(√N)
「総和=K」を扱う
最大値と最小値を求める
ダブルカウントを防ぐ場合分けのテクニック
O(√N)まで考えれば十分
凸関数
K飛ばしで累積和
ジグザグ
階差数列
最初は二次元 FFT が必要な気分になっていて右往左往していた。個数制限なしナップサック問題になるのは面白かった！ 問題へのリンク 問題概要 正の整数 が与えられる。長さ の非負整数列 であって という条件を満たすものの個数を、1000000007 で割ったあま…
AtCoder
AtCoder700点
ARC-D
平均に関する問題
平均値制約を総和制約に変換する
特殊なmod
格子点をmodごとに分類する
戻すDP
DP
ナップサックDP
DP高速化
DP高速化:いもす法
DP高速化:累積和
前処理
多項式・形式的冪級数
個数重複も考慮したナップサックDP
数え上げ問題
各kに対して
各要素ごとに独立
入力が定数個
差分更新
in-place DP
黄色diff
K飛ばしで累積和
すごく NTT したくなる 問題へのリンク 問題概要 正の整数 が与えられる。 をそれぞれ 個以上 個以下とってくる方法のうち、平均が となるものの個数を素数 で割ったあまりを、各 に対して求めよ。 制約 考えたこと まず、平均制約を次のように言い換える。…
