Codeforces Round #288 DIV2 D問題 - Tanya and Password

Source

Codeforces Round #288 DIV2 D問題 (2000pt)
Problem description

問題概要

$N$ 個の $3$ 文字からなる文字列 $S_1,S_2,\ldots,S_N$ が与えられる．
$N+2$ 文字の文字列で，その連続する $3$ 文字からなる $N$ 個の部分列が $S_1,\ldots,S_N$ と多重集合として一致するような文字列を $1$ つ求める問題．
（任意の文字列に対して，$N$ 個の部分列に含まれる数と，$S_1,\ldots,S_N$ に含まれる数が等しい）
存在しないならそれを指摘する．

解法

以下の有向グラフを考える．
各ノードは $2$ 文字からなる文字列で，与えられた $N$ 個の文字列を枝とみなす．
文字列が $s_1s_2s_3$ なら，$s_1s_2$ というノードから $s_2 s_3$ というノードへの枝と思う．
すると，そのグラフ上で，全ての枝を一度ずつ通るようなパスが見つけられれば，$N+2$ 文字の文字列を復元できる．
これはEuler路なので，まず，グラフが連結でなければ存在しない．
そして，入次数 $-$ 出次数が全て $0$ の場合，または， $1$ のノードと $-1$ のノードが $1$ つずつで残りは $0$ の場合，の $2$ パターンでなければ存在しない．
存在する場合は，入次数 $-$ 出次数が $-1$ のノード（全部 $0$ の場合はどのノードからでも良い）から初めて，順番に使われてない辺をDFSで辿っていく．
辿れるとことまで辿って，また使われていない辺があれば，そこで寄り道したことにしてその閉路も足していくというふうにやればEuler路を求めることができる（実際にはDFSでこれ以上進めないとなったノードから順番に記憶していって，最後に反転させるなどすれば良い）．
時間計算量は $O(N)$ 程度．

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 mygc(c) (c)=getchar()
#define mypc(c) putchar(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
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');}

void* setDirectEdge(int N, int M, int A[], int B[], int **es, int ***edge, void *workMemory){int i;*es=(int*)workMemory;*edge=(int**)((*es)+N);(*edge)[0]=(int*)((*edge)+N);rep(i,N)(*es)[i]=0;rep(i,M)(*es)[A[i]]++;REP(i,1,N)(*edge)[i]=(*edge)[i-1]+(*es)[i-1];workMemory=(void*)((*edge)[N-1]+(*es)[N-1]);rep(i,N)(*es)[i]=0;rep(i,M)(*edge)[A[i]][(*es)[A[i]]++]=B[i];return workMemory;}
void directedEulerPathDFS(int now, int *es, int **edge, int *used, int res[], int *sz){int i;while(used[now]<es[now]){i=used[now]++;directedEulerPathDFS(edge[now][i],es,edge,used,res,sz);}res[(*sz)++]=now;}
int directedEulerPath(int N, int *es, int **edge, int res[], void *mem){int i,j,M=0,s=0,*d,*u;d=(int*)mem;u=d+N;rep(i,N)d[i]=0;rep(i,N){M+=es[i];rep(j,es[i])d[edge[i][j]]--;d[i]+=es[i];}j=-1;rep(i,N){if(!d[i]) continue;if(d[i]<-1||d[i]>1)return -1;if(d[i]==1){if(j!=-1)return -1;j=i;}}if(j==-1){rep(i,N)if(es[i]){j=i;break;}}rep(i,N)u[i]=0;directedEulerPathDFS(j,es,edge,u,res,&s);if(s!=M+1)return -1;reverse(res,res+s);return s;}

char memarr[77000000]; void *mem = memarr;
#define MD 1000000007

int N;
char in[210000][5];
int A[210000], B[210000];

int node;
int *es, **edge;

int res[210000], ress;


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

  reader(&N);
  rep(i,N) reader(in[i]);

  node = 128 * 128;
  rep(i,N){
    A[i] = in[i][0] * 128 + in[i][1];
    B[i] = in[i][1] * 128 + in[i][2];
  }

  mem = setDirectEdge(node, N, A, B, &es, &edge, mem);
  ress = directedEulerPath(node, es, edge, res, mem);
  if(ress < 0){ writerLn("NO"); return 0; }

  writerLn("YES");
  mypc(res[0]/128);
  rep(i,ress) mypc(res[i]%128);
  writerLn("");

  return 0;
}

Current time: 2024年04月20日09時16分23秒
Last modified: 2015年01月28日23時10分46秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF288 CF_Div2_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン：