平均値制約を総和制約に変換する
AtCoder
AtCoder700点
ARC-D
平均に関する問題
平均値制約を総和制約に変換する
特殊なmod
格子点をmodごとに分類する
戻すDP
DP
ナップサックDP
DP高速化
DP高速化:いもす法
DP高速化:累積和
前処理
多項式・形式的冪級数
個数重複も考慮したナップサックDP
数え上げ問題
各kに対して
各要素ごとに独立
入力が定数個
差分更新
in-place DP
黄色diff
K飛ばしで累積和
すごく NTT したくなる 問題へのリンク 問題概要 正の整数 が与えられる。 をそれぞれ 個以上 個以下とってくる方法のうち、平均が となるものの個数を素数 で割ったあまりを、各 に対して求めよ。 制約 考えたこと まず、平均制約を次のように言い換える。…
「平均値が A」という制約は上手に扱うテクニックがある。 今回はそれを思いつかなくても解けるけど、思いつくと計算量が落ちる。 問題へのリンク 問題概要 個の整数 からいくつか選ぶ方法のうち、その平均値がちょうど となるものが何通りあるかを求めよ。 …
AtCoder
AtCoder600点
ARC-E
平均に関する問題
O(N^2)個のものを考える問題
数列
区間
数え上げ問題
累積和
転倒数
BIT
変数変換して扱いやすい同型な問題を見出す
平均値制約を総和制約に変換する
f(i,j)をiとjとに分離する
青色diff
じょえちゃんえるから。 「平均値が 以上」という条件を見たときにパッと考えつく話がある。 問題へのリンク 問題概要 個の正の整数列 と整数 が与えられる。 整数列の連続する部分列であって、その平均値が 以上であるものが何個あるかを求めよ。 制約 考え…