概要

最初に間違えるまでの問題には o、最初に間違えた問題とそれ以降の問題には x を出力します。最初の \(0\) の位置を調べれば、答えをまとめて作れます。

考察

得点がもらえるのは、最初の問題から一度も間違えずに正解している間だけです。

そのため、各 \(A_i\) を単純に「\(1\) なら o、\(0\) なら x」と置き換える方法では正しくありません。一度間違えた後は、正解しても x にする必要があります。

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

1 1 0 1 0

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

ooxxx

ここで、最初の \(0\) より前はすべて \(1\) なので、最初の \(0\) の位置だけ分かれば十分です。\(0\) が一つもない場合は、すべての問題で得点がもらえます。

なお、先頭から順に「すでに間違えたか」を管理する方法でも十分高速に解けます。この問題では、処理の高速化よりも、最初の間違い以降の扱いに注意することが重要です。

アルゴリズム

1. \(N\) と配列 \(A\) を読み込みます。
2. 最初の \(0\) の \(0\) 始まりの添字を first_miss とします。
   • \(0\) が存在する場合は、a.index(0) で求めます。
   • \(0\) が存在しない場合は、first_miss = n とします。
3. 次の文字列を連結して出力します。
   • o を first_miss 個並べた文字列
   • x を \(N - \text{first\_miss}\) 個並べた文字列

最初の \(0\) の添字は、その前にある正解の個数と一致します。よって、この方法で得点がもらえた問題と、それ以降の問題を正しく表せます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

\(0\) の存在確認、最初の位置の探索、出力文字列の生成はいずれも最大 \(O(N)\) です。また、入力配列と出力文字列に \(O(N)\) の領域を使います。

実装のポイント

• Python の a.index(0) は、最初の \(0\) の添字を返します。ただし、\(0\) が存在しないとエラーになるため、先に 0 in a で確認します。

• 文字列と整数の掛け算で、同じ文字を指定回数並べられます。例えば、'o' * 3 は ooo です。

• 最初の問題で間違えた場合は first_miss = 0 となり、すべて x になります。全問正解の場合は first_miss = n となり、すべて o になります。

  ソースコード

# 問題文から独立に実装: 最初の 0 の位置までが o
n = int(input())
a = list(map(int, input().split()))
first_miss = a.index(0) if 0 in a else n
print('o' * first_miss + 'x' * (n - first_miss))

---

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