Overview

Determine whether the snowfall on each day is strictly greater than the snowfall on all previous days. Output a string where days setting a new record are represented by o, and other days by x.

Analysis

The condition “strictly greater than all previous days” can be rephrased as strictly greater than the maximum snowfall of all previous days.

Therefore, for day \(2\) and onwards, we can determine the result by checking the following condition:

\(A_i > \max(A_1, A_2, \ldots, A_{i-1})\)

For day \(1\), there are no past days to compare with, so it is always o as specified by the problem statement.

For example, if the snowfall amounts are \([3, 3, 2, 5, 4]\), the process is as follows:

Day	Snowfall	Previous Maximum	Result
\(1\)	\(3\)	None	o
\(2\)	\(3\)	\(3\)	x
\(3\)	\(2\)	\(3\)	x
\(4\)	\(5\)	\(3\)	o
\(5\)	\(4\)	\(5\)	x

The output is oxxox. Note that tying the maximum value does not count as a new record.

A naive approach that recalculates the maximum of previous days each time takes \(O(N^2)\) time in total. However, since \(N \leq 100\) in this problem, this approach is well within the time limit, and the provided code uses this method.

Note that comparing only with the previous day will lead to a wrong answer by missing records from earlier days. You must always find the maximum over all preceding days.

Algorithm

1. Read the number of days \(N\) and the array of snowfall amounts a.
2. Prepare an empty list res to store the characters of the answer.
3. Iterate through index \(i\) from \(0\) to \(N-1\):
   • If \(i=0\), append o since it is the first day.
   • Otherwise, find the previous maximum using max(a[:i]).
     • If a[i] is strictly greater than that maximum, append o.
     • Otherwise, append x.
4. Concatenate the characters with "".join(res) and output the result.

Since each day is evaluated according to the definition of a new record and appended in chronological order, the desired string is obtained.

Complexity

• Time Complexity: \(O(N^2)\)
  • When processing index \(i\), creating a[:i] and computing the maximum each take \(O(i)\) time. In total, this requires \(O(1+2+\cdots+(N-1))=O(N^2)\) time.
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used for the input array, the answer list, and temporary arrays created by slicing.

Implementation Notes

• Use > for comparison. If >= is used, days with snowfall equal to the past maximum would incorrectly be treated as new records.

• a[:i] consists of elements from index \(0\) to \(i-1\). It does not include the current day’s a[i].

• In Python, or short-circuits: if the left-hand side is true, the right-hand side is not evaluated. Therefore, writing i == 0 or a[i] > max(a[:i]) avoids calling max on an empty list on the first day.

• Using "".join(res) constructs a string of length \(N\) without extra spaces.

  Source Code

# 問題文から独立に実装: それ以前の最大より大きいか
n = int(input())
a = list(map(int, input().split()))
res = []
for i in range(n):
    res.append('o' if i == 0 or a[i] > max(a[:i]) else 'x')
print("".join(res))

---

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