超初心者が競プロに挑む

初心者からの競プロ練習記録

ARC002C解いてみた

問題A,Bは特に解説読んでわかった。

問題C

L,Rの全通りについての下記の漸化式に従った動的計画法を実行して求めることができる。

dp[i]をi番目までの最小のコマンド入力回数とします(普通のi番目です。例えば0番目といわれたら、0文字目つまり、何の文字も指しません。プログラミング的ではないという意味で)。

\begin{eqnarray} dp[i] =\begin{cases} dp[i-2] +1  (コマンドのi番目とi-1番目がLまたはRで置換可能である時) \\ dp[i-1] + 1 (それ以外の時)\end{cases}\end{eqnarray}

ソースコードは以下のようになる

#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
  int N;
  char c[1010];
  scanf("%d", &N);
  scanf("%s", c);

  char ab[4] = {'A','B', 'X', 'Y'};
  int answer=10000;
  for(int j=0;j<(1<<8);++j) {
    int dp[1010];
    for(int i=0;i<=N;++i) {
      dp[i] = i;
    }
    char X[3]={0,0,0};
    char Y[3]={0,0,0};
    X[0] = ab[(j)&3];
    X[1] = ab[(j>>2)&3];
    Y[0] = ab[(j>>4)&3];
    Y[1] = ab[(j>>6)&3];
    for(int i=2;i<=N;++i) {
      if(c[i-2] == X[0] && c[i-1] ==X[1]) {
        dp[i] = dp[i-2] + 1;
      } else if(c[i-2] == Y[0] && c[i-1] ==Y[1]) {
        dp[i] = dp[i-2] + 1;
      } else {
      dp[i] = dp[i-1] + 1;
      }
    }
    answer = min(answer, dp[N]);
  }
  printf("%d\n", answer);
  return 0;
}

疑問点1 この漸化式で良い証明はどうなるのか?

i回目までの最小のボタン入力がわかっているとします。dp[i],dp[i+1],dp[i+2]の関係を調べます。

ここで、i-1,i,i+1,i+2番目のコマンドがP,Q,S,Tとします。

ここで、S,TがLかRに一致している時はi+2回目のまでの最小のボタン入力は明らかにdp[i+2]=dp[i]です。なぜならこれより良い方法は存在しないからです。

また、Q, S, Tの並びがL,Rと置換できない時にはdp[i+1]=dp[i]+1,dp[i+2]=dp[i]+2として良いですね。

Q,SがL,Rで置換できる時を考えます。P,QがL,Rに置換できない時には、明らかに置換した方が回数が減ります。dp[i+1]=dp[i],dp[i+2]=dp[i]+1です。

P,QがL,Rで置換できる時はどうでしょうか。この場合はP,Qを置換してもQ,Sを置換しても計算するとdp[i+1]の回数もdp[i+2]の回数も変わりません。dp[i+1]=dp[i]+1,dp[i+2]=dp[i]+2となります。

これをまとめると、漸化式のようにi番目とi-1番目が置換できる場合には、とりあえずそこで置換したと考えてdp[i]=dp[i-2]+1として、それ以外では1ずつ足せば良いとなります。

疑問点2 割り当てられるコマンドが仮にk文字(kが3以上)でも同じ漸化式で良いのか?

同じように考えます。i回目までの最小のボタン入力がわかっているとします。i+1~i+kが置換できる場合には、明らかに置換したものが最短になります。dp[i+k]=dp[i]+1です。

また、i-k+1番目以降全く置換できない時は、ボタン入力回数は単に1ずつ増加します。

i+1-j~i+k-jが置換できるときはどうでしょうか(jは1~k-1の間)。この時、i+1-j~i番目までについて、すでに置換されている部分がない場合には明らかに置換した方が回数が少なくなります。dp[i+k-j]=dp[i-j]+1です。また、すでに置換されていた場合でも、計算するとi+1-j~i+k-jで置換したと考えても回数に変化はありません。dp[i+k-j]=dp[i-j]+1として良いとなります。

まとめると、常にi-k~i番目が置換できればそこで置換したと考えて漸化式を進められます。