概要

各日の積雪量を、それより前のすべての日の積雪量と比較します。過去のどの日よりも積雪量が大きければ o、そうでなければ x を出力します。

考察

ある日が新記録の日になるためには、それ以前に、その日以上の積雪量の日が一度もないことが必要です。

つまり、\(i\) 日目について、\(j < i\) を満たす日の中に \(A_j \geq A_i\) となる日があれば、新記録ではありません。同じ積雪量の日がある場合も、新記録にはならないことに注意してください。

各日について過去のすべての日を調べる素朴な方法では、全体の比較回数は

\(\displaystyle 0+1+\cdots+(N-1)=\frac{N(N-1)}{2}\)

となります。今回は \(N \leq 100\) なので、最大でも \(4950\) 回の比較で済み、十分間に合います。そのため、この方法をそのまま実装できます。

なお、前日だけと比較すると誤答になります。例えば積雪量が \(5, 2, 4\) の場合、\(3\) 日目は前日より多いものの、\(1\) 日目の \(5\) を超えていないため、新記録ではありません。

アルゴリズム

1. 積雪量を配列 a に読み込み、答えを格納する空文字列 s を用意します。
2. 各日を先頭から順に処理します。
   • 新記録かどうかを表す変数 record を true にします。
   • その日より前のすべての日を調べます。
   • 過去にその日以上の積雪量の日があれば、record を false にします。
   • record が true なら o、false なら x を s に追加します。
3. 完成した文字列 s を出力します。

例えば、積雪量が \(3, 5, 5, 2, 7\) の場合は次のようになります。

日	積雪量	判定	理由
\(1\)	\(3\)	o	最初の日は必ず新記録
\(2\)	\(5\)	o	過去のすべての日より多い
\(3\)	\(5\)	x	\(2\) 日目と同じ積雪量
\(4\)	\(2\)	x	過去にこれ以上の積雪量の日がある
\(5\)	\(7\)	o	過去のすべての日より多い

したがって、出力は ooxxo です。

この手順では、新記録でない原因となる過去の日があれば必ず検出できます。一方、そのような日がなければ過去のすべての日より積雪量が大きいため、正しく新記録と判定できます。

計算量

• 時間計算量: \(O(N^2)\)
• 空間計算量: \(O(N)\)

各日について過去の日を調べるため、時間計算量は \(O(N^2)\) です。配列 a と答えの文字列 s に、それぞれ \(O(N)\) の領域を使います。

実装のポイント

• コードでは添字を \(0\) から数えるため、a[i] より前の日は a[0] から a[i - 1] です。内側のループは j < i とします。

• 同じ積雪量も新記録ではないので、判定条件は a[j] >= a[i] です。

• record は各日の処理の最初に true に戻します。一度 false になったら、その日の処理中に true へ戻してはいけません。

• 最初の日は内側のループが一度も実行されず、record が true のままになります。そのため、特別な場合分けをしなくても o が追加されます。

  ソースコード

// 問題文から独立に実装: 各日について前の全日と比較
#include <iostream>
#include <string>
#include <vector>
int main() {
    int n; std::cin >> n;
    std::vector<int> a(n);
    for (int& x : a) std::cin >> x;
    std::string s;
    for (int i = 0; i < n; ++i) {
        bool record = true;
        for (int j = 0; j < i; ++j) if (a[j] >= a[i]) record = false;
        s += record ? 'o' : 'x';
    }
    std::cout << s << std::endl;
}

---

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