意外とややこしい問題。 $N$ ラウンド目の成績によっては、これまでの暫定の最大スコアと最小スコアが変わるかもしれないという点に注意！

問題へのリンク

問題概要

$N$ ラウンドの試験が行われる。各ラウンドの得点は 0 以上 100 以下の整数値である。全ラウンドの最終スコアは、 $N$ 回のラウンドのうち、最大スコアと最小スコアを除外した $N-2$ 回の分の得点の総和で決まる。

最初の $N-1$ 回のラウンドは実施済みで、得点は $A_{1}, A_{2}, \dots, A_{N-1}$ であった。

最終スコアが $X$ 点以上となるような、 $N$ ラウンド目の得点の最小値を求めよ。不可能な場合は -1 と答えよ。

制約

$3 \le N \le 100$

嘘解法

一見すると、次の解法で解けるように思えるかもしれない。

$A_{1}, A_{2}, \dots, A_{N-1}$ の最大値を $M$ 、最小値を $m$ とする
$S = A_{1} + A_{2} + \dots + A_{N-1} - M - m$ として、 $X - S$ を答えればよい

しかしこの解法には穴がある。それは、最後の $N$ ラウンド目のスコアによっては、最大値 $M$ や最小値 $m$ が入れ替わるかもしれないのだ。

解法 (1)：全探索

状況がややこしい。こういうときは「全探索で解けないか」を考えることが有効になる。今回であれば、 $N$ ラウンド目の得点は 0 以上 100 以下の整数値しかとらないことに目をつけよう。つまり、次の問題がとければ良いのだ。

$N$ ラウンド目の得点が $x$ であるとき、最終スコアが $X$ 以上になるかどうかを判定せよ

この答えが Yes となる最小の $x$ を求めればよい。

判定問題は $N$ 個のスコアの最大値と最小値を引いた値を実際に求めて $x$ と比較して解ける。

コード

#include <bits/stdc++.h>
using namespace std;

// 最終ラウンドが x 点のときの最終スコアを求める関数
int score(int x, vector<int> A) {
    // 最大値と最小値と総和
    int maxv = x, minv = x, sum = x;
    for (int a : A) {
        maxv = max(maxv, a);
        minv = min(minv, a);
        sum += a;
    }
    return sum - maxv - minv;
}

int main() {
    // 入力
    int N, X;
    cin >> N >> X;
    vector<int> A(N-1);
    for (int i = 0; i < N-1; ++i) cin >> A[i];
    
    // 全探索
    int res = -1;
    for (int x = 0; x <= 100; ++x) {
        // 最終スコアが X 以上ならそれを答えにして break する
        if (score(x, A) >= X) {
            res = x;
            break;
        }
    }
    cout << res << endl;
}

解法 (2)：最小値と最大値がどうなるかを考察

もう一つの解法として、 $N$ ラウンド目の得点によって、最大値と最小値がどのように変化するかを考察する方法もある。まず、 $N-1$ ラウンドまでの最小値を $a$ 、最大値を $b$ 、総和を $s$ としよう。

まず、最小値 $a$ が更新される場合を考えよう。その場合は $N$ ラウンド目は 0 点としてしまってよい。どのみち、最終スコアからはカットされるからだ。つまり、0 点でも OK なら、答えは 0 点でよい。逆に、0 点でダメだったら、最小値は更新されないものと考えてよいことがわかる。

次に、最大値 $b$ が更新される場合を考えよう。その場合は $N$ ラウンド目の得点は $b$ としてよい。どのみち、それ以上の得点をとってもカットされるからだ。つまり、b 点でダメだったら、不可能なので -1 を出力すればよい。

それ以外の場合 ( $b$ 点で OK の場合) は、最小値と最大値は変わらないものと考えてよい。つまり、 $N$ ラウンド目で獲得しなければならない得点は $x = X - (s - a - b)$ 以上となる。 $a \le x \le b$ であれば ( $b$ 点で OK であった時点で、これは保証される)、これが答えとなる。

以上をまとめると

$0$ 点で OK なら、0 が答え
$b$ 点でダメなら、-1 が答え
それ以外は、 $x = X - (s - a - b)$ として、 $x$ が答え

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 入力
    int N, X;
    cin >> N >> X;
    vector<int> A(N-1);
    for (int i = 0; i < N-1; ++i) cin >> A[i];
    
    // 最小値、最大値、総和
    int a = 101, b = -1, s = 0;
    for (int i = 0; i < N-1; ++i) {
        a = min(a, A[i]);
        b = max(b, A[i]);
        s += A[i];
    }
    
    if (s - b >= X) {
        // 0 点時の得点 (s - b) が X 以上なら 0 が答え
        cout << 0 << endl;
    } else if (s - a < X) {
        // b 点時の得点 (s - a) が X 未満なら -1 が答え
        cout << -1 << endl;
    } else {
        cout << X - (s - a - b) << endl;
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 321 B - Cutoff (灰色, 200 点)

問題概要

制約

嘘解法

解法 (1)：全探索

コード

解法 (2)：最小値と最大値がどうなるかを考察

コード