解法

得点がもらえるのは「先頭から連続して正解している間」だけです。つまり、最初に \(A_i = 0\) となる問題が現れた時点で、それ以降のすべての問題(その問題自身も含む)は得点対象外になります。

したがって、先頭からの連続する \(1\) の個数を \(k\) とすると、答えは o を \(k\) 個、x を \(N - k\) 個並べた文字列になります。

実装ではフラグ ok を用意し、各問題を順に見ます。\(A_i = 0\) が現れたら ok を false にし、それ以降は false のままです。各問題で ok が true なら o、そうでなければ x を出力文字列に追加します。

正しさの証明

問題 \(i\) で得点がもらえる条件は「\(1\) 問目から \(i\) 問目まですべて正解」すなわち \(A_1 = A_2 = \cdots = A_i = 1\) です。

• \(i \le k\) のとき:\(k\) の定義より \(A_1, \ldots, A_k\) はすべて \(1\) なので \(A_1 = \cdots = A_i = 1\) が成り立ち、得点がもらえます。アルゴリズムはこの間 ok が true のままなので o を出力します。
• \(i > k\) のとき:\(A_{k+1} = 0\) であり \(k+1 \le i\) なので、\(A_1 = \cdots = A_i = 1\) は成り立たず得点はもらえません。アルゴリズムは \(i = k+1\) の時点で ok が false になり、それ以降 false のままなので x を出力します。\(A_{k+1} = 0\) 自身も正解ではないため x が正しい出力です。

よってすべての問題について正しい文字が出力されます。出力は一意に定まるため、同点時の処理(タイブレーク)は存在しません。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: 入力を逐次読みながら処理する C++ 版は出力文字列を除き \(O(1)\)、出力文字列を含めても \(O(N)\) です。Python 版は入力を一括で読むため \(O(N)\) です。