Overview

Compare each day’s snowfall with the snowfall of all preceding days. If the snowfall is strictly greater than that of every previous day, output o; otherwise, output x.

Analysis

For a certain day to set a new record, there must not be any prior day with an equal or greater amount of snowfall.

In other words, for the \(i\)-th day, if there exists a day \(j < i\) such that \(A_j \geq A_i\), it is not a new record. Note that if there is a day with the same amount of snowfall, it does not count as a new record.

Using the naive approach of checking all previous days for each day, the total number of comparisons is:

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

Since \(N \leq 100\) here, there are at most \(4950\) comparisons, which is well within the time limit. Therefore, this approach can be implemented directly.

Note that comparing only with the immediately preceding day will result in a wrong answer. For example, if the snowfall amounts are \(5, 2, 4\), the \(3\)rd day has more snow than the previous day, but it does not exceed the \(5\) from the \(1\)st day, so it is not a new record.

Algorithm

1. Read the snowfall amounts into an array a, and initialize an empty string s to store the answer.
2. Process each day in order from the beginning:
   • Initialize a variable record, representing whether it is a new record, to true.
   • Check all days before that day.
   • If there is a previous day with an equal or greater amount of snowfall, set record to false.
   • If record is true, append o to s; if false, append x to s.
3. Output the resulting string s.

For example, when the snowfall amounts are \(3, 5, 5, 2, 7\), the process is as follows:

Day	Snowfall	Result	Reason
\(1\)	\(3\)	o	The first day is always a new record
\(2\)	\(5\)	o	Greater than all previous days
\(3\)	\(5\)	x	Same snowfall as day \(2\)
\(4\)	\(2\)	x	A previous day had an equal or greater snowfall
\(5\)	\(7\)	o	Greater than all previous days

Therefore, the output is ooxxo.

With this procedure, any previous day that prevents a new record will definitely be detected. On the other hand, if no such day exists, the snowfall is strictly greater than all previous days, so it is correctly determined to be a new record.

Complexity

• Time Complexity: \(O(N^2)\)
• Space Complexity: \(O(N)\)

Since we check the previous days for each day, the time complexity is \(O(N^2)\). We use \(O(N)\) space each for the array a and the answer string s.

Implementation Notes

• Since indices are \(0\)-indexed in code, the days prior to a[i] are a[0] through a[i - 1]. The inner loop should run for j < i.

• Since having the same snowfall does not count as a new record, the condition to check is a[j] >= a[i].

• Reset record to true at the beginning of processing each day. Once it becomes false, it must not be set back to true during the processing of that day.

• For the first day, the inner loop does not execute at all, leaving record as true. Thus, o will be appended without requiring any special case handling.

  Source Code

// 問題文から独立に実装: 各日について前の全日と比較
#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;
}

---

This editorial was generated by gpt-6-astra-medium.