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

2014年11月18日13時06分26秒

Codeforces Round #256 DIV2 B問題 - Suffix Structures

Source

Codeforces Round #256 DIV2 B問題
Problem description

問題概要

アルファベット小文字のみからなる $2$ つの文字列 $S,T$ が与えられる.
suffix automatonを使うと,文字列から任意の $1$ 文字を削除するという操作を何回でもできる.
suffix arrayを使うと,文字列内の任意の $2$ 文字をスワップするという操作を何回でもできる.
文字列 $S$ を文字列 $T$ に変換するためには,「suffix automatonのみを使うとできる」,「suffix arrayのみを使うとできる」,「片方では無理だけど両方使うとできる」,「両方使ってもできない」のどれであるかを判定する問題.
注:この問題で言う「suffix~」というのは,現実世界でのそれとは異なる.

解法

まず,各文字の出現回数を調べる.
$T$ の方が出現回数が多いという文字が $1$ 文字でもあれば,不可能.
全ての文字の出現回数が一致していればarrayのみで変換可能.
後は,$S$ が $T$ の部分列(部分文字列ではない)になっていればautomatonのみで可能で,そうでなければ両方必要.
部分列になっているかの判定は,greedyに,$S$ の最初の文字から,$T$ のどの文字に対応するかを見ていけば良い(対応させれる場所が複数あるなら,できるだけ $T$ の早い場所に出てくるのに対応させる).
計算時間量 $O(|S|+|T|+C)$,ここで $C=26$ はアルファベットの文字数.

C++のスパゲッティなコード

#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 READER_BUF_SIZE 1048576
#define WRITER_BUF_SIZE 1048576
int reader_pt=READER_BUF_SIZE,reader_last;char reader_buf[READER_BUF_SIZE];
int writer_pt=0;char writer_buf[WRITER_BUF_SIZE];
#define mygc(c) {if(reader_pt==READER_BUF_SIZE)reader_pt=0,reader_last=fread(reader_buf,sizeof(char),READER_BUF_SIZE,stdin);(c)=reader_buf[reader_pt++];}
#define mypc(c) {if(writer_pt==WRITER_BUF_SIZE)writer_pt=0,fwrite(writer_buf,sizeof(char),WRITER_BUF_SIZE,stdout);writer_buf[writer_pt++]=(c);}
#define myed {fwrite(writer_buf,sizeof(char),writer_pt,stdout);writer_pt=0;}

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;}return s;}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}

char S[1000], T[1000];
int SN, TN;

int SA[100], TA[100];

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

  SN = reader(S);
  TN = reader(T);

  rep(i,26) SA[i] = TA[i] = 0;
  rep(i,SN) SA[S[i]-'a']++;
  rep(i,TN) TA[T[i]-'a']++;

  rep(i,26) if(TA[i] > SA[i]) break;
  if(i < 26){ writer("need tree\n"); myed; return 0; }

  rep(i,26) if(TA[i]!=SA[i]) break;
  if(i==26){ writer("array\n"); myed; return 0; }

  k = 0;
  rep(i,TN){
    for(;;){
      if(T[i]!=S[k]) k++;
      else           break;
      if(k==SN){k=SN+1; break; }
    }
    k++;
  }
  if(k<=SN){ writer("automaton\n"); myed; return 0; }

  writer("both\n"); myed;
  return 0;
}

Current time: 2024年03月29日08時55分53秒
Last modified: 2014年11月18日13時06分26秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF256 CF_Div2_B
トップページに戻る

Logged in as: unknown user (not login)

ログイン: