はまやんはまやんはまやん

hamayanhamayan's blog

引き算をして門松列(その1) [yukicoder 966]

https://yukicoder.me/problems/no/966

解説

https://yukicoder.me/submissions/417566

3種類の操作があるが、3種類の操作を1つずつ行う操作では、全体の大小関係が変化しないので意味がない。
よって、操作を行う整数の対象は2つ以下である。
max,mid,minを決めてしまえば、midとminを減らすよう操作すればいい。
maxは操作する必要はない。
midはmax-1を目指せばいいし、minはmid-1を目指せばいい。
あとは、Bがmaxかminになる場合だけ考える。

若干方針ガチャな問題。
最適方針を熟考するのが大切。
(自分は根性場合分けを考えて破滅した)

int A[3];
//---------------------------------------------------------------------------------------------------
void solve() {
    rep(i, 0, 3) cin >> A[i];

    int ans = inf;

    vector<int> ord;
    rep(i, 0, 3) ord.push_back(i);
    do {
        if (ord[1] == 1) continue;
        int pre = A[ord[0]];
        int tot = 0;
        rep(i, 1, 3) {
            int nxt = min(A[ord[i]], pre - 1);
            tot += A[ord[i]] - nxt;
            pre = nxt;
        }
        if (0 < pre) chmin(ans, tot);
    } while (next_permutation(all(ord)));

    if (ans == inf) ans = -1;
    printf("%d\n", ans);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}