hotpepsiの練習帳

SRM 683

00:54

https://competitiveprogramming.info/topcoder/srm/round/16653/div/1

Div1 Easy (250) MoveStones

問題

• 何個かの石からなる山がN個あり、円環状に並んでいる
• 各山の個数は配列a[0],a[1],...a[N-1]で与えられる
• 1ターンに、1個の石を隣に移動できる
• 山の個数をb[0],b[1],...b[N-1]にするための最小ターン数を求める

方針

• 適当に書く
• Challenge Succeeded
• (終了後)
• 最適解では、お互いにやりとりしない山が発生するので、各山がその位置であると仮定して全山で試せばよいらしい
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_683/MoveStones.cpp

結果

x-- 0pt rating 1490 -> 1442 (-48)

部屋一位の人(Blue.Maryさん)の解法は、差分の累積和v[i+1] = v[i] + a[i] - b[i]を求めておいて、その中央の値m = v[N÷2]とすると、その差の累積和Σ|v[i] - m|が答えらしい。

ひとつずつ移動する系はSRM 645 Div2 MediumとかSRM 646 Div1 Easy TheConsecutiveIntegersDivOneとか、(平均ではなく)中央値に集めるのが最適になることが多いようだ。

http://togetter.com/li/944461