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

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

2023-08-05

AtCoder ABC 313 A - To Be Saikyo (6Q, 灰色, 100 点)

トップタイがある場合に注意！

問題へのリンク

問題概要 (0 始まりに表現改)

$N$ 人の人 $0, 1, \dots, N-1$ がいる。人 $i$ のプログラミング力は $P_{i}$ である。

人 $0$ は必要に応じてプログラミング力を鍛えることで、 $N$ 人の中で単独トップになろうとしている。

そのためにプログラミング力をいくつ高めればよいかを求めよ。

面倒な解法

$N$ 人のプログラミング力の最大値を $M$ として処理しようとすると、場合分けが少し面倒になる。

$P_{0} \lt M$ のときは、答えは $M + 1 - P_{0}$
のときは......
- 他にプログラミング力が $M$ の人がいなければ、答えは $0$
- いれば、答えは $1$

この解法だと「人 $0$ が最強であるときに、人 $0$ 以外の $N-1$ の中に同じく最強の人がいるかどうか」を判定する必要が生じてしまう。これは面倒だ。

楽な解法

そこで、人 $0$ を除いた $N-1$ のプログラミング力の最大値を $M$ とする。そうすれば、

$P_{0} \le M$ のときは、答えは $M + 1 - P_{0}$
$P_{0} \gt M$ のときは、答えは $0$

というように、シンプルに解ける！

コード

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

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    
    // 人 0 を除外した最大値
    int maxv = -1;
    for (int i = 1; i < N; ++i) maxv = max(maxv, A[i]);

    cout << (A[0] <= maxv ? maxv + 1 - A[0] : 0) << endl;
}