【AGC 026】C.String Coloring

Atcoder Python AGC

問題文

長さ 2N の，英小文字のみからなる文字列 S が与えられます。

S の各文字を赤色か青色かに塗り分ける方法は22N 通りありますが，

このうち以下の条件を満たす塗り分け方は何通りですか？

  • 赤色に塗られた文字を左から右に読んだ文字列と，

    青色に塗られた文字を右から左に読んだ文字列が一致する

制約

  • 1≤N≤18
  • Sの長さは2Nである
  • Sは英小文字のみからなる

考え方

コンテスト中には全く分からなかったので以下のコードを参考に考えました。 https://beta.atcoder.jp/contests/agc026/submissions/2864808

itertools.product関数

#以下二つは同じ結果
print(list(product(range(3),repeat=3)))
print(list(((x,y,z) for x in range(3) for y in range(3) for z in range(3))))

[(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2), 
(1, 0, 0), (1, 0, 1), (1, 0, 2),(1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2), 
(2, 0, 0), (2, 0, 1), (2, 0, 2), (2, 1, 0), (2, 1, 1), (2, 1, 2),(2, 2, 0), (2, 2, 1), (2, 2, 2)]

この関数を使って{0,1}のビットを用いて左側半分、右側半分についてそれぞれ文字列を区分する。

  • N=4,S=cabaacbaにおいて左側半分を区別する例
from collections import Counter
from itertools import product

N=int(input())
S=list(input())

bit=list(product(range(2),repeat=N)) #この例ではN=4なので、(0,0,0,0)~(1,1,1,1)の16パターン
leftlist=[]

for i in range(len(bit)):
  red=''
  blue=''
  for j in range(N):
    if bit[i][j] == 1:
      red+=S[j]
    else:
      blue+=S[j]
  leftlist.append("".join(red + "|" + blue))
left=Counter(leftlist)
print(left)    

Counter({'cba|a': 1, 'cb|aa': 1, 'ca|ab': 1, 'caa|b': 1, '|caba': 1, 'a|cba': 1, 'caba|': 1, 'ab|ca': 1, 
'ba|ca': 1, 'aba|c': 1, 'aa|cb': 1, 'cab|a': 1, 'ca|ba': 1, 'a|cab': 1, 'c|aba': 1, 'b|caa': 1})
#それぞれの分け方について、何通りあるかが表示される。この例では全て1回しか出てこない値は全て1

例えば、タプルの一つ目に出ている,

'cba|a': 1について考えてみると下のような状態

cabaacba ×この時は題意を満たすように塗れない

'ca|ab': 1について考えてみると下のような状態

cabaacba

下のように塗ると題意を満たします　

cabaacba

文字列の右側の塗り方をみると、ac|ba(blue+red)になっている。

左側はca|ab(red+blue)...(ここで何かに気付く）

文字列を逆側から考えると右半分についても、ca|ab(blue+red)

よって、左側半分と右側半分に対して色塗りの組み合わせが同じものを数え上げれば良いです。

左半分の青と右半分の赤は読む時は共に逆向きなので直感的に変に感じるかもしれないことに気をつけて下さい。

ソースコード

from collections import Counter
from itertools import product
 
N=int(input())
S=list(input())
S_rev=list(reversed(S[N:])) #右側から読んだ右半分の文字を考える
 
 
leftlist=[] #左半分の分け方の組み合わせを格納
rightlist=[] #右半分について同様
 
for bit in product(range(2),repeat=N):
  #左半分、右半分について赤と青に塗り分ける
  red_left='' 
  blue_left=''
  red_right=''
  blue_right=''
  for j in range(N):
    if bit[j] == 1:
      red_left+=S[j] #bitに1が立っているところを赤に
      blue_right+=S_rev[j]
    else:
      blue_left+=S[j]
      red_right+=S_rev[j]
  leftlist.append("".join(red_left + "|" + blue_left)) #左の塗り方をリストに格納
  rightlist.append("".join(blue_right + "|" + red_right)) #右について同様
left=Counter(leftlist)
right=Counter(rightlist)
 
answer=0
 
for key,value in left.items():
  answer+= value * right[key] #同じkey(分け方）に対するredとblueの通りを掛け合わせる
print(answer)

私も理解が不十分なのですが、分からないところがあればコメントして下さい!(一緒に考えます）