Codeforces Round #315 DIV1 C問題 (1500pt)
Codeforces Round #315 DIV2 E問題 (2750pt)
Problem description
ある言語では,単語は以下のルールによって定められる.
使われる文字の種類は $L$ 種類で,アルファベット小文字の最初から $L$ 個を用いる.
また各文字は母音か子音であり,それは与えられる.
単語は全て $N$ 文字からなる.
また,制約が $M$ 個与えられ,各制約は,$t_1$ 文字目が(母音|子音)であれば,$t_2$ 文字目は(母音|子音)でなければならないという形をしている.
以上の条件を満たすものは全てその言語の正しい単語である.
$N$ 文字のアルファベット小文字の最初から $L$ 文字のみを用いた文字列 $S$ が与えられるので,$S$ より辞書順で小さくないもので,辞書順最小の単語を求める問題.
存在しないならそれを指摘する.
各制約は,対偶も加えておく,つまり,$1$ 文字目が母音ならば $2$ 文字目が子音という条件があれば,$2$ 文字目が母音ならば $1$ 文字目は子音という条件も加えておく.
そうすると,$N$ 文字からなる文字列で,各文字を母音/子音/どちらでも良いと割り振った時に,そのような単語が存在しうるかどうかを,単純に条件を辿っていく(決まっている文字について条件を確認して,新しく決まった文字についても同様に条件を確かめていく)だけで判定することができる.
後は,$S$ が正しい単語かどうかを判定して,正しくなければ,最後の文字を $1$ つずつ大きくしながら判定していく.
最後の文字をどうしても正しい単語にならなければ,最後の文字はなんでも良いことにして,最後から $2$ 番目の文字を増やしていく,などとして,正しい単語になりうるようになれば,不確定の文字を最初から辞書順最小になるように確定させていく.
これだと,時間計算量は $O(NML)$ だが,母音か子音のどちらかのみを試せば良いので,$O(NM)$ でもできる.
#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;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
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 S, N, M;
int rule[2][200][200];
char num[222];
char in[222];
int now[222];
int st[222], sts;
int is_ok(){
int i, j, k;
sts = 0;
rep(i,N){
now[i] = -1;
if(in[i] != '?'){
now[i] = num[in[i]-'a'];
st[sts++] = i;
}
}
while(sts){
i = st[--sts];
rep(j,N){
k = rule[now[i]][i][j];
if(k==3) continue;
if(k==0) return 0;
if(now[j]==-1){
st[sts++] = j;
if(k==1) now[j] = 0;
if(k==2) now[j] = 1;
}
if(k==1 && now[j]!=0) return 0;
if(k==2 && now[j]!=1) return 0;
}
}
return 1;
}
int main(){
int i, j, k, s, a, b;
int cnv[333];
cnv['V'] = 0;
cnv['C'] = 1;
S = reader(num);
rep(i,S) num[i] = cnv[num[i]];
reader(&N,&M);
rep(i,2) rep(j,N) rep(k,N) rule[i][j][k] = 3;
rep(i,2) rep(j,N) rule[i][j][j] = (1<<i);
while(M--){
reader(&i,in);
reader(&j,in+1);
rep(k,2) in[k] = cnv[in[k]];
i--; j--;
rule[in[0]][i][j] &= (1<<in[1]);
rule[1-in[1]][j][i] &= (1<<(1-in[0]));
}
reader(in);
if(is_ok()){ writerLn(in); return 0; }
for(i=N-1;i>=0;i--){
for(;;){
in[i]++;
if(in[i] > 'a'+S-1) break;
if(is_ok()) break;
}
if(in[i] > 'a'+S-1) in[i] = '?'; else break;
}
if(in[0]=='?'){ writerLn(-1); return 0; }
rep(i,N) if(in[i]=='?'){
in[i] = 'a';
while(!is_ok()){
in[i]++;
if(in[i] > 'a'+S-1){
writerLn(-1);
return 0;
}
}
}
writerLn(in);
return 0;
}
Current time: 2024年04月20日02時20分50秒
Last modified: 2015年08月15日05時50分24秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF315 CF_Div1_C CF_Div2_E
トップページに戻る
Logged in as: unknown user (not login)