解法

「\(i\) 日目が新記録の日である」とは、\(A_i\) が \(A_1, A_2, \ldots, A_{i-1}\) のすべてより大きいこと、すなわち \(A_i > \max(A_1, \ldots, A_{i-1})\) であることを意味します。

そこで、\(i\) 日目までの積雪量の最大値を変数 mx に保持しながら、日を順番に見ていきます。\(A_i > \mathrm{mx}\) ならば \(i\) 日目は新記録の日なので o を出力し、mx を \(A_i\) に更新します。そうでなければ x を出力します。

初期値として \(\mathrm{mx} = -1\) とすれば、\(A_1 \geq 0 > \mathrm{mx}\) となるため、\(1\) 日目は必ず新記録の日となり、問題文の条件を自然に満たします。

疑似コード

mx = -1
for i = 1..N:
    read A_i
    if A_i > mx:
        output 'o'; mx = A_i
    else:
        output 'x'

正しさの証明

不変条件: \(i\) 日目を処理する直前の時点で、\(\mathrm{mx} = \max(A_1, \ldots, A_{i-1})\) が成り立つ(ただし \(i = 1\) のときは \(\mathrm{mx} = -1\) で、空集合の最大値として振る舞う)。

• 初期状態: \(i = 1\) のとき \(\mathrm{mx} = -1\)。\(A_1 \geq 0\) より \(A_1 > \mathrm{mx}\) なので、\(1\) 日目は必ず o となり、条件「\(1\) 日目は必ず新記録の日」を満たす。
• 維持: \(i\) 日目で \(A_i > \mathrm{mx}\) なら o を出力して \(\mathrm{mx} \leftarrow A_i\) とする。不変条件より \(\mathrm{mx}\) は \(A_1, \ldots, A_{i-1}\) の最大値なので、\(A_i > \mathrm{mx}\) はまさに「それより前のすべての日の積雪量より大きい」という条件と同値であり、o の判定は正しい。更新後の \(\mathrm{mx}\) は \(\max(A_1, \ldots, A_i)\) に等しい。\(A_i \leq \mathrm{mx}\) のときは x を出力し、\(\mathrm{mx}\) は変わらず \(\max(A_1, \ldots, A_i) = \mathrm{mx}\) のままなので不変条件は保たれる。

よって全 \(i\) について出力される文字が正しく、得られる文字列は所望の答えである。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: 入力を一つずつ読み込んで処理すれば補助空間 \(O(1)\)(出力文字列を除く)。Python 実装では入力全体を一度に読むため \(O(N)\) だが、\(N \leq 100\) なので問題ない。

同点の扱い

条件は「それより前のすべての日の積雪量より大きい」なので、過去の最大値と等しい場合は新記録ではなく x となる。したがって比較は厳密な不等号 > を用いる。