Codeforces Round #388 (Div. 2)

http://codeforces.com/contest/749

A. Bachgold Problem

奇数なら 3+2+2+2+2+... と分解する。偶数なら 2+2+2+... と分解する。これが最大なのは明らかだろう。

B. Parallelogram is Back

三角形ABCに対して、答えになる点A',B',C'は下図のようになる。

C. Voting

queue を用いてシミュレーションする。queueDにはDの人のIDを、queueRにはRの人のIDを順に入れておく。

queueDとqueueRの先頭を見て、IDが小さい方を取り出す。

たとえばqueueDの先頭の方が小さかったら、queueDの先頭を取り出して、ID+nとしてqueueDに入れ直す。queueRの先頭は削除する。

D. Leaving Auction

a[i]:=i番目の人の最終的な金額という配列を作っておく。もし欠席がなければ、この配列の最大値を取る人が落札者である。

欠席が出たときは、たとえばjが欠席していたらa[j]=0としておく。欠席者がないとき同様に、この配列の最大値を取る人が落札者になる。

落札者が分かったら、落札が確定する一手前の落札者の金額を知りたくなる。これは、a[落札者]=0とした配列の最大値となる。

配列の値を書き換えて、全体の最大値を求める作業を高速におこなうのだからRMQが使える。

Inversions After Shuffle

長さKの順列をランダムシャッフルしたときの転倒数の期待値を求めよう。

たとえば1..5までの順序が確定していて、ここに6を挿入することを考える。このとき転倒数の増加量の期待値は$(0+1+2+3+4+5)/6$となる。

長さKの順列を作るには、この操作をK回繰り返せばいいので、期待値は、

$$\sum_{i=0}^{K - 1} \left( \frac{1}{i+1}\sum_{j=0}^{i}j \right) = \frac14 K(K - 1)$$

となる。

数列 $a$ を $x .y .z$ と分解して、$y$ をランダムシャッフルした数列の転倒数の期待値はどうなるだろうか。転倒数のペアが変わるとしたら、それは $y$ 内部のペアだけである。つまり、転倒数の期待値は $\mathrm{inv}(a)-\mathrm{inv}(y)+|y|(|y| - 1)/4$ である。

よって、すべての区間の転倒数の総和を求められれば期待値は求まる。

たとえば$(i,j)$が転倒のペアだったとしよう。このペアを含む区間がいくつあるのかというと$(i+1)\times(n-j)$個ある。このことを使うと、よくあるBITを用いた転倒数の計算法と似たような方法で、すべての区間の転倒数の総和が求められる。

Dで難しく考えてしまい、苦戦してしまった。