手探りで解法のヒントを見つける

競技プログラミングでは、入力例などのケースで「実験」を行うことで、解法の手がかりをつかめる場合があります。

早速、具体例として、初期状態 00000 から状態を 01010 にするためにどうすればいいか考えます。例えば、以下のように手探りで考えることになると思います。

1 文字ずつでも合わせていきたいので、まずは 2 文字目を 1 にすることを考えよう。A, A, B の順に押せば、00000 → 10000 → 11000 → 01000 となった。あとは 4 文字目さえ 1 にすればよい。でも、ここからどうすればいいのか？

• 例えば、A を 3 連続で押せば 01000 → 11000 → 11100 → 11110 となる。しかし、せっかく 2 文字目だけ 1 にしておいたのが侵食されてしまう。
• どこかで B を押しておけばよかったのではないか。例えば A を 1 回押して 11000 とした後に B を押すと、01000 となる。しかし、もう一度 A を押しても 11000 に戻ってしまう。だから、結局は前と同じことになる。

つまり、一旦 2 文字目を 1 にしても、4 文字目を 1 に合わせようとしたら、その労力が無駄になってしまいます。だから、最初は 4 文字目を 1 にすることを考えなければなりません。以下のようにして、状態を 01010 にできます。

• まずは 4 文字目を 1 にしたい。A, A, A, A, B, B, B の順に押せば、00000 → 10000 → 11000 → 11100 → 11110 → 01110 → 00110 → 00010 となる。
• あとは 2 文字目さえ 1 にすればよい。A, A, B の順に押せば、00010 → 10010 → 11010 → 01010 となる（先ほどの例と同じやり方）。

パズルの解き方

まず、000...0 の状態から、\(k\) 文字目だけ 1 にするためには、「スイッチ A を \(k\) 連続押し、その後スイッチ B を \(k-1\) 連続押す」操作をすればよいです。この後に \(k\) 文字目より前の文字を 1 に変えたい時でも、同じ方法が使えます。

よって、\(S\) に 1 が \(x_1, x_2, \dots, x_k\) 文字目 \((x_1 < x_2 < \dots < x_k)\) にあるとして

• A を \(x_k\) 連続押し、B を \(x_k-1\) 連続押す（\(x_k\) 文字目が 1 に変わる）
• （中略）
• A を \(x_2\) 連続押し、B を \(x_2-1\) 連続押す（\(x_2\) 文字目が 1 に変わる）
• A を \(x_1\) 連続押し、B を \(x_1-1\) 連続押す（\(x_1\) 文字目が 1 に変わる）

という操作方法で目的の状態にできます。

解答例

C++ での実装例は https://atcoder.jp/contests/arc177/submissions/53281593 です。

Python では以下のように実装できます。

# 入力
n = int(input())
s = input()

# 答えを求める
ans = ''
for i in range(n-1, -1, -1):
	if s[i] == '1':
		ans += 'A' * (i+1) + 'B' * i

# 出力
print(len(ans))
print(ans)