かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

ABC150 E - Change a Little Bit

競技プログラミング 解説 ABC 典型 式変形

問題はこちら

問題概要

0,1からなる長さ{1\le N\le 2×10^5}の2つの数列{S,T}に対し, 関数{f(S,T)}を以下のように定める.

  • {S}に対し以下の操作を繰り返して{T}と等しくすることを考える. このとき行う操作のコストの和として考えられる最小の値が{f(S,T)}である.

    • {S_i}を(0から1, もしくは1から0に)変更する. この操作のコストは, 変更の直前に{S_i\neq T_j(1\le j\le N)}であったような整数{j}の個数を{D}として, {D×C_i}である.

全ての{S,T}の組に対して{f(S,T)}の和を{10^9+7}で割った余りを求めよ.

思考の流れ

変更する順番は{C_i}の小さい方からやるのがいいのはすぐわかる.
しかし, 考えるべき{(S,T)}の組み合わせは, {2^{2N}}通りある.
「全列挙できない場合は寄与分を考える」を使えそう.

{\downarrow}

今回は各{C_i}が何回足されるかを考える.
{C_i}がソートされているとして, 自分の後ろにある変更しなければならない{S_i}の個数分足される. {S}を一つ決めた時に{S}と{T}が{i}以降で異なっている位置の数が{k}個であるようなものの数は{{}_{N-i}C_{k}×2^{i-1}}個ある. つまり, {S}一つに対して

{\sum_{i=1}^{N}{C_i\sum_{k=0}^{N-i}{{}_{N-i}C_{k}×2^{i-1}×(k+1)}}}

あるので, 求める答えは

{2^{N}\sum_{i=1}^{N}{C_i\sum_{k=0}^{N-i}{{}_{N-i}C_{k}×2^{i-1}×(k+1)}}}

これをwolframalphaになげると

{2^{2N-2}\sum_{i=1}^{N}{C_i×(N-i+2)}}

となり, {O(N\log{N})}で求められる.

提出プログラム

https://atcoder.jp/contests/abc150/submissions/12542834

感想

wolframalphaはコンテスト前に開いておきましょう.