Codeforces Round #353 (Div. 2) C. Money Transfers

http://codeforces.com/contest/675/problem/C

問題

数列 an が与えられる。i 番目にある値を i-1,i+1 のどちらかに流すという操作ができる。

すべての要素を 0 にするのに必要な最小の操作回数を求めよ。

  • 2≦n≦105
  • 1≦a[i]≦109

解法

右だけに移動させるように限定しても、最小ステップ数は変わらないはず。

となるとスタート地点を一つ決めて、0になるまで右に流し続けるという貪欲をやれば答えが求まる。

簡単な例をひとつ示した。矢印の終着点の要素は移動させなくてもいいので、n-(矢印の本数)が必要な移動回数になる。

f:id:pekempey:20160517055646p:plain

累積和の世界で見ると、矢印の終着点はからなず同じ値になる。なぜなら、S[i+n]=S[i] なら S[i..i+n-1]=0 になるからだ。

つまり累積和の中で一番多く現れる値の個数を n から引いてあげれば、それが答えになる。

スタート地点の選び方は n 通りあるので、愚直にやると O(n2)。しかし、この方法であれば map を用いて O(n log n) で解ける。

Codeforces Round #353 (Div. 2) C. Money Transfers

本番は i 番目からどこまで足せば 0 になるかを前計算しておいて、流す作業を高速化して通した。累積和の頻度を見るの頭いいな。