ARC#031 C.積み木

その他 過去問

問題

高さの違うN個の積み木が並べてある。
隣り合う2つを交換する操作を何回か繰り返して、h_1 < h_2 < ... < h_i > h_i+1 > ... > h_Nとなるようにしたい。
そのようにする最小交換回数を返す。

N <= 10^5
積み木の高さ <= N

考え方

高さの小さい積み木から左右のどちらかにその積み木より高い積み木がなくなるまで動かしていく。
単純にやると、各積み木で「左に動かす場合の交換回数」と「右に動かす場合の交換回数」を確認する必要があるため、O(n^2)かかってしまう。


そこで、「左に動かす場合の交換回数」＝「左側にあるその積み木より高い積み木の数」を効率的に計算したい。
BIT(FenwickTree)を使うと、0〜iまでの合計値、各要素への加算操作がO(log n)で行える。
なので、BITに「ある積み木の高さよりも高い積み木の個数」を持たせることで、個数の合計値をO(log n)で求められる。


具体的には、BITは最初、すべての要素を1にしておき、合計値＝積み木の数になるようにしておく。
ある積み木について、その積み木より大きい積み木の数を求めるのは、その積み木の部分を-1すれば、合計値で得られる。
積み木iについて左右どちらかに動かすかは、BITからi番目を-1してから、[0,i)と[i+1,N)=[0,N)-[0,i+1)それぞれの合計値で小さい方で求められる。


また、N<=10^5だと、交換回数がintに収まらない可能性があるので、64bit整数を使う。

反省

http://d.hatena.ne.jp/phyllo_algo/20140601/1401597356
gcj2014round2のUp and DownのNが大きい場合。
「たのしい家庭菜園」は高さが同じ場合があるが、これの解説でBITを使うことは見てたけど、どう使うかまで考えてなかったので、今回考えてみようとして失敗。
ちゃんと問題を解ききるところまでやらないと身に付かない・・・