2020-04-24から1日間の記事一覧
「平均値が A」という制約は上手に扱うテクニックがある。 今回はそれを思いつかなくても解けるけど、思いつくと計算量が落ちる。 問題へのリンク 問題概要 個の整数 からいくつか選ぶ方法のうち、その平均値がちょうど となるものが何通りあるかを求めよ。 …
AtCoder
AtCoder600点
ARC-E
平均値に関する問題
解空間:O(N^2)通りの選択肢
数列
区間
累積和
転倒数
BIT
変数変換して扱いやすい同型な問題を見出す
平均値制約を総和制約に変換する
f(i,j)をiとjとに分離する
青色diff
解空間:O(N^2)個の区間
数え上げ問題
制約条件:ある値<=K
連続部分列を扱う問題
Zero-Sum Ranges
中堅以上の典型要素を詰め合わせた教育的問題
じょえちゃんえるから。 「平均値が 以上」という条件を見たときにパッと考えつく話がある。 問題へのリンク 問題概要 個の正の整数列 と整数 が与えられる。 整数列の連続する部分列であって、その平均値が 以上であるものが何個あるかを求めよ。 制約 考え…