AOJ 2324: Full Text Search

この記事は、AOJ-ICPC Advent Calendarの記事です。

まず、文字一つ一つを頂点としたグラフだと思って2つの隣り合う文字にたいして辺をはります。重複辺はつけなくていいです。
このグラフに辺を付け足す必要があれば付け足してオイラー路を作ってやるという見方をすると、後は「このケースはこう」みたいなのがいくつかあるので、それを調べます。コード中で一番オイラー路オイラー路している場所(87~110行目くらい)では、オイラー路が2種類以上存在しているかどうかを判定しています。
頂点数が52しかないので、かなり適当にオイラー路を構成できます。

#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
char str[1100];
int c[1100];
int g[60][60];
int G[60][60];
int in[60];
int out[60];
int UF[60];
int FIND(int a){
    if(UF[a]<0)return a;
    return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
    a=FIND(a);b=FIND(b);if(a==b)return;UF[a]+=UF[b];UF[b]=a;
}
int liv[60];
bool chk(int at){
    for(int i=0;i<60;i++)UF[i]=-1;
    for(int i=0;i<60;i++)liv[i]=0;
    for(int i=0;i<60;i++)for(int j=0;j<60;j++){
        if(G[i][j]){
            liv[i]=liv[j]=1;
            UNION(i,j);
        }
    }
    for(int i=0;i<60;i++)for(int j=0;j<60;j++)if(liv[i]&&liv[j]&&FIND(i)!=FIND(j))return false;
    for(int i=0;i<60;i++)if(liv[i]&&FIND(at)!=FIND(i))return false;
    return true;
}
int L[5100];
int R[5100];
int main(){
    while(1){
        scanf("%s",str);
        if(str[0]=='#')return 0;
        int n=strlen(str);
        if(n<=2){
            printf("No Results\n");continue;
        }
        for(int i=0;i<60;i++)for(int j=0;j<60;j++)g[i][j]=0;
        for(int i=0;i<n;i++){
            if('a'<=str[i]&&str[i]<='z')c[i]=str[i]-'a';
            else c[i]=str[i]-'A'+26;
        }
        for(int i=0;i<n-1;i++)g[c[i]][c[i+1]]=1;
        for(int i=0;i<60;i++)in[i]=out[i]=0;
        int m=0;
        for(int i=0;i<60;i++)for(int j=0;j<60;j++){
            if(g[i][j]){
                m++;
                in[j]++;out[i]++;
            }
        }
        int pc=0;
        int mc=0;
        int pt=0;
        int pa=0;
        int ma=0;
        for(int i=0;i<60;i++){
            if(out[i]>in[i]){
                pc++;pt+=out[i]-in[i];
                pa=i;
            }else if(in[i]>out[i]){
                mc++;
                ma=i;
            }
        }
        for(int i=0;i<5100;i++)L[i]=R[i]=0;
    //  for(int i=0;i<60;i++)if(in[i]||out[i])printf("%d %d\n",in[i],out[i]);
    //  printf("%d %d %d %d\n",pc,mc,pt,pa);
        if(pc==0&&mc==0){
            printf("%d\n",m+1);continue;
        }
        int ret=m+pt;
        if(pc>1||mc>1){
            printf("%d\n",ret);continue;
        }
        g[ma][pa]+=pt-1;
        m+=pt-1;
        int at=pa;
        for(int i=0;i<60;i++)for(int j=0;j<60;j++)G[i][j]=g[i][j];
         
        for(int i=0;i<m;i++){
            for(int j=0;j<60;j++){
                if(!G[at][j])continue;
                G[at][j]--;
                if(chk(j)){
                    at=j;
                    L[i]=j;
                    break;
                }else G[at][j]++;
            }
        }
        at=pa;
        for(int i=0;i<60;i++)for(int j=0;j<60;j++)G[i][j]=g[i][j];
        //for(int i=0;i<m;i++)printf("%d %d\n",L[i],R[i]);
        for(int i=0;i<m;i++){
            for(int j=59;j>=0;j--){
                if(!G[at][j])continue;
                G[at][j]--;
                if(chk(j)){
                    at=j;
                    R[i]=j;
                    break;
                }else G[at][j]++;
            }
        }
    //  for(int i=0;i<m;i++)printf("%d %d\n",L[i],R[i]);
        bool ok=false;
        for(int i=0;i<m;i++){
            if(L[i]!=R[i])ok=true;
        }
        if(m+1<n)ok=true;
        if(ok)printf("%d\n",m+1);
        else printf("%d\n",m+2);
    }
}