Change a Little Bit [AtCoder Beginner Contest 150 E]

https://atcoder.jp/contests/abc150/tasks/abc150_e

解説

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

多分、何から考えていいかわからない人が多いだろう。
何か限定的に考えていける部分がないか見てみると、とりあえずf(S,T)を求めるにはどうすればいいかというのがある。
操作すべきiは、S[i]!=T[i]部分だけであり、S[i]=T[i]を操作しても無駄であることは分かるだろう。
あとはどの順番で操作を行うかであるが、Dは単調減少していくので、C[i]の小さい順でやっていくのが
最適っぽい。
まあ、それはわかったけど、で？という雰囲気。

大体何かを全探索して、計算していくが、全探索できるのはC[i]くらい。
f(S,T)の総和は？C[0]+？C[1]+...となるので、この？の部分を高速に計算できれば、
C[i]で全探索することで、総和を求めることができる。
ちょっと飛躍した発想に見えるかもしれないが、？のような場合の数、組み合わせ的なものを求めて、
値と掛け合わせることで総和を求めるテクは多くの問題で見られる。

さて、残りの問題が、f(S,T)においてC[i]の係数が何であるかという問題になった。
元々の問題よりかはマシになったが、まだ難しい。
この係数が何を示すかというと、すべてのS[i]!=T[i]であるS,Tの組において、
S[j]!=T[j]であり、S[i]≦S[j]である個数の総和
具体的な数はここでは関係ないので、N, N-1, ... 3,2,1に対してこれを考えてみる。
降順になっているのは、以上の個数を考えていくからである。
これは期待値を考えると実は早い。
i番目の数において、C[i]≦C[j]の個数の期待値を考えると、(i + 1)/2である。
場合の数は4^N-12であるため、個数の総和は、期待値×場合の数で、(i+1)/24^N-12=4^N-1(i+1)
4^N-12C[0] + 4^N-13C[1] + ...
=4^N-1(2C[0] + 3*C[1] + ...)
となり、これが答え。

int N, C[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> C[i];
    sort(C, C + N, greater<int>());

    mint ans = 0;
    rep(i, 0, N) ans += mint(i + 2) * C[i];
    rep(i, 0, N - 1) ans *= 4;
    cout << ans << endl;
}