I will write a commentary article about a problem with a lie solution because there are few explanations because it is an old problem. In particular, I had a hard time because I couldn't find any explanation in the Python language I was using on the internet. I will explain both the source code in the Python language.
Problem statement ARC002 C-command input Commentary Official commentary
Enumerate L and R and greedily replace either L or R in order. In this solution the input is
8
ABABBABA
It is explained in the official commentary that it will be wrong in such cases. The correct answer is "4" because it can be LLRR if L = AB and R = BA. If it is a lie solution method, it will be LLBLA or ARBRR and it will be "5". However, since such a case is not included in the test items, it will be AC even with the lie solution method.
As stated in the official commentary, we use dynamic programming. I'm the i-th letter ・ (J = 0) Number of characters when not replaced by L, R ・ (J = 1) Number of characters when replaced with L ・ (J = 2) Number of characters when replaced by R I made 3 states and solved it. This dp table is written as dp [j] [i].
dp [0] [i] is the value obtained by adding +1 to the minimum number of characters at the time before one character.
dp[0][i]= min(dp[0][i-1],dp[1][i-1],dp[2][i-1])+1
Since dp [1] [i] and dp [2] [i] replace the i-1 and i characters with L or R, the minimum number of characters up to the i-2 character is increased by +1. It is the number of characters.
if c[i-2:i]==L:
dp[1][i]=min(dp[0][i-2],dp[1][i-2],dp[2][i-2])+1
if c[i-2:i]==R:
dp[2][i]=min(dp[0][i-2],dp[1][i-2],dp[2][i-2])+1
If the i-1 and i characters are not L and R and cannot be replaced ・ Copy dp [0] [i] Or ・ Enter a value larger than the answer (N or float ("inf")) Let's leave it as. Since the minimum value is taken by dynamic programming, there is no problem as long as there is something more than dp [0] [i].
N=int(input())
c=input()
L_list=["AA","AB","AX","AY","BA","BB","BX","BY","XA","XB","XX","XY","YA","YB","YX","YY"]
R_list=["AA","AB","AX","AY","BA","BB","BX","BY","XA","XB","XX","XY","YA","YB","YX","YY"]
ans=N
for L in L_list:
for R in R_list:
dp= [[0]*(N+1) for _ in range(3)] #Although 0 is assigned as the initial value, it is actually a large value or the number of characters.(i)It is easier to write after this if you substitute
for i in range(1,N+1):
dp[0][i]= min(dp[0][i-1],dp[1][i-1],dp[2][i-1])+1
if i==1:
dp[1][i]= 1
dp[2][i]= 1
else:
if c[i-2:i]==L:
dp[1][i]=min(dp[0][i-2],dp[1][i-2],dp[2][i-2])+1
dp[2][i]=N
elif c[i-2:i]==R:
dp[1][i]=N
dp[2][i]=min(dp[0][i-2],dp[1][i-2],dp[2][i-2])+1
else:
dp[1][i]=N
dp[2][i]=N
tmp=min(dp[0][-1],dp[1][-1],dp[2][-1])
ans=min(ans,tmp)
print(ans)
Those who are writing commentary articles in C ++ It's okay to forget