[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;
}