平均値制約を総和制約に変換する
「平均値が A」という制約は上手に扱うテクニックがある。 今回はそれを思いつかなくても解けるけど、思いつくと計算量が落ちる。 問題へのリンク 問題概要 個の整数 からいくつか選ぶ方法のうち、その平均値がちょうど となるものが何通りあるかを求めよ。 …
AtCoder
AtCoder600点
ARC-E
平均値
O(N^2)個のものを考える問題
数列
区間
数え上げ問題
累積和
転倒数
BIT
変数変換して扱いやすい同型な問題を見出す
平均値制約を総和制約に変換する
じょえちゃんえるから。 「平均値が 以上」という条件を見たときにパッと考えつく話がある。 問題へのリンク 問題概要 個の正の整数列 と整数 が与えられる。 整数列の連続する部分列であって、その平均値が 以上であるものが何個あるかを求めよ。 制約 考え…
