概要

文字列 \(S\) に含まれる数字のうち、最も大きいものを求めます。\(9\) から \(0\) の順に調べ、最初に見つかった数字を出力します。

考察

負荷レベルは \(0\) から \(9\) までの \(10\) 種類しかありません。そのため、大きい数字から順に「その数字が \(S\) に含まれているか」を確認すれば、最大値を求められます。

例えば、\(S =\) 30752 の場合、9 と 8 は含まれていませんが、7 は含まれています。これより大きい数字がないことはすでに確認済みなので、答えは \(7\) です。

なお、この問題では、すべての文字を順に見て最大値を更新する素朴な方法でも十分に間に合います。特別な高速化は必要ありません。提示コードでは、数字の種類が少ないことを利用して、大きい順に探す方法を採用しています。

アルゴリズム

1. \(N\) と文字列 \(S\) を読み込みます。
2. \(d\) を \(9, 8, \ldots, 0\) の順に調べます。
3. \(d\) に対応する数字の文字が \(S\) に含まれていれば、\(d\) を出力して終了します。

最初に見つかった \(d\) は \(S\) に含まれており、\(d\) より大きい数字はすべて含まれていません。したがって、\(d\) が最大の負荷レベルです。

また、\(S\) の長さは \(1\) 以上で、数字のみからなるため、必ずいずれかの数字が見つかります。

計算量

• 時間計算量: \(O(N)\)
  文字列の検索は \(1\) 回あたり \(O(N)\) で、最大 \(10\) 回行います。\(10\) は定数なので、全体で \(O(N)\) です。
• 空間計算量: \(O(N)\)
  入力文字列 \(S\) の保存に必要です。それ以外の追加領域は \(O(1)\) です。

実装のポイント

• 提示コードは C++ です。char('0' + d) によって、整数 \(d\) を対応する数字の文字に変換しています。例えば、\(d = 7\) なら文字 '7' になります。

• s.find(...) は、指定した文字が見つかればその位置を、見つからなければ std::string::npos を返します。

• 数字が見つかったら、出力後に return 0; で終了します。大きい順に調べているため、それより小さい数字を確認する必要はありません。

• 0 も検索対象に含めることで、\(S\) がすべて 0 の場合にも正しく答えられます。

  ソースコード

// 問題文から独立に実装: 9 から下へ、S に含まれる最初の数字を探す
#include <iostream>
#include <string>
int main() {
    int n; std::string s; std::cin >> n >> s;
    for (int d = 9; d >= 0; --d) {
        if (s.find(char('0' + d)) != std::string::npos) { std::cout << d << std::endl; return 0; }
    }
}

---

この解説は gpt-6-astra-medium によって生成されました。