AtCoder ARC002 C-コマンド入力 の嘘解法について

はじめに

　嘘解法がある問題について、古い問題ということもあり解説が少ないため解説記事を書きます。
　特に、自分が用いているPython言語での解説がネット上に見当たらず苦労したので、
　Python言語でのソースコードともに解説します。

問題

　問題文
　　ARC002 C-コマンド入力
　解説
　　公式解説

嘘解法

　L,Rを列挙し、L,Rどちらかから順に貪欲に置換する、を全通り試す。
　この解法では入力が

  8
  ABABBABA

　のようなケースで誤りになることが公式解説において説明されています。
　正解はL=AB,R=BAとすればLLRRと出来るので「4」ですが、
　嘘解法ですと、LLBLAあるいはARBRRとなって「5」となってしまいます。
　ただしこのようなケースがテスト項目に入っていないため、嘘解法でもACになります。

正しい解法

　公式解説にある通り、動的計画法を用います。
　自分は、i文字目を
　・(j=0) L,Rで置き換えない場合の文字数
　・(j=1) Lで置き換えられて、置き換えた場合の文字数
　・(j=2) Rで置き換えられて、置き換えた場合の文字数
　という3状態を作って解きました。
　このdp表を dp[j][i]と書いています。

　dp[0][i]は、1文字前の時点での文字数の最小値に+1した値です。

dp[0][i]= min(dp[0][i-1],dp[1][i-1],dp[2][i-1])+1

　dp[1][i]およびdp[2][i]は、i-1文字目とi文字目をLあるいはRで置き換えるわけですから、i-2文字目までの文字数の最小値に+1した文字数となります。

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

　i-1文字目とi文字目がL,Rでなく置き換えられない場合は
　・dp[0][i]をコピーしておく
　か
　・答えよりも大きい値を入れておく(Nとかfloat("inf")とか)
　としておきましょう。
　動的計画法によって最小値を取っていくので、dp[0][i]以上の値が何か入っていれば問題ありません。

サンプルコード(Python)

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)]  #初期値として0を代入していますが、本当は大きい値や文字数(i)を代入した方がこの後簡単に書けます

    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)

関連リンク

　C++での解説記事を書かれている方
　　忘れても大丈夫