はじめに (ネタバレ無し)

こんにちは
ひぽたふです。

解きながらの考察、実際の解法をまとめておこうかなと思います。

今回解いた問題はこれです。

No.966 引き算をして門松列（その１） - yukicoder

星2つの問題です。実装でちょっと沼りかけた問題でした。

以下はネタバレがあるので見る際は注意してください。

はじめに (ネタバレ無し)
解きながらの考察 (ネタバレ　方針まで)
- 問題概要
- 考察
あとがき + 解法(ネタバレ全開)
ソースコード
今回の便利

解きながらの考察 (ネタバレ　方針まで)

ここからはネタバレがあります。問題を解いている際に考えていたことをまとめておこうかなと思います。

問題概要

A, B, Cの整数が与えられる。
いずれかを1減らす操作を何回か行って、AかCが2番目に小さくなるようにしたい。
最小で何回行えば良いか。

全部の値が異なることと、0になってはいけないという制約付き。

考察

2番目に大きい数値がAかCって事は、Bは一番大きいか、一番小さいか・・・かな？
A, B, Cの長さを調節してそうなるようにすると。
求めるのは最小の操作回数。

Bを一番大きくするには、A, CをB未満になるように削る必要がありそう。
Bを一番小さくするには、Bがmin(A, C)未満になるように削る必要がありそう。

他の操作は・・・なさそうかな。
どっちの操作が最小コストか比べれば答えが出そう！
1クエリにつきO(1)、この方針で実装を始めようかな。

細かい条件を精査して、AC！

あとがき + 解法(ネタバレ全開)

実装中に、全ての整数が異なる必要があるという事に気がついて、思ってた以上に実装に苦戦しました。

基本の方針はそのままで、A, C大きさ順序も考慮しました。

B > A > C, B > C > A
A > C > B, C > A > B

この四つのパターンでコスト計算して、その中から最小を選ぶという感じです。

ソースコード

ll cost(ll minv, ll maxv1, ll maxv2) {
  ll maxv2_cost = max((maxv2 - maxv1) + 1, 0ll);
  maxv2 -= maxv2_cost;
  ll minv_cost = max((minv - maxv2) + 1, 0ll);
  minv -= minv_cost;
  if (maxv2 <= 0 || minv <= 0) {
    return LLONG_MAX;
  }
  return maxv2_cost + minv_cost;
}

int main() {
  int input(n);
  REP(i, n) {
    ll input(a, b, c);
    // bが一番大きい時
    ll pattern1 = min(cost(a, b, c), cost(c, b, a));

    // bが一番小さい時
    ll pattern2 = min(cost(b, c, a), cost(b, a, c));

    ll mincost = min(pattern1, pattern2);
    if (mincost == LLONG_MAX) {
      print(-1);
    } else {
      print(mincost);
    }
  }
}