概要

最初に間違えた問題より前は o、最初に間違えた問題とそれ以降はすべて x にします。「一度でも間違えたか」を管理しながら、結果を先頭から順に調べます。

考察

\(i\) 問目で得点をもらえるのは、\(1\) 問目から \(i\) 問目まですべて正解している場合だけです。

したがって、単に \(A_i = 1\) なら o、\(A_i = 0\) なら x とする方法では正しくありません。一度間違えた後は、正解しても得点をもらえないためです。

例えば、結果が次のような場合を考えます。

1 1 0 1 0

最初の \(2\) 問では得点をもらえますが、\(3\) 問目で間違えるため、それ以降は得点をもらえません。答えは次の文字列になります。

ooxxx

各問題について、それまでの結果を毎回調べ直す方法でも判定できますが、その必要はありません。一度でも間違えると、その後は得点をもらえる状態に戻らないので、状態を表す変数を \(1\) つ持てば十分です。

アルゴリズム

「ここまで一度も間違えていない」ことを表す変数 ok を使います。

1. ok = True とし、答えを保存するリスト res を空にします。
2. 各問題の結果を先頭から順に調べます。
   • 結果が 0 なら、ok = False にします。
   • ok が True なら o、False なら x を res に追加します。
3. res の文字を連結して出力します。

各問題の結果を反映した直後、ok は「最初の問題から現在の問題まですべて正解している場合に限り True」となります。これは得点をもらえる条件そのものなので、各位置に正しい文字を追加できます。

計算量

• 時間計算量: \(O(N)\)
  \(N\) 問の結果をそれぞれ一度ずつ調べ、最後に長さ \(N\) の文字列を作ります。
• 空間計算量: \(O(N)\)
  入力データと、答えの文字を保存するリストを使います。

実装のポイント

• 文字を追加する前に ok を更新します。 間違えた問題そのものも x にする必要があるためです。

• 一度 ok = False になったら、その後に正解しても True に戻しません。

• 提示コードでは、各結果を整数ではなく文字列として保持しているため、v == '0' と比較しています。

• ''.join(res) を使うことで、文字の間に空白を入れずに連結できます。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    a = data[1:1 + n]
    res = []
    ok = True
    for v in a:
        if v == '0':
            ok = False
        res.append('o' if ok else 'x')
    sys.stdout.write(''.join(res) + '\n')

main()

---

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