概要

各日の積雪量が、それ以前のすべての日の積雪量より大きいかを判定します。新記録の日には o、それ以外の日には x を並べて出力します。

考察

「それ以前のすべての日より大きい」という条件は、それ以前の積雪量の最大値より大きいと言い換えられます。

したがって、\(2\) 日目以降については、次の条件を調べれば判定できます。

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

\(1\) 日目には比較する過去の日がないため、問題文の指定どおり必ず o とします。

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

日	積雪量	それ以前の最大値	判定
\(1\)	\(3\)	なし	o
\(2\)	\(3\)	\(3\)	x
\(3\)	\(2\)	\(3\)	x
\(4\)	\(5\)	\(3\)	o
\(5\)	\(4\)	\(5\)	x

出力は oxxox です。最大値と同じ値では新記録にならないことに注意してください。

毎回、それ以前の最大値を求め直す素朴な方法では、全体で \(O(N^2)\) の時間がかかります。しかし、この問題では \(N \leq 100\) なので十分に間に合い、提示されたコードもこの方法を使っています。

なお、前日だけと比較すると、それより前の日の記録を見落として誤答になります。必ず、それ以前のすべての日を対象に最大値を求めます。

アルゴリズム

1. 日数 \(N\) と積雪量の配列 a を読み込みます。
2. 答えの文字を格納する空のリスト res を用意します。
3. 添字 \(i\) を \(0\) から \(N-1\) まで順に処理します。
   • \(i=0\) なら、最初の日なので o を追加します。
   • それ以外では、max(a[:i]) でそれ以前の最大値を求めます。
     • a[i] がその最大値より大きければ o を追加します。
     • そうでなければ x を追加します。
4. "".join(res) で文字を連結し、出力します。

各日について新記録の定義どおりに判定し、その結果を日付順に追加しているので、求める文字列が得られます。

計算量

• 時間計算量: \(O(N^2)\)
  • 添字 \(i\) の処理では、a[:i] の作成と最大値の計算にそれぞれ \(O(i)\) かかります。全体では \(O(1+2+\cdots+(N-1))=O(N^2)\) です。
• 空間計算量: \(O(N)\)
  • 入力配列、答えのリスト、およびスライスによる一時的な配列に \(O(N)\) の領域を使います。

実装のポイント

• 比較には > を使います。 >= にすると、過去の最大値と同じ積雪量の日まで新記録としてしまいます。

• a[:i] は添字 \(0\) から \(i-1\) までの要素です。当日の a[i] は含みません。

• Python の or は、左側が真なら右側を評価しません。そのため、i == 0 or a[i] > max(a[:i]) と書くことで、最初の日に空のリストへ max を使うことを避けられます。

• "".join(res) を使うと、余分な空白を入れずに長さ \(N\) の文字列を作れます。

  ソースコード

# 問題文から独立に実装: それ以前の最大より大きいか
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))

---

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