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

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

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

AtCoder AtCoder100点 ABC-A 灰色diff for文 数列 最大値や最小値に着目する 最小回数・最小個数を求める for文:最大値・最小値・総和 配列 易しい配列の問題 現実世界の題材を扱った問題 そのまま覚えたい易しい教育的典型問題 単独トップを目指す問題 全探索:考えられる整数値を全探索 最適化問題

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

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

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

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

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

面倒な解法

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

  • P_{0} \lt M のときは、答えは M + 1 - P_{0}
  • P_{0} = M のときは......
    • 他にプログラミング力が 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;
}