New Year Contest 2015 C問題 - 文字列の書き換え

Source

New Year Contest 2015
問題文

問題概要

アルファベット小文字のみからなる文字列 $S,T$ が与えられる.
文字列 $S$ において,以下の操作を何回でもして良いので,文字列 $S$ を $T$ に変換できるかどうかを判定する問題.
・$S$ から文字を $1$ つ選び,その直後に違う文字を挿入する

解法

一つの解法はDPを用いることで解ける.
$S$ の最初 $a$ 文字から,$T$ の最初 $b$ 文字を作れるかどうかを考える.
作れるんだったら,$S_{a+1} = T_{b+1}$ なら,$S$ の最初 $a+1$ 文字から $T$ の最初 $b+1$ 文字も作れる.
また,$T_b \neq T_{b+1}$ なら,操作をすることで,$S$ の最初 $a$ 文字から $T$ の最初 $b+1$ 文字も作れる.
更に,$T_b = T_{b+1}$ だとしても,$T_b$ の文字を挿入することで得られたのであれば,その前に挿入することで,$S$ の最初 $a$ 文字から $T$ の最初 $b+1$ 文字も作れる.
よって,状態としては,($a$,$b$,$T_b$ は挿入することで得られたかどうか)を状態にして,$S$ の最初 $a$ 文字から,$T$ の最初 $b$ 文字を作れるかどうかを計算していけば良い.
時間計算量,空間計算量ともに $O(|S| \times |T|)$.

二つ目のの解法.
$T$ が $S$ の部分列でなければ不可能なのは明らかで,これは尺取法(貪欲法)の要領で確認できる.
そうであれば,$S$ と $T$ の最初の文字が一致していて,さらに,その $1$ 文字目と一致している最初の部分の文字数が $T$ の方が長くなければ,残りは挿入操作でどうとでもできるので可能.
時間計算量 $O(|S|+|T|)$.

C++によるスパゲッティなソースコード(DP)

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

int As, Bs;
char A[5555], B[5555];
int dp[2][5555][5555];

int main(){
  int i, j, k;

  As = reader(A);
  Bs = reader(B);

  dp[0][0][0] = 1;
  rep(i,As+1) rep(j,Bs+1) rep(k,2) if(dp[k][i][j]){
    if(k && j < Bs) dp[k][i][j+1] = 1;
    if(i < As && j < Bs && A[i]==B[j]) dp[0][i+1][j+1] = 1;
    if(k==0 && j < Bs && j && B[j-1]!=B[j]) dp[1][i][j+1] = 1;
  }

  if(dp[0][As][Bs]||dp[1][As][Bs]) writerLn("Yes"); else writerLn("No");

  return 0;
}

C++によるスパゲッティなソースコード(部分文字列判定+Ad hoc)

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

template<class T> int isSubsequence(T A[], int As, T B[], int Bs){int i,j=0;rep(i,As)if(A[i]==B[j])if(++j==Bs)break;return j==Bs;}

int As, Bs;
char A[5555], B[5555];

int main(){
  int i, j, k;
  int res = 1;

  As = reader(A);
  Bs = reader(B);

  if(!isSubsequence(B, Bs, A, As)) res = 0;
  if(A[0] != B[0]) res = 0;
  REP(i,1,As) if(A[i]!=A[0]) break;
  REP(j,1,Bs) if(B[j]!=B[0]) break;
  if(i<j) res = 0;
  if(res) writerLn("Yes"); else writerLn("No");

  return 0;
}

Current time: 2017年09月25日11時28分07秒
Last modified: 2015年01月28日00時32分06秒 (by laycrs)
Tags: Competitive_Programming AtCoder New_Year_Contest_2015
トップページに戻る

Logged in as: unknown user (not login)

ログイン: