AGC 027 B - Garbage Collector

• 問題

解法

本番中の考察

• 何回原点に戻ってくるかでXの係数が変わるのでこの回数を決めうちして1回O(N)でやったら部分点取れそう
• 部分最適構造( [l,r) 間のごみの最適なとり方が x=l,..,r として [l,x),[x,r) の最適なとり方を各々やってきたうちコスト最小のもの ) ある？

• それがあったら区間DPでO(N²)、RMQで早くしてO(NlogN) とかになるね

• とりあえず実験してみる.
  1回で x_1, x_2, .. ,x_k のごみをとってくるとする.
  比較的明らかに一番最初に x_k まで行って,帰りに全てをとってくるのが最適であることはわかる.
  このコストは 拾って捨てるコストを除くと,
  (行きの分) x_k
  (帰りの分) 2² (x_k - x{k-1} ) + 3² (x{k-1} - x_{k-2} ) + ... + k²(x_2 - x_1) + (k+1)² x_1 となる.

• 部分最適構造はあるか?
  5つのごみを2回で拾ってくるとして,(同じ色のものを同じ回でとってくる)
  (1) x_1 x_2 x_3 x_4 x_5
  (2) x_1 x_2 x_3 x_4 x_5
  のどれが最適か実験してみる.
  (1) = 7x_1 + 5x_2 + 5x_3 + 5x_4 + 5x_5
  (2) = 5x_1 + 5x_2 + 7x_3 + 5x_4 + 5x_5
  x_1 < x_3だから, (1) < (2) となるので, 部分最適構造は成り立たなそうなことがわかる. 多分DPは使えない.
  一方で回数を決めうちした時に, そのごみを何個持った状態で拾うか,というのは
  x_1 x_2 x_3 .. x_5 に対して 回数 m=2 とすると 1 1 2 2 3 を割り振らないといけないことがわかる.
  この時, 大きい数は近いごみに割り振った方が良い(負担が少なくなるので)ことが直感的にわかる(本番中にちゃんとした証明はできなかった)

• 計算
  N=5, m=2とすると,
  行きの分 = x_4 + x_5
  帰りの分
  = 4(x_5 - x_3) + 9(x_3 - x_1) + 16x_1

• 4(x_4 - x_2) + 9x_2
  これは愚直に計算して1つのm当たり O(N) で求められる. よって全体でO(N²)になり部分点が取れる.

また, これを縦に見ていくと和を累積和で計算できることがわかり項数はN/mになるので,
sum_(1<=m<=N) O(N/m) = O(NlogN) となる.

本番中でできなかった部分

x_1 x_2 .. x_k を1回で取ってくるコストは,
1 2 .. k と順番を割り振ることになるので
(行きの分) x_k
(帰りの分) 2² (x_k - x{k-1} ) + 3² (x{k-1} - x{k-2} ) + ... + k²(x_2 - x_1) + (k+1)² x_1 と書いたが,
これはもっと簡潔に書けて, 5x_k + 5x{k-1} + 7x{k-2} + 9x{k-3} + .. + (2k+1)x_1 となる.
( (k'+1)² - k'^2 = 2k'+1 となるので )
これに気づけたら相当早く解けた.

メモ

• 青くなった. やったぜ
• long longでオーバーフローしたので誤差怖かったがdoubleにした.
• そもそもllに入らない答えは出ないと思うので,毎回INF超えないかチェックしてやれば大丈夫そう
• 累積和の計算は場合分けがめんどそうだが,
  rsum := ( [l,r) の和 ) と定義してやって,
  r <= 0 の時 0, l < 0 の時 l = 0, r > N の時 r = Nと定義してやれば簡潔に書けて,凡ミスもしない
  (本番中xとxの累積和を間違ったりして解けなかった(よくやる))

コード