algospot.com :: 과거 게시판: [editorial] 2007년 서울 온사이트 본선 H번 Puzzle

[editorial] 2007년 서울 온사이트 본선 H번 Puzzle

Kureyo
- 문제 요약 - A부터 시작되는 n개의 알파벳을 가지고 문자열을 구성합니다. 구성된 문자열은 s개의 금지문자열을 포함하면 안 됩니다. 이때 구성 가능한 최대길이의 문자열은? [ 최대길이가 여러개 있으면 사전순으로 가장 큰것을 출력해야합니다. ] 전제조건은 다음과 같습니다. n<=26, s<=1000, 각 금지문자열의 길이<=50 (* 만약 가능한 길이가 무한히 길거나 가능한 문자열이 (null)뿐이면 No를 출력해야합니다.)
- 풀이 - 문자열에 한 글자를 뒤에 덧붙여서 계속해서 문자열을 확장시켜나가는 경우에 대해 생각해봅시다. 이 문자열이 금지문자열을 단 하나도 포함하고 있지않다면 우리는 그 문자열의 뒤에서부터의 일부 에만 관심을 가져도 됩니다. 간단한 예로 모든 금지문자열이 10글자 이내라면 우리는 만든 문자열의 마지막 9글자만에 대해서만 알고 있어도 어떤 확장이 금지문자열을 만드는지 안 만드는지 확인할 수 있습니다. 더 생각해보면 현재까지 만든 문자열의 suffix와 금지문자열의 prefix가 일치하는 것 중 가장 긴 것 만을 저장해도 된다는 것을 알 수 있습니다. 이를 문자열의 상태라고 하면, 앞에 어떤 문자가 오던지 같은 상태에서 뒤에 덧붙일 수 있는 최대길이는 항상 같을 것입니다. 가능한 상태의 개수는 금지문자열 preifx들의 집합의 크기이고 이는 모든 금자문자열의 길이의 합보다 작습니다. 모든 상태가 정의가 되었으니 각 상태의 관계에 대해서 생각해봅시다. 각 상태에서 어떠한 글자를 덧붙이면 이는 또 다른 상태(혹은 자기 자신으로)로 변경이 될것입니다. 각 상태를 하나의 node로 또한 상태간의 관계를 edge라 생각하면 이를 directed graph와 같이 나타낼수 있을 것입니다. 같은 금지문자열에 속해있는 한 글자 차이나는 prefix 들간의 관계는 명백합니다. 금지문자열에 { ACGTACGT, CGACGA } 일때 ACG의 T확장은 ACGT이지요. 하지만 ACG에 T가 아닌 A를 붙인다면 ACGA가 되는데 ACGA를 prefix로 갖는 금지문자열은 없으므로 위에서의 정의에 따라 ACG의 A확장은 CGA가 됩니다. 대회때는 이에 해당하는 문자가 없다면 앞에서부터 한 글자씩 제거하며 찾았습니다만ㅠ_ㅠ(결과는 TLE) 이보다 빠른 방법을 생각해봅시다. ACG에 A를 붙이든 B를 붙이든 C를 붙이든 전부 해당하는 prefix가 없기 때문에 CGA GA A를 체크해보고 CGB GB B를 체크해보고 CGC GC C를 체크해봐야합니다. 그런데 방법을 바꿔서 CG를 찾고 G를 찾고 (null)을 찾고를 반복해서 그 중 존재하는 것을 찾았다고 했을때 그것의 A,B,C확장을 찾으면 매번 검사할 필요없이 단 한번 찾아서 이것의 확장을 가져오면 됩니다. 즉 첫글자를 제외한 문자열(이 경우 "CG"가 됩니다)에서 가능한 최대 길이의 suffix가 하나의 상태랑 일치하는 상태를 찾아서 이것의 확장을 자신의 확장으로 가져옵니다. 이것을 편의상 nonhead라고 합시다. 이제 각 노드(상태)의 nonhead 노드(상태)를 찾아낸다면 O(|V|*n)시간에 그래프를 구성할 수 있습니다. nonhead를 찾는 빠른 방법에 대해 생각해봅시다. 상태들은 가능한 prefix들의 집합입니다. 그러므로 (null)을 제외한 모든 상태에서 그 상태의 마지막 문자를 제외한 문자열 또한 상태에 항상 포함되어 있습니다. 그 상태를 원 상태의 nontail이라고 할 때, 이는 모든 상태를 구하면서 한 번에 알아낼 수 있습니다. 어떤 노드 A와 그것의 nontail 노드 B, 각각의 nonhead노드인 An과 Bn이 있다고 합시다. A와 B의 관계는 B에서 A의 마지막 글자로 확장한 것이 A를 가르키는 관계입니다. 또한 이것은 An과 Bn에서도 성립합니다. Bn에서 A의 마지막 글자를 확장하면 이는 An이 될 것 입니다. B노드는 항상 A노드보다 짧기 때문에 길이가 1인 원소들의 nonhead가 (null)이라는 것만 정의해주면 모든 노드의 nonhead를 이 관계를 이용해서 밝혀낼수 있습니다. 그러므로 미리 구해둔 nontail노드들을 이용해 모든 노드들의 nonhead 노드를 찾아내는데 걸리는 시간은 O(|V|)입니다. 그래프를 구성하는데 걸린 시간은 O(|V|*n)입니다. ( |V| = 상태의 갯수 <= 1000*50 ) 드디어-_-; 우리의 문제로 돌아와봅시다. 우리의 문제는 가능한 긴 문자열을 만드는 것이었습니다. 가능한 긴 문자열을 만들기 위해서는 시작 노드 (null)에서 최대한 긴 연속적인 확장을 찾아야하고, 확장은 그래프에서의 에지이므로 원 문제는 모든 가중치가 1인 방향그래프에서 시작점이 주어졌을 때의 최장거리를 구하는 문제가 됩니다. 만약 사이클이 존재한다면, 최장거리가 정의되지않습니다.( => 가능한 문자열의 길이가 무한합니다.) 만약 사이클이 존재하지 않는다면, 그래프는 acylic graph이므로 편한 방법으로 푸시면 됩니다. :) 제 경우는 사이클을 찾는데 dfs를 돌리고 없으면 topology sort를 하였습니다만, 생각해보니 dfs를 잘 고쳐서 사이클도 찾고 최장거리도 찾게하면 더 코딩도 간결해질거 같아서 새로 짜보았습니다. 시간복잡도는 역시 O(|V|*n)=O(n*s*L)이 됩니다. ( |E| = |V|*n , O(|V|+|E|)=O(|V|*n) ) 오토마타를 제가 정식으로 배웠다면 조금더 쉽게 쓸 수 있었을거 같은데 모르는 채로 제가 떠올린 것들을 전부 옮겨 적다보니 본의아니게 스크롤이 길어졌습니다. (_ _)
```
// seoul regional 2007
// H. puzzle
#include <algorithm>
#include <cstdio>
#include <cstring>
#define _NMAX 1000
#define _LMAX 50
using namespace std;
int C,N,V;
int Last[ _NMAX ],Length[ _NMAX ];
char Res[ _NMAX ][ _LMAX+1 ];
struct node
{
    int visit,maxdist; // for find maximum distance from v ... dfs
    int forward[26];
    int nontail,nonhead,tail;
    int forbidden;
    void init() { int q; visit=maxdist=forbidden=0; nonhead=nontail=-1; for (q=0;q<C;q++) forward[q]=-1; }
};
node Prefix[ _NMAX * _LMAX ];
int dfs(int v);
inline int newnode() {  Prefix[V].init();return V++; }
int main()
{
    int T;
    scanf("%d",&T);
    for (;T;T--)
    {
        V=0;
        scanf("%d %d",&C,&N);
        int q,w;
        int u,v,tail;
        newnode();
        for (q=0;q<N;q++) { scanf("%s",Res[q]); Length[q]=strlen(Res[q]); Last[q]=0; }
        for (q=0;q<_LMAX;q++)
            for (w=0;w<N;w++)
            {
                if (Length[w]<=q) continue;
                u=Last[w];
                tail=Res[w][q]-'A';
                if (Prefix[u].forward[tail]<0) 
                { 
                    v=newnode(); 
                    Prefix[u].forward[tail]=v; 
                    Prefix[v].nontail=u; 
                    Prefix[v].tail=tail;
                    Last[w]=v;
                }
                else Last[w]=Prefix[u].forward[tail]; //always a shorter prefix's # is smaller than a longer one's
            }
            for (q=0;q<N;q++) Prefix[ Last[q] ].forbidden=1;
            //make graph
            for (q=0;q<C;q++) Prefix[0].forward[q]=max( Prefix[0].forward[q], 0 );
            for (q=1;q<V;q++)
            {
                if (Prefix[q].nontail==0) Prefix[q].nonhead=0;
                else 
                {
                    int &waist = Prefix[ Prefix[q].nontail ].nonhead;
                    Prefix[q].nonhead=Prefix[waist].forward[ Prefix[q].tail ]; // prefix = head + waist + tail
                }
                Prefix[q].forbidden= Prefix[q].forbidden | Prefix[ Prefix[q].nonhead ].forbidden | Prefix[ Prefix[q].nontail ].forbidden;
                for (w=0;w<C;w++) if (Prefix[q].forward[w]<0) Prefix[q].forward[w]=Prefix[ Prefix[q].nonhead ].forward[w];
            } 
            //find maximum distance
            int t=dfs(0);
            if (t<=1) printf("No\n"); 
            else 
            {
                for (u=0,q=t-1;q>0;q--) // except last prefix ( = forbidden word )
                    for (w=C-1;w>=0;w--)
                    {
                        v=Prefix[u].forward[w];
                        if ( Prefix[v].maxdist == q) { u=v; printf("%c",(char)w+'A'); break; }
                    } 
                    printf("\n");
            }
    }
    return 0;
}
int dfs(int u) //return maximum distance from u... if meet cycle return -1.
{
    if (Prefix[u].forbidden) return 0;
    Prefix[u].visit=1;
    Prefix[u].maxdist=0;
    int q,v,t;
    for (q=0;q<C;q++)
    {
        v=Prefix[u].forward[q];
        if (Prefix[v].visit==1) return -1; //cycle
        if (Prefix[v].visit==2) t=Prefix[v].maxdist; //already visited
        else t=dfs(v);
        if (t<0) return -1; //cycle
        if (t+1>Prefix[u].maxdist) Prefix[u].maxdist=t+1;
    }
    Prefix[u].visit=2;  
    return Prefix[u].maxdist;
}

~~~<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/5570">원문보기</a>]</div>
```
16년 전

