まずはしらみつぶし
まずは、しらみつぶしで、文字列が変化する様子を観察します。キューを用いた全件探索を実装します。
import sys, copy from collections import defaultdict, deque def main(f): N = int(f.readline()) S = f.readline().strip() q = deque() q.append((0, S)) # count, string c_max = 0 while q: c, s = q.pop() print(c,':', s) c_max = max(c, c_max) for i in range(len(s)): tmp = s.translate(str.maketrans('abc', 'bca')) if s[i] == 'b': s = tmp[:i] + 'a' + s[i+1:] q.append((c+1, s)) if s[i] == 'c': s = tmp[:i] + 'b' + s[i+1:] q.append((c+1, s)) print(c_max) with open('input.txt', 'r') as f: main(f)
# input 3 aba # output 0 : aba 1 : baa 2 : aaa 2
これを見ると文字列の右から順に、a が増えていって、最後はすべて a になって終わります。
ここで変換のルールを思い出すと、ある位置の文字を c -> b -> a と変更すると共に、それより前の文字をローテーションします。逆にいうと、c -> b -> a と変更する対象より後ろは、何も変化しません。したがって、ある位置から後ろがすべて a になれば、その部分はもはや変化することができないのです。
ということは、できるだけ長く変更を続けるには、前の方の文字を優先的に変更して、後ろの方の文字はできるだけ変更しない方がよさそう、と気づきます。
イメージでいうと、n 桁の数字を減らしていく作業に似ています。減らす操作をできるだけ長く続けるには、1 ずつ減らすのがベストです。
(1) 下の桁の値を 1 ずつ減らしていき、それ以上減らせなくなった（つまり 0 になった）ら、1つ上の桁を 1 減らす。
(2) 上の桁を 1 減らすと、その下の桁の数字はすべて 9 にもどる。
これって、変更した文字の手前をすべてローテーションする、という作業を (2) に対応させると、非常によく似ていることがわかります。
前を優先的に変更する
というわけで、しらみつぶしではなく、前の方の文字を優先的に変更するというロジックで組み直してみます。
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)
