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

2016年02月05日22時07分39秒

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 C問題 - アメージングな文字列は、きみが作る！

Source

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選
問題文

問題概要

アルファベット小文字のみからなる $N$ 文字の文字列 $S$ が与えられる．
$K$ 回だけ以下の操作1.から3.のどれかを行えるとき，最終的に得られる文字列のうち，辞書順最小のものを求める問題．

  1. $S$ から $1$ 文字削除する
  2. $S$ の中の $1$ 文字を別のアルファベット小文字に変える
  3. $S$ の好きな場所にアルファベット小文字を $1$ 文字挿入する

解法

という $3$ 段階の比較の仕方をしていく．
まず，$\verb|a|$ 以外の文字を全て削除できるなら，$N-K$ 文字の $\verb|a|$ のみからなる文字列が答え．
そうでないなら，最初に連続する $\verb|a|$ の数を最大にすることを考える．
これは，$K$ 回の操作は，全て最初に $\verb|a|$ を挿入するか，他の文字を $\verb|a|$ に変えるか，のどちらかの操作しか行わないことを意味する．
$\verb|a|$ の数を最大化するには，すでに $S$ に含まれる $\verb|a|$ をできるかぎり有効利用すればよく，$S$ の中に含まれる $\verb|a|$ に対して，それより左の $\verb|a|$ 以外の文字を $\verb|a|$ に変えることができるなら，それを行う，とする．
残りの操作回数は，最初に連続する $\verb|a|$ の後の文字列を最小にすることに使用する．
SuffixArrayを作っておいて，辞書順で小さい順に，先頭が $\verb|a|$ でなく，それより前を全て $\verb|a|$ に変換可能なものを見つけて，それを行い，余った操作回数は先頭に $\verb|a|$ をくっつければ良い．

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_unlocked()
#define mypc(c) putchar_unlocked(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');}

char memarr[17000000]; void *mem = memarr;

template<class T> void SuffixArray(T *s, int N, int K, int *SA, int *LCP, void *mem) {int i,j,d,m,*u,n,v,p;char*t=(char*)mem;char*l=t+N+1;int*x=(int*)(l+N+1);int*z=x+K+1;int*y=z+K+1;mem=y+K+1;N++;s[N-1]=0;t[N-1]=1;t[N-2]=0;for(i=N-3;i>=0;i--)if(s[i]<s[i+1]||(s[i]==s[i+1]&&t[i+1]))t[i]=1;else t[i]=0;l[0]=0;REP(i,1,N)if(t[i]&&!t[i-1])l[i]=1;else l[i]=0;rep(i,K+1)z[i]=0;rep(i,N)z[s[i]]++;j=0;rep(i,K+1)j+=z[i],y[i]=j-z[i],z[i]=j;rep(i,K+1)x[i]=z[i];for(i=0;i<N;i++)SA[i]=-1;for(i=1;i<N;i++)if(l[i])SA[--x[s[i]]]=i;rep(i,K+1)x[i]=y[i];rep(i,N){j=SA[i]-1;if(j>=0&&!t[j])SA[x[s[j]]++]=j;}rep(i,K+1)x[i]=z[i];for(i=N-1;i>=0;i--){j=SA[i]-1;if(j>=0&&t[j])SA[--x[s[j]]]=j;}m=0;rep(i,N)if(l[SA[i]])SA[m++]=SA[i];REP(i,m,N)SA[i]=-1;n=0;v=-1;rep(i,m){p=SA[i];rep(d,N){if(v==-1||s[p+d]!=s[v+d]||t[p+d]!=t[v+d]){n++;v=p;break;}else if(d>0&&(l[p+d]||l[v+d]))break;}p/=2;SA[m+p]=n-1;}for(i=N-1,j=N-1;i>=m;i--)if(SA[i]>=0)SA[j--]=SA[i];u=SA+N-m;if(n<m)SuffixArray(u,m-1,n-1,SA,NULL,mem);else for(i=0;i<m;i++)SA[u[i]]=i;rep(i,K+1)x[i]=z[i];for(i=1,j=0;i<N;i++)if(l[i])u[j++]=i;for(i=0;i<m;i++)SA[i]=u[SA[i]];for(i=m;i<N;i++)SA[i]=-1;for(i=m-1;i>=0;i--)j=SA[i],SA[i]=-1,SA[--x[s[j]]]=j;rep(i,N){j=SA[i]-1;if(j>=0&&!t[j])SA[y[s[j]]++]=j;}for(i=N-1;i>=0;i--){j=SA[i]-1;if(j>=0&&t[j])SA[--z[s[j]]]=j;}if(LCP!=NULL){x=(int*)t;d=0;rep(i,N)x[SA[i]]=i;rep(i,N){if(x[i]){for(j=SA[x[i]-1];j+d<N-1&&i+d<N-1&&s[j+d]==s[i+d];d++);LCP[x[i]]=d;}else LCP[x[i]]=-1;if(d>0)d--;}}}

int N, K;
char S[400000];

int SA[400000];
int cnt[400000];

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

  N = reader(S);
  reader(&K);

  cnt[i] = 0;
  rep(i,N){
    cnt[i+1] = cnt[i];
    if(S[i]!='a') cnt[i+1]++;
  }
  if(K >= cnt[N]){
    rep(i,N-K) mypc('a');
    mypc('\n');
    return 0;
  }

  k = 0;
  rep(i,N) if(S[i]=='a' && cnt[i] <= K) k = i;
  rep(i,k) if(S[i]!='a') S[i]='a', K--;

  cnt[i] = 0;
  rep(i,N){
    cnt[i+1] = cnt[i];
    if(S[i]!='a') cnt[i+1]++;
  }

  SuffixArray(S, N, 128, SA, NULL, mem);

  REP(i,1,N+1){
    if(S[SA[i]]=='a') continue;
    if(cnt[SA[i]] <= K){
      rep(j,SA[i]) if(S[j]!='a') S[j]='a', K--;
      break;
    }
  }
  rep(i,K) mypc('a');
  writerLn(S);

  return 0;
}

Current time: 2024年04月20日18時58分39秒
Last modified: 2016年02月05日22時07分39秒 (by laycrs)
Tags: Competitive_Programming AtCoder discovery2016-qual
トップページに戻る

Logged in as: unknown user (not login)

ログイン：