3개의 댓글이 있습니다.

Kureyo

http://acm.pku.edu.cn/JudgeOnline/problem?id=2778 도 한 번 풀어보세요 :$

16년 전 link
cancho

2778번 정말 힘들게 짰던 문제네요 ;ㅁ;
덕분에 오기로 11번 섭밋해 fastest(?)를 찍었죠-_-
http://koi4u.byus.net/moi/20060604/p7.htm
저처럼 영어에 울렁증이 있으신 분들은 저걸 보셔도...

16년 전 link
Kureyo

nonhead구하는것이 전제가 잘못되어서 편집했습니다 ;ㅅ; (그림도 첨부)

16년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.

Kureyo: http://acm.pku.edu.cn/JudgeOnline/problem?id=2778 도 한 번 풀어보세요 :$

16년 전 link

cancho: 2778번 정말 힘들게 짰던 문제네요 ;ㅁ;
덕분에 오기로 11번 섭밋해 fastest(?)를 찍었죠-_-
http://koi4u.byus.net/moi/20060604/p7.htm
저처럼 영어에 울렁증이 있으신 분들은 저걸 보셔도...

16년 전 link

Kureyo: nonhead구하는것이 전제가 잘못되어서 편집했습니다 ;ㅅ; (그림도 첨부)

16년 전 link

정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.

SINCE 2007

다가오는 이벤트들

[editorial] 2007년 서울 온사이트 본선 H번 Puzzle

3개의 댓글이 있습니다.