[ABC004] D - マーブル

[Q] https://atcoder.jp/contests/abc004/tasks/abc004_4

考察
1. Rは、連続的にまとまって配置されるだろう。GもBもそう。
2. なので、Rの開始地点さえ決めればいい。GとBもそう。
3. ありうる開始地点を全探索する。たとえば、Rは-450~-50 くらいから始まりえそう。
400*400*400 = 10000 * 6400 なら間に合う。

ありうる開始地点を考える。極端な例を見積もってみる。

1. 300 1 1
R: -250 ~ 49
G: 50
B: 100

2. 1 300 1
R: -151
G: -150 ~ 149
B: 150

3. 1 1 300
R: -100
G: -51
B: -50 ~ 249

4. 300 300 1 // -50を中心にわけあう
R: -350 ~ -51
G: -50 ~ 249
B: 250

5. 1 300 300 // 50を中心にわけあう
R: -251
G: -250 ~ 49
B: 50 ~ 350

6. 300 300 300 // 0が中心
R: -450 ~ -151
G: -150 ~ 149
B: 150 ~ 450

以上から、
minR, maxR = -450, -151
minG, maxG = -250, 51
minB, maxB = -50, 250

多分幅300+両端の302で探索すれば十分だけど、余裕をもって、
-500 ~ R ~ -100
-300 ~ G ~ 100
-100 ~ B ~ 300
で開始地点を全探索すればよさそう。

Q. 開始地点を決めた場合のスコア計算は？
A. O(1)でできるはず。3パターンが考えられる。
(a) 箱よりマイナスにある場合
(b) 箱をまたぐ場合
(c) 箱よりプラスにある場合

Gを考える。
(a) -5,-4,-3の場合。
5+4+3 = (5*3)*3/2 // (初項 + 末項) * 項数 / 2

(b) -2, -1, 0, 1の場合。
マイナス部分は、
2 + 1 + 0 = 2*(2+1)/2
プラス部分は、
0 + 1 = 1*(1+1)/2

(c) 3,4,5 の場合。(a)と同じ。

実装

ll dist_sum(ll s, ll g, ll base) {
 ll ret = 0;
 ll ds = abs(base - s);
 ll dg = abs(base - g);
 ll n = g - s + 1;
 if (s <= base && g <= base) {
   ret += (ds + dg) * n / 2;
 } else if (s <= base && g >= base) {
   ret += ds * (ds + 1) / 2;
   ret += dg * (dg + 1) / 2;
 } else {
   ret += (ds + dg) * n / 2;
 }
 return ret;
}

int main() {
 cincout();
 ll R, G, B;
 cin >> R >> G >> B;
 ll ans = oo;
 for (ll r = -500; r <= -100; ++r) {
   for (ll g = max(r + R, -300LL); g <= 100; ++g) {
     for (ll b = max(g + G, -100LL); b <= 300; ++b) {
       ll sr = dist_sum(r, r + R - 1, -100);
       ll sg = dist_sum(g, g + G - 1, 0);
       ll sb = dist_sum(b, b + B - 1, 100);
       chmin(ans, sr + sg + sb);
     }
   }
 }
 cout << ans << endl;
}

https://atcoder.jp/contests/abc004/submissions/30555168