[editorial] IOI 2008 Day 1 - FISH

  • Kureyo
    Kureyo

    링크: http://acm.ajou.ac.kr:9041/JudgeOnline/showproblem?problem_id=1238
    spoiler="풀이열기" 설명의 편의를 위해서, 초기상태에 물고기의 뱃속에 들어있는 보석의 종류를 물고기의 종류라고 합시다.
    또한, 어떤 물고기 A가 먹을 수있는 물고기들의 집합을 G(A)라고 합시다. 이때 그 물고기의 뱃속에서 나올수 있는 조합의 갯수는
    ( G(A)속의 종류 1의 갯수 + 1 ) * ( .. 종류 2의 갯수 + 1 ) * ( .. 보석 K의 갯수 + 1) 이 될 것입니다.
    예를 들어서, 종류1 의 물고기A가 종류별로 각각 {3,2,4}마리의 물고기를 먹을 수 있을때 그 뱃속에서 나올수 있는 조합의 수는:
    1번 보석의 갯수는 1 ... 4 / 2번 보석의 갯수는 0 ... 2 / 3번 보석의 갯수는 0 ... 4
    로 4*3*5=60 가지입니다.
    (1) 어떤 동종의 물고기 A,B가 있다고 합시다. 이때 각 물고기의 길이를 L(A), L(B)라고 하고,
    L(A) ≥ L(B) 임을 가정합시다. B가 먹을 수 있는 물고기는 항상 A가 먹을 수 있기 때문에 G(A)⊇G(B)가 성립됩니다.
    거기에 더해서, A,B의 종류가 같기 때문에 B의 뱃속에서 나올 수 있는 조합은 항상 A의 뱃속에서 나올수 있습니다.
    여기에서 각 종류별로 가장 큰 물고기의 배에서 나올 수 있는 조합을 세어도 답이 될것임을 알 수 있습니다.
    앞으로는 각 종류별로 챔피언인 K마리의 물고기만이 다른 물고기를 먹는다고 생각하도록 하겠습니다.
    (2) 이제 서로 다른 종류의 가장 큰 물고기 K 마리만을 포식자로 남겨놓았습니다.
    그 가장 큰 물고기에 그 종류의 번호를 붙여서 부르도록 하겠습니다.
    예를들어 종류가 1번인 물고기 중 가장 큰 물고기를 1번물고기라 부르겠습니다.
    이번에도 서로 다른 종류의 N,M 두 물고기가 L(N) ≥ L(M)을 만족한다고 합시다. 역시 G(N)⊇G(M)이 성립할 것입니다.
    그러면 역시 M이 만들 수 있는 조합의 대부분이 N이 만들 수 있는 조합에 포함될 것입니다.
    그러나, N과 M이 각각 가지고 있는 고유의 보석의 종류가 다르기 때문에 M은 다음 2가지측면에서 차별화를 시도할 수 있습니다.
    case i. - 보석 N의 갯수를 0개 가질 수 있다 :
    물고기 N이 태생적인 한계[?] 때문에 항상 보석 N을 최소한 1개는 가져야하기 때문에,
    보석 N을 0개 가지는 경우가 있다면 이는 항상 물고기 N이 고려하지 않았던 경우입니다.
    case ii- 보석 M의 갯수를 N이 가진 최대값보다 한 개 더 많이 가질 수 있다 :
    L(M)이 꽤 클 때, 물고기 M이 '먹을 수 있는(자신이 가지고 있는 것은 제외하고)' 보석M의 갯수(노테이션이 헷갈리는군요-_-;)와
    물고기 N이 먹을 수 있는 보석 M의 갯수가 같을 수 있습니다. 이 경우에는 물고기M 자신이 갖고 있는 보석M을 보태서 최대값이
    N의 최대값보다 1 클 수 있는데, 이 역시 물고기 N이 고려하지 않았던 경우입니다.
    1번 케이스의 경우는 어떤 N과 M에 대해서도 가능하지만 2번 케이스의 경우는 몇몇 N과 M에 대해서만 성립합니다.
    극단적인 예로, N이 아예 M자체를 먹어 버릴 수 있다면 1번 케이스의 경우를 제외하고는 M의 어떤 조합도 N이 만드는 조합에
    포함될 것입니다. 정확히 말하자면, N이 물고기M이 먹을 수 없는 종류 M인 가장 작은 물고기(자기 자신을 포함해서)를 먹을 수 있다면
    2번 케이스는 성립할 수 없습니다.
    (3) 편의를 위해서 문제에 추가적으로 다음과 같은 가정이 있다고 하겠습니다:
    각 종류별로 가장 큰 물고기의 크기순으로 번호가 매겨져 있습니다. 즉, L(1)≥L(2)≥L(3)≥...≥L(K).
    (만약 그렇지 않은 경우에도, 위 조건을 만족하도록 보석의 번호를 다시 매길 수 있습니다.)
    또한 각 물고기 i가 먹을수 있는 보석 j의 갯수를 T(i,j)라 하고 T(i,j) = G(i)에 속하는 보석 j의 갯수라 정의하겠습니다.
    큰 순서대로, 즉 번호순으로 각 물고기가 만들 수 있는 '새로운' 조합을 고려하는 방법으로 접근하고자 합니다.
    임의의 x번째 물고기를 고려하는 경우를 생각해봅시다.
    1 ... x-1 번째 물고기까지는 고려되었고, x+1 ... k 번째 물고기는 고려되지 않았습니다.
    따라서, 앞에서부터 1...x에 대해서만 보석의 조합이 이전과 다르면, 그 뒤의 종류들은 (0)에서 고려했던데로
    { T(x, x+1) + 1 } * { T(x, x+2)+1 } * ... { T(x, k)+1 } 의 가짓수를 만들어 낼 수 있습니다. 반대로 1...x 의 보석의 조합이
    이전에 고려되었던 조합이면 그 뒤의 조합은 어떻게 되든 이미 고려되었던 조합이 됩니다.
    x의 관점에서 새로운 조합을 만들어 내는 방법은 (2)에서의 케이스들에서 살펴보았습니다.
    (0)에서 살펴보았듯이, x의 뱃속에서 나올 수 있는 보석 x의 갯수는 [1...T(x,x)+1] 입니다.
    이 중 T(x,x)+1 개가 나오는 경우를 제외하고는, 2번 케이스에 해당하지 않습니다.
    그러나 종류 1...x까지 보석의 갯수가 0개 나온다고 본다면 고려되지 않았던 조합을 만들어 낼 수 있습니다.
    이때 가능한 조합의 갯수는 { T(x, x+1) + 1 } * { T(x, x+2)+1 } * ... { T(x, k)+1 } => <1>
    T(x,x) +1 개가 나오는 경우에는 T(y,x) < T(x,x)+1 , y 이러한 y들은 이전에 고려되지 않았던것처럼 볼 수있으므로 { T(x,y)+1 } 만큼의 선택의 수가 늘어나게 됩니다.
    이 y들중 가장 작은 값을 min_y라고 하면, 역시 가능한 조합의 갯수는
    { T(x, min_y)+1 } * { T(x, min_y+1)+1 } ... * { T(x, x-1)+1 } * { T(x, x+1) + 1 } * { T(x, x+2)+1 } * ... { T(x, k)+1 } => <2>
    그런데, <1>은 [1...T(x,x)]에 대한 경우이므로 T(x,x)번 발생하고 <2>는 단 한번(T(x,x)+1)번 발생합니다.
    그러므로 각 x에 대해서,
    { T(x,x) } * { T(x, x+1) + 1 } * { T(x, x+2)+1 } * ... { T(x, k)+1 }

    • { T(x, min_y)+1 } * { T(x, min_y+1)+1 } ... * { T(x, x-1)+1 } * { T(x, x+1) + 1 } * { T(x, x+2)+1 } * ... { T(x, k)+1 }
      를 수행해주면 됩니다. 각 곱셈을 순서대로 해준다면 O(K*K)의 시간이 걸리는데, 우리의 친구 Indexed Tree를 사용하면 이를 O(K lg K)로 줄일 수 있습니다. 이번에도 글이 길었네요-_-; 항상 글이 장광설적으로 가는거 같습니다 ㅠㅠ [/spoiler] [spoiler="소스보기"]~~~ cpp

    #include
    #include
    #include
    #include
    using namespace std;
    const int _FMAX_=500000;
    typedef pair pii;
    int F,K,M;
    int Len[_FMAX_],Jew[_FMAX_],Rec[_FMAX_];
    int WhenRemoved[_FMAX_],Cnt[_FMAX_];
    pii Data[_FMAX_];
    inline int uinc(int a) { return (a+1)%M; }
    inline int udec(int a) { return (a+M-1)%M; }
    inline int umul(int a,int b) { return (a*b)%M; }
    bool lenst(int a,int b) {return Len[a] const int base=1<<19;
    struct prt
    {
    int node[1<<20];
    void set(int x,int v)
    {
    x+=base;
    node[x]=v;
    x>>=1;
    while (x)
    {
    node[x]=umul(node[x*2],node[x*2+1]);
    x>>=1;
    }
    }
    int prod(int a,int b)
    {
    a+=base; b+=base;
    int ret=1;
    while (a {
    if (a&1) {ret=umul(ret,node[a]); a++; }
    if (~b&1) {ret=umul(ret,node[b]); b--; }
    if (a>b) break;
    a>>=1;b>>=1;
    }
    if (a==b) ret=umul(ret,node[a]);
    return ret;
    }
    }DC;
    void reorder()
    {
    int q,c=0;//reorder
    for (q=0;q sort(Data,Data+F);
    for (q=0;q {
    Len[q]=Data[q].first;
    Jew[q]=Data[q].second;
    }//recolor
    for (q=0;q for (q=F-1;q>=0;q--)
    if (Rec[Jew[q]]<0) Jew[q]=Rec[Jew[q]]=c++;
    else Jew[q]=Rec[Jew[q]];
    }
    int main()
    {
    scanf("%d %d %d",&F,&K,&M);
    int q,w;
    for (q=0;q {
    scanf("%d %d",Len+q,Jew+q);
    Jew[q]--;
    }
    reorder();
    int col=-1,cursor=F-1,ret=0;
    for (q=0;q for (q=0;q for (q=F-1;q>=0;q--)
    if (Jew[q]>col)
    {
    col=Jew[q];
    while (cursor>=0)
    {
    if (Len[cursor]*2<=Len[q]) break;
    int &t=Jew[cursor];
    Cnt[t]--;
    DC.set(t,(Cnt[t]+1)%M);
    WhenRemoved[t]=col;
    cursor--;
    }
    int obj=WhenRemoved[col];
    int f=umul( DC.prod(obj,col-1) , DC.prod(col+1,K-1) );
    int g=umul( Cnt[col]%M , DC.prod(col+1,K-1) );
    ret=(ret+f+g)%M;
    }
    printf("%d\n",ret);
    return 0;
    }

    ~~~[/spoiler]

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]


    16년 전
3개의 댓글이 있습니다.
  • VOCList
    VOCList

    장대한남자 ㅠㅠ


    16년 전 link
  • yohani12
    yohani12

    이건 무슨 알고리즘을 통해서 푸는 문제이죠??


    16년 전 link
  • Kureyo
    Kureyo

    알고리즘이라기 보다는 거의 조합론적인 문제인거같습니다 ㅠㅠ
    저는 시간복잡도를 줄이기위해서 마지막에 자료구조로 BIT를 쓰기는 했지만요


    16년 전 link

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