drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder600点 ARC-E 平均値に関する問題 解空間:O(N^2)通りの選択肢 数列 区間 累積和 転倒数 BIT 考察：変数変換 変数変換：「値の平均がA」⇔「値-Aの総和が0」 f(i,j)をiとjとに分離する 青色diff 解空間:O(N^2)個の区間 数え上げ問題 制約条件:ある値<=K 連続部分列を扱う問題 Zero-Sum Ranges 中堅以上の典型要素を詰め合わせた教育的問題 じょえちゃんえるから。 「平均値が 以上」という条件を見たときにパッと考えつく話がある。 問題へのリンク 問題概要 個の正の整数列 と整数 が与えられる。 整数列の連続する部分列であって、その平均値が 以上であるものが何個あるかを求めよ。 制約 考えたこと 一般に、 の平均値が 以上 ⇔ の平均値が 以上 ⇔ の総和が 以上 という言い換えができる。「平均値」に関する条件が、なんと「総和」に関する条件へと早変わりして、滅茶苦茶扱いやすくなるのだ。というわけで、元の問題は次の問題へと言い換えることができる。 個の整数 の連続する部分列であって、その総和が 以上であるものが何個あるかを求めよ。 累… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F04%2F24%2F015400" title="AtCoder ARC 075 E - Meaningful Mean (青色, 600 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2020-04-24 01:54:00 rich https://drken1215.hatenablog.com/entry/2020/04/24/015400 1.0 100%