https://www.codechef.com/DEC17/problems/CHEFUNI
座標(0,0,0)にいる
ここから以下の操作をして最小コストで座標(X,Y,Z)に移動せよ。
- コストAで、x,y,z座標のどれか1つをインクリメントする
- コストBで、x,y,z座標のどれか2つをインクリメントする
- コストCで、x,y,z座標の全てのインクリメントする
解法
基本は貪欲に解く。
「コスト/1座標進める」でコスパが良いものを選択していく。
この貪欲の過程で「今残っている進めるべき座標からBの操作を最大何回行えるか」の関数が必要。
getmaxb(x, y, z) := 座標を(+x,+y,+z)するときにBの操作を最大何回行えるか
x,y,zを小さい順にv[0],v[1],v[2]とする。
v[0]+v[1]≦v[2]となれば、v[0]とv[2],v[1]とv[2]で操作をしていけば最高回数が達成できる。
そうではない場合は、v[0]+v[1]≦v[2]となるまで、Bを三回行い、全て-2していく操作を行う。
これを愚直にやっていると遅いので、何回-2していけばいいかを考えてみよう。
Bを3回行う操作を1回行うと、不等式の左辺は-4, 右辺は-2される。
よって差が2だけ縮まる。
そのため、delta=v[0]+v[1]-v[2]の差を埋めるためにceil(delta/2)回操作を行えば良いと分かる。
後、この操作はfloor(v[0]/2)が限界なので、どちらか小さい方で削る。
削ってv[0]+v[1]≦v[2]となれば最高回数を達成させる。
これだけ操作をしてみて、まだちょっと残っていれば、大きい方からペアで貪欲に消していって消せなくなったら答え。
(i) Aが一番コスパが良い場合（A≦B/2 かつ A≦C/3）
全てAで処理してしまうのが良い
(ii) Bが一番コスパが良い場合（B/2＜A かつ B/2≦C/3）
Cは1回か0回やれば十分であることが分かる。
（Bを3回やればCを2回やったのと同等のことができるため）
なので、Cは0回か1回かどちらも試してみる。
後は、なるべくBで進めたあとに残りをAで進める。
(iii) Cが一番コスパが良く、BよりもAの方がコスパがいい場合（A≦B/2）
なるべくCで進め、残ったやつをAで進める。
(iv) Cが一番コスパが良く、次にBが良く、Aが最も悪い
cを使う回数で三分探索して最小値をあぶり出すが、普通にやると凹関数になってない。
実験してみると、cが偶数のとき、cが奇数のときで分けて見ると凹関数になっている。
（なぜかは分からない）
なので、別々に三分探索してやって、コストが小さい方が答え
template<typename Func> int findMin(int L, int R, Func f) { //[L, R) int lo = L - 1, hi = R - 1; while (lo + 1 != hi) { int mi = (lo + hi) / 2; if (f(mi) <= f(mi + 1)) hi = mi; else lo = mi; } return hi; } typedef long long ll; #define INF 1LL<<60 ll X, Y, Z, A, B, C; //--------------------------------------------------------------------------------------------------- ll getmaxb(ll x, ll y, ll z) { vector<ll> v; v.push_back(x); v.push_back(y); v.push_back(z); sort(v.begin(), v.end()); if (v[0] + v[1] <= v[2]) return v[0] + v[1]; ll dmax = v[0] / 2; ll delta = v[0] + v[1] - v[2]; ll dwant = (delta + 1) / 2; ll d = min(dmax, dwant); ll res = d * 3; v[0] -= d * 2; v[1] -= d * 2; v[2] -= d * 2; if (v[0] + v[1] <= v[2]) { res += v[0] + v[1]; v[2] -= (v[0] + v[1]); v[0] = 0; v[1] = 0; } sort(v.begin(), v.end()); while (0 < v[1]) { res++; v[1]--; v[2]--; sort(v.begin(), v.end()); } return res; } //--------------------------------------------------------------------------------------------------- ll sm; ll d = 0; ll f(ll c) { if (c < 0) return INF; c = c * 2 + d; if (X - c < 0 or Y - c < 0 or Z - c < 0) return INF; ll x = X - c; ll y = Y - c; ll z = Z - c; ll b = getmaxb(x, y, z); return c * C + b * B + (sm - c * 3 - b * 2) * A; } //--------------------------------------------------------------------------------------------------- ll solve() { sm = X + Y + Z; ll mi = min(X, min(Y, Z)); // A is good if (A * 2 <= B and A * 3 <= C) return sm * A; // B is good if (B < A * 2 and B * 3 <= C * 2) { ll ans = INF; // don't use rule C ll b = getmaxb(X, Y, Z); ans = b * B + (sm - b * 2) * A; // use rule C once if (0 < mi) { ll b = getmaxb(X - 1, Y - 1, Z - 1); ans = min(ans, C + b * B + (sm - b * 2 - 3) * A); } return ans; } // C is good // A <= B if (A * 2 <= B) return mi * C + (sm - mi * 3) * A; // B < A ll ans = INF; d = 0; ll gc = findMin(0, mi / 2 + 1, f); ans = min(ans, f(gc)); d = 1; gc = findMin(0, mi / 2 + 1, f); ans = min(ans, f(gc)); return ans; } //--------------------------------------------------------------------------------------------------- void _main() { int T; cin >> T; rep(t, 0, T) { cin >> X >> Y >> Z >> A >> B >> C; ll a = solve(); printf("%lld\n", a); } }
