概要

各日の積雪量が、それまでの積雪量の最大値を超えているかを判定します。新記録なら o、そうでなければ x を順につなげて出力します。

考察

\(i\) 日目が新記録の日になる条件は、\(A_i\) がそれより前のすべての日の積雪量より大きいことです。

素朴には、各日について、それより前の日をすべて調べれば判定できます。この方法の時間計算量は \(O(N^2)\) で、今回の制約では十分間に合います。

ただし、過去の積雪量を毎回すべて調べる必要はありません。それまでの最大値だけを覚えておけば、その値との比較だけで判定できます。

それまでの最大値を mx とすると、次のようになります。

• \(A_i > \mathrm{mx}\) なら新記録なので o とし、mx を \(A_i\) に更新する。
• \(A_i \leq \mathrm{mx}\) なら新記録ではないので x とし、mx は変更しない。

最大値と同じ値では新記録にならない点に注意してください。

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

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

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

アルゴリズム

1. 答えの文字を保存する空のリスト ans を用意する。
2. それまでの最大値 mx を \(-1\) で初期化する。
3. 積雪量を先頭から順に取り出し、その値を v とする。
   • v > mx なら、ans に o を追加し、mx を v に更新する。
   • そうでなければ、ans に x を追加する。
4. ans の文字を連結して出力する。

制約より \(A_i \geq 0\) なので、mx の初期値を \(-1\) にすれば、\(1\) 日目は必ず o になります。

また、各日の処理後には、mx はその日までの最大値になっています。そのため、翌日もそれ以前の最大値と正しく比較でき、すべての日を正しく判定できます。

計算量

• 時間計算量: \(O(N)\)
  各日の判定を \(1\) 回ずつ行い、最後の文字列の連結にも \(O(N)\) かかります。
• 空間計算量: \(O(N)\)
  入力の配列と、答えを保存するリストを使用します。最大値の管理自体に必要な追加領域は \(O(1)\) です。

実装のポイント

• 新記録の条件は v > mx です。v >= mx にすると、過去の最大値と同じ場合も新記録と判定してしまいます。

• mx を \(0\) で初期化すると、\(A_1 = 0\) の場合に \(1\) 日目が x になってしまいます。コードでは、すべての積雪量より小さい \(-1\) を使っています。

• ''.join(ans) を使うと、リストに保存した文字を空白なしで連結できます。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))
    ans = []
    mx = -1  # A_i >= 0, so day 1 is always a new record
    for v in a:
        if v > mx:
            ans.append('o')
            mx = v
        else:
            ans.append('x')
    print(''.join(ans))

main()

---

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