YukicoderContest233 E問題P3 「引き算をして門松列（その３）」
問題概要
制約
$ T\leq10^4
解法・お気持ち
この問題では
$ A, Bを$ Xで減らす
$ B, Cを$ Yで減らす
$ A, Cを$ Zで減らす
を行う。
こういう$ N個のうち$ N-1個操作を行うものは
よって、全体から$ 1を引いて、減らさない一箇所を$ 1足す操作に言い換えればいい。
最後に引いた回数だけ全体を引けばいいので、結局は
$ A, B, Cに$ +1することを繰り返して門松を作ればいい。 https://gyazo.com/987305099db806f351e81cced654caaa
最後の状態としての候補はそれぞれ
$ A, B, Cからたかだか$ 0, 1, 2を引いたものになる。
なぜなら、$ 3つすべての門松をマイナスすると意味がない。
よって、どれかは固定され、その時最大$ 2だけ差がつけばいいからである。
よって、最後にまとめて、操作した回数だけ全体を引くことを考えるとすれば
$ +1をうまく行って門松にし、その狙う値は$ A, B, Cに$ 0, 1, 2を足したものになる。
計算量
$ O(T)
新たな学び
最終状態を考えると候補はたかだか２７通り
反省点
もっかい解く
コード
code: cpp
constexpr LL INF = 1e18 + 1e6;
bool isKadomatu(vector<LL> abc) {
bool good = true;
for (int i = 0; i < 3; i++) if (abci <= 0) good = false; if (abc0 == abc1 or abc1 == abc2 or abc0 == abc2) good = false; if ((abc0 < abc1 and abc1 < abc2) or (abc0 > abc1 and abc1 > abc2)) good = false; return good;
}
int main() {
int T;
cin >> T;
while (T--) {
vector<LL> ABC(3), XYZ(3);
cin >> ABC >> XYZ;
vector<int> p(3);
iota(p.begin(), p.end(), 0);
LL ans = INF;
do {
LL cost = 0;
vector<pair<int, int>> q(3);
for (int i = 0; i < 3; i++) qi = make_pair(pi, i); sort(q.begin(), q.end());
vector<LL> abc = ABC;
for (int i = 1; i < 3; i++) {
if (abc[qi - 1.second] <= abc[qi.second]) { cost += (abc[qi.second] - abc[qi - 1.second] + 1) * XYZ[qi.second]; abc[qi.second] = abc[qi - 1.second] - 1; }
}
if (isKadomatu(abc)) chmin(ans, cost);
} while (next_permutation(p.begin(), p.end()));
if(ans != INF) cout << ans << endl;
else cout << -1 << endl;
}
}