保存されている過去のバージョンの一覧

2015年01月28日00時32分06秒
2015年01月28日00時06分47秒
2015年01月27日23時52分37秒

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: 2024年04月19日20時48分09秒
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)

ログイン：