前を優先的に変更する
というわけで、しらみつぶしではなく、前の方の文字を優先的に変更するというロジックで組み直してみます。
import sys
def main(f):
N = int(f.readline())
s = list(f.readline().strip())
while s[-1] == 'a' and len(s) > 1:
s.pop()
c = 0
while True:
print(c, ':', s)
update = False
for i in range(len(s)):
if s[i] == 'c':
s[i] = 'b'
c += 1
update = True
break
if s[i] == 'b':
s[i] = 'a'
if s[-1] == 'a':
s.pop()
c += 1
update = True
break
s[i] = 'b'
if not update:
break
print(c)
with open('input.txt', 'r') as f:
main(f)
ここでは、文字列をリストに変換して、（文字列をコピーするのではなく）リストを直接変更していくように実装を変えています。また、結果を見やすくするために、末尾の a は削除していきます。
# input
5
baaca
# output
0 : ['b', 'a', 'a', 'c']
1 : ['a', 'a', 'a', 'c']
2 : ['b', 'b', 'b', 'b']
3 : ['a', 'b', 'b', 'b']
4 : ['b', 'a', 'b', 'b']
5 : ['a', 'a', 'b', 'b']
6 : ['b', 'b', 'a', 'b']
7 : ['a', 'b', 'a', 'b']
8 : ['b', 'a', 'a', 'b']
9 : ['a', 'a', 'a', 'b']
10 : ['b', 'b', 'b']
11 : ['a', 'b', 'b']
12 : ['b', 'a', 'b']
13 : ['a', 'a', 'b']
14 : ['b', 'b']
15 : ['a', 'b']
16 : ['b']
17 : []
17
問題で与えられたサンプルに対して、確かに正しい答えが得られています。
さきほど、数字を減らしていく作業との類似を指摘しましたが、出力を下から上に読むと、数字を 1 ずつ増やしていく操作にも見えてきます。実際、17 -> 16 -> ... -> 2 までの流れは、a = 0, b = 1 とした 2 進数で、0 〜 1111 まで数える作業とぴったり一致しています。c がなければ、単純な 2 進数への置き換えで答えが得られることになります。
c を含む場合を探ってみる
では、c は、この計算ルールにどのように影響しているのでしょうか？ c を複数入れた例で様子を見ます。
# input
5
acbcb
# output
0 : ['a', 'c', 'b', 'c', 'a', 'b']
1 : ['b', 'b', 'b', 'c', 'a', 'b']
2 : ['a', 'b', 'b', 'c', 'a', 'b']
3 : ['b', 'a', 'b', 'c', 'a', 'b']
4 : ['a', 'a', 'b', 'c', 'a', 'b']
5 : ['b', 'b', 'a', 'c', 'a', 'b']
6 : ['a', 'b', 'a', 'c', 'a', 'b']
7 : ['b', 'a', 'a', 'c', 'a', 'b']
8 : ['a', 'a', 'a', 'c', 'a', 'b']
9 : ['b', 'b', 'b', 'b', 'a', 'b']
10 : ['a', 'b', 'b', 'b', 'a', 'b']
11 : ['b', 'a', 'b', 'b', 'a', 'b']
12 : ['a', 'a', 'b', 'b', 'a', 'b']
13 : ['b', 'b', 'a', 'b', 'a', 'b']
14 : ['a', 'b', 'a', 'b', 'a', 'b']
15 : ['b', 'a', 'a', 'b', 'a', 'b']
16 : ['a', 'a', 'a', 'b', 'a', 'b']
17 : ['b', 'b', 'b', 'a', 'a', 'b']
18 : ['a', 'b', 'b', 'a', 'a', 'b']
19 : ['b', 'a', 'b', 'a', 'a', 'b']
20 : ['a', 'a', 'b', 'a', 'a', 'b']
21 : ['b', 'b', 'a', 'a', 'a', 'b']
22 : ['a', 'b', 'a', 'a', 'a', 'b']
23 : ['b', 'a', 'a', 'a', 'a', 'b']
24 : ['a', 'a', 'a', 'a', 'a', 'b']
25 : ['b', 'b', 'b', 'b', 'b']
26 : ['a', 'b', 'b', 'b', 'b']
27 : ['b', 'a', 'b', 'b', 'b']
28 : ['a', 'a', 'b', 'b', 'b']
29 : ['b', 'b', 'a', 'b', 'b']
30 : ['a', 'b', 'a', 'b', 'b']
31 : ['b', 'a', 'a', 'b', 'b']
32 : ['a', 'a', 'a', 'b', 'b']
33 : ['b', 'b', 'b', 'a', 'b']
34 : ['a', 'b', 'b', 'a', 'b']
35 : ['b', 'a', 'b', 'a', 'b']
36 : ['a', 'a', 'b', 'a', 'b']
37 : ['b', 'b', 'a', 'a', 'b']
38 : ['a', 'b', 'a', 'a', 'b']
39 : ['b', 'a', 'a', 'a', 'b']
40 : ['a', 'a', 'a', 'a', 'b']
41 : ['b', 'b', 'b', 'b']
42 : ['a', 'b', 'b', 'b']
43 : ['b', 'a', 'b', 'b']
44 : ['a', 'a', 'b', 'b']
45 : ['b', 'b', 'a', 'b']
46 : ['a', 'b', 'a', 'b']
47 : ['b', 'a', 'a', 'b']
48 : ['a', 'a', 'a', 'b']
49 : ['b', 'b', 'b']
50 : ['a', 'b', 'b']
51 : ['b', 'a', 'b']
52 : ['a', 'a', 'b']
53 : ['b', 'b']
54 : ['a', 'b']
55 : ['b']
56 : []
56
出力結果を下から上に見ると、右から順に c が現れていることがわかります。一番右の c が現れる 1 つ前（出力で言うと、1行下）までを見ると、さきほどの2進数計算で 1 ずつ増えていって、
・c より前（c の位置を含む）は、すべて b
・c より後（c の位置は含まない）は、もとの文字列のまま
という値にたどり着いています。したがって、「上記で決まる 2 進数 + 1」回の（逆向きの）操作で、1 つ目の c が出現する所までいけるのです。
では、その上の行はどうなっているでしょうか？ 一番右の c 以降は変化しませんので、c より前だけを見ればよいことに気が付きます。そして、一番右の c 以降を切り捨てて考えれば、次の c が現れるまで、同じルールの計算になっています。
つまり、右から順に c が出現する位置を探しながら、c が出現するごとに、先の「上記で決まる 2 進数 + 1」の値を加えていけばOKとわかります。さっくり実装すると、こんな感じですね。
import sys
def main(f):
N = int(f.readline())
s = list(f.readline().strip())
c = 0
bits = 0
for i in range(len(s)-1, -1, -1):
if s[i] == 'c':
for j in range(i, -1, -1):
bits = bits * 2 + 1
c += bits + 1
bits = 0
continue
if s[i] == 'a':
bits = bits * 2 + 0
if s[i] == 'b':
bits = bits * 2 + 1
c += bits
print(c)
with open('input.txt', 'r') as f:
main(f)
atcoder.jp
