概要

最初に間違えるまでの問題を o、最初に間違えた問題とそれ以降の問題を x として出力します。一度でも間違えたかどうかを記録しながら、順番に処理します。

考察

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

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

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

1 1 0 1 0

最初の \(2\) 問は得点がもらえますが、\(3\) 問目で間違えています。その後の \(4\) 問目は正解でも得点がもらえないので、出力は次のようになります。

ooxxx

ここで必要なのは、過去の結果をすべて覚えることではなく、「これまで一度も間違えていないか」という情報だけです。これを真偽値のフラグ ok で管理すれば、各問題を一度ずつ確認するだけで解けます。

アルゴリズム

1. 答えを格納する文字列 res を空文字列にし、ok を true にします。
2. 各問題の結果を先頭から順に読み、次の処理を行います。
   • ok が true かつ今回の結果が \(1\) なら、res に o を追加します。
   • それ以外なら、ok を false にして、res に x を追加します。
3. すべての問題を処理したら、res を出力します。

各問題の処理前に、ok は「それまでの問題にすべて正解しているか」を表します。したがって、ok が true で今回も正解した場合にだけ o を追加することで、得点の条件をそのまま再現できます。

計算量

• 時間計算量: \(O(N)\)
  各問題を一度ずつ処理します。
• 空間計算量: \(O(N)\)
  長さ \(N\) の出力文字列を保持します。それ以外に必要な作業領域は \(O(1)\) です。

実装のポイント

• 最初はまだ一度も間違えていないので、ok を true に初期化します。

• 一度 ok が false になったら、その後に正解しても true に戻してはいけません。

• 最初に間違えた問題自体も x です。

• 全問正解ならすべて o、最初の問題で間違えたならすべて x になります。

• 結果を配列に保存する必要はなく、提示コードのように読み込んだ直後に処理できます。

  ソースコード

// 問題文から独立に実装: フラグを持ち回る
#include <iostream>
#include <string>
int main() {
    int n; std::cin >> n;
    std::string res;
    bool ok = true;
    for (int i = 0; i < n; ++i) {
        int a; std::cin >> a;
        if (ok && a == 1) res += 'o';
        else { ok = false; res += 'x'; }
    }
    std::cout << res << std::endl;
}

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