AtCoder Beginner Contest 286のC pythonでの実装
問題:C - Rotate and Palindrome
注意としてpythonで提出するとTLEになるのでPypyで提出すると通る。
問題内容:操作A(左端の文字を右端に移動する)と操作B(ある文字を別の文字にする)を最小回数やって文字列が回文になったときの操作Aのコストaと操作Bのコストbの和を求めるもの。
考え方:ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286) - YouTubeでも言っているが操作Aをi回してiに対して操作B全通り試すというのをfor文でやればよい。
pythonでの実装:
n,a,b=map(int, input().split()) s=list(input()) st=s[::-1] count=0 l=[] #最初から合ってるとき if s==st: print(0) exit() count=0 for i in range(n): if i>=1: #操作A s.append(s[0]) del s[0] count=a*i #操作B for j in range(n//2): if s[j]!=s[n-j-1]: count+=b l.append(count) count=0 print(min(l))
プログラムについて:操作Aはs.append(s[0])で初めの文字を一番うしろに追加して、del s[0]で初めの文字を消す。
操作Bはif s[j]!=s[n-j-1]:のとき、例えばjが0では一番左と一番右が違うとき、count+=bする。これは違うときにどちらか片方の文字を変えれば回文になるからである。またfor j in range(n//2):のn//2は操作Bを例えば5文字のとき0,4文字目と1,3文字目を比べれば良いので5//2=2文字目まで回せば良い。
最終的にはi(操作Aの回数)に対するそれぞれのコストを求めてリストに入れていきリストの最小値をとればよい。