Mirgon_s Programming

no arbitrage sequence exists

이 문제는 처음보면 조금 생각하기 어려운 문제입니다.
최단거리를 구하라고 했으니 최단거리를 구하겠는데...
더군다가 간 길은 또 갈 수 있고....
실제 값은 큰 걸 저장해야하니...말입니다.

그렇다면 생각을 조금 바꿔봐서...
큰 값을 저장하는 대신에 가는 edge에 제한을 걸면 어떻게 될까요?
그렇다면 최단거리를 구하는 것은 edge를 가장 적게 거친 애를 고르면 되는 것이고 값을 저장하는 것은 애시당초 큰 값을 저장한다고 했으니깐 되지 않을까요?

저렇게 하면 됩니다. ㅎ;
이 문제는 Floyd를 조금 바꾸는데요
Floyd는 최단거리를 구하는 알고리즘으로써
Floyd[i][j] = i~j까지 가는데에 최단거리라고 되어있습니다.
그렇다면......
Floyd[i][j] = i~j까지 가는데에 최장거리 ( 여기선 가장 큰 값으로 정의해야겠지요 ) 라고 하면 당연히 되지 않습니다. 왜냐하면 한바퀴 돌아서 큰값이 있다면 계속 돌면 돌수록 좋을테니깐요....
그러면...이제 edge에 제한을 걸어봅시다.
Floyd[i][j][k] = i~j까지가는데 k번의 edge를 거쳤을때( edge중복 가능 ) 이렇게 정의하면 됩니다.
점화식으로는
Floyd[i][j][k] = Floyd[i][l][k-1] * G(j,l) ( l = 1~n , G(a,b)는 a에서 b로 가는 edge의 값) 하면 됩니다.
(조금 허탕할까요 =ㅁ=ㅋ

#include <cstdio>
#include <vector>
const int NMAX = 20;
double a[NMAX+10][NMAX+10][NMAX+10];
int chase[NMAX+10][NMAX+10][NMAX+10];
int print[NMAX+10],pcnt;
void recur(int s,int p, int num)
{
    print[pcnt++] = p;
    
    if(num == 1)
        return;

    recur(s,chase[s][p][num],num-1);
}
void Aruray_Mirgon()
{
    //freopen("input.txt","rt",stdin);
    //freopen("output.txt","wt",stdout);

    int n,i,j,k,step,al;
    double temp;
    while(scanf("%d",&n) == 1){

        memset(a,0,sizeof(a));
        memset(chase,0,sizeof(chase));
        memset(print,0,sizeof(print));
        pcnt = 0;
        for(i=1;i<=n;i++){

            for(j=1;j<=n;j++){

                if(i == j){
                    a[i][j][1] = 1;
                    chase[i][i][0] = 1;
                    continue;
                }
                scanf("%lf",&a[i][j][1]);
                chase[i][j][1] = i;
            }
        }

        //floyd
        temp = 0;
        for(step = 2; step <= n; step ++ ){

            for(k = 1; k <= n; k ++ ){

                for(i = 1; i <= n; i ++ ){

                    for(j = 1; j <= n; j ++ ){

                        temp = a[i][k][step-1] * a[k][j][1];

                        if(temp > a[i][j][step]){
                            
                            a[i][j][step] = temp;
                            chase[i][j][step] = k;
                        }
                    }
                }
            }
        }

        al = 0 ;
        for(step = 2; step <= n; step ++ ){

            for(i = 1; i <= n; i++){

                if(a[i][i][step] > 1.01){
                    //score!
                    
                    print[pcnt++] = i;
                    recur(i,chase[i][i][step],step-1);
                    print[pcnt++] = i;
                    
                    al = 1;
                    for(j=pcnt-1;j>=1;j--)
                        printf("%d ",print[j]);
                    printf("%d",print[0]);
                    printf("\n");
                    break;
                }
            }
            if(al == 1)
                break;
        }
        //floyd
        if(al == 0)
            printf("no arbitrage sequence exists\n");
    }
}
void main()
{
    Aruray_Mirgon();
}

dynamic프로그래밍으로 문제가 쉽게 풀립니다.
그것도 1차원 다이나믹 프로그래밍으루요;
박스의 차원이 계속 늘어나기 때문에 상당히 어렵게 생각 할 수도 있는데 뭔가  Fake같은 겁니다.

일단 다이나믹의 부분문제를 쓰자면
D[i] =  i 상자를 포갰을 때의 최대 길이

D[i] = if( G(i,j) == 1 )
            max { D[j] }
j = 1 ~ i-1; G(i,j) 는 i가 j를 쌓을 수 있을 때 1를 리턴 아니면 0을 리턴

요런 식으로 해주시면 됩니다. (다이나믹 자체는 그다지 어렵지 않다고 생각합니다.

그럼 이제 저 함수 G가 문제되는데요...이 부분은 생각보다 매우 간단합니다. (저도 쪼금 해맸는데 ㅎ;;)
결론부터 말하자면 박스 i와 박스 j를 구성하는 숫자들을 정렬해 준후 순서대로 따지다가 박스 i의 숫자가 박스 j의 수보다 작다면 바로 리턴 0을 해주시면 됩니다.
이게 가능한 이유가

박스 i의 구성하는 숫자들을
i1 , i2 , i3 , i4 ... in (정렬 되어있다고 가정합니다.)
또 박스 j를 구성하는 숫자들을
j1 , j2 , j3, j4 ... jn이라고 하면

만약 어느 x지점에서 i의 숫자가 j의 숫자보다 작다고 해봅시다.
ix < jx 라고 가정한다면...jx를 커버 할 수 있는 숫자를 구하기 위해 ix+1를 가져와야만 할 것입니다. 그런데 ix+1를 가져오면요?;; jx+1를 커버할 수 있는 숫자가 없어집니다. 그럼 ix+2를 가져오고 등등 ... 가다보면 결국엔 jn을 커버할 수 있는 숫자가 없어지게 됩니다. 결국엔 둘의 값을 정렬해놓고 한개라도 커버할 수 없다면 둘은 서로 포개질 수 없는 상자가 되는 거지요...

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using std::sort;
using std::stable_sort;
const int N_MAX = 33;
const int M_MAX = 13;

struct fs{
    int first[M_MAX+5];
    int second;
};
fs a[N_MAX+5];
int chase[N_MAX + 5];
int dynamic[N_MAX + 5],n,m;
int print[N_MAX + 5],pcnt;
struct comp{

    bool operator () (const fs &fi , const fs &se){
        int j;

        for(j=m;j>=1;j--){

            if(fi.first[j] != se.first[j])
                return fi.first[j] < se.first[j];
        }
        return 1;
    }
}_comp;
struct comp_st{

    bool operator () (const int &fi, const int &se){

        return fi > se;
    }
}_comp_st;
int judge_can_pile(int p,int q)
{
    int i;
    for(i=1;i<=m;i++){

        if(a[p].first[i] >= a[q].first[i])
            return 0;
    }
    return 1;
}
void Aruray_Mirgon()
{
    //freopen("input.txt","rt",stdin);
    //freopen("output.txt","wt",stdout);
    int i,j,max,t,q,k;
    int temp[M_MAX+5];
    while(scanf("%d %d",&n,&m) == 2){


        memset(dynamic,0,sizeof(dynamic));
        memset(chase,0,sizeof(chase));
        for(i=1;i<=n;i++){ // box 수

            a[i].second = i; // number
            for(j=1;j<=m;j++){ // 차원

                scanf("%d",&a[i].first[j]);
            }

           
            //구성요소들을 정렬 해주기...
            for(j=1;j<=m;j++){
               
                for(k=j+1;k<=m;k++){

                    if(a[i].first[j] > a[i].first[k]){
                        t = a[i].first[j];
                        a[i].first[j] = a[i].first[k];
                        a[i].first[k] = t;
                    }
                }
            } // bubble...
            //근데 왜 여기서 STL _ sort 가 듣지 않는지 이해가 가질 않음 =ㅁ=;
            // 왜 안되는지 아시는 분은 http://arubirate.tistory.com으로 해결 방법좀요...
            //sort(a[i].first+1,a[i].first+m,_comp_st);
        }

        sort(a+1,a+n+1,_comp);

        /*for(i=1;i<=n;i++){

            for(j=1;j<=m;j++){

                printf("%d ",a[i].first[j]);
            }
            printf("\n");
        }*/

        //DP부분
        dynamic[n] = 1;
        chase[n] = -1;
        for(i = n-1; i >= 1; i--){

            max = 1; q = -1;
            for(j = i+1; j <= n; j++){

                t = judge_can_pile(i,j);
                if(t == 1){

                    if(max < dynamic[j]+1){
                        q = j;    max = dynamic[j] + 1;
                    }
                }
            }
            dynamic[i] = max;
            chase[i] = q;
        }
        //

        //역추적
        max = -1;
        for(i=1;i<=n;i++){

            if(dynamic[i] > max){
                q = i;    max = dynamic[i];
            }
        }

        printf("%d\n",max);

        pcnt = 0;
        while(q != -1){
           
            print[pcnt++] = a[q].second;
            q = chase[q];
        }
        //
        for(i=0;i<pcnt-1;i++)
            printf("%d ",print[i]);
        printf("%d",print[pcnt-1]);
        printf("\n");
    }
}
void main()
{
    Aruray_Mirgon();
}

#include <cstdio>
#include <algorithm>
#include <cstring>
using std::reverse;
const int NMAX = 100; // 이러면 100자리까지되는 거죠!
char a[NMAX+10],b[NMAX+10];
char c[NMAX*2+10]; // 곱하기 때문에 자리수가 2배로 늘어날수 있습니다.
char t;
int alen,blen,cw,clen;
// int형으로 잡아도되지만 굳이 char형으로 잡은 이유는 메모리를 조금이나마 아껴보자는 생각...
void Aruray_Mirgon()
{
    freopen("input.txt","rt",stdin);
    freopen("output.txt","wt",stdout);
    //부호 안되는 version입니다...
    //부호는 너무 어려버요 ㅎ ^^;;
    int i,count;
    scanf("%s ",a);
    scanf("%c ",&t); // t는 부호!
    scanf("%s",b); // 입력받음!
    //입력 형식은 숫자 부호 숫자로 해주세요
    //ex) 3282457 + 2405245904250
    alen = strlen(a);
    blen = strlen(b);
    for(i=0;i<alen;i++){
        a[i] -= '0'; b[i] -= '0'; } // 진짜 숫자로 만들어줍니다.

    reverse(a,a+alen);
    reverse(b,b+blen); // 계산의 편의상 수를 뒤집어줍니다...
    //배열 0이 일의자리수 배열 1이 십의자리수...가는거죠...
   
    count = 0; cw = 0;
    if(t == '+'){// plus!
        while(count < alen || count < blen) //두수의 길이가 끝날때 까지...
        {
            c[count] += (a[count]+b[count])%10;
            c[count+1] += (a[count]+b[count])/10;
            cw = count;
            while(c[cw] >= 10){ // 반올림을 힘차게 해보아요 'ㅁ';
                c[cw+1] += c[cw]/10;
                c[cw] = c[cw] % 10; cw++;
            }
            count++;
        }
    }

    //오늘 너무 피곤해요 데렌님 더하기만 ㅜㅡ;;바주세요;;
    if(t == '-') // minus!
    {
    }
    if(t == '*')
    {
    }
    /*if(t == '/'){ // 개인적으로 나누기는 못 합니다...
    큰수 하나만 가지고 작은수로 나눌 땐 해도 큰수 2개를 하면 잘 못하겠더군요...
    나중에 차근차근 생각해봐서 올리도록 하겠습니다...
    }*/
    for(i=200;i>=0;i--){
        if(c[i] != 0){ clen = i; break;}
    }
    for(i=clen;i>=0;i--)
        printf("%d",c[i]);

}
void main()
{
    Aruray_Mirgon();
}

말할 것도 없센...
그닥...노가다하셔도되고 백트하셔도되고...(저는 백트...)
O(1)만에 푸는 방법도 있으리라고 보지만 그다지 고민 안하셔도 될 것 같습니다...'ㅁ';;
개인적으론 봤을 땐 별 도움 안 될 것 같더군요

#include <cstdio>
int b[5],g[5],c[5];
int check[5],order[5],a[5];
int bs,gs,cs,sum,answer;
void recur(int p)
{
    int i;
    if( p == 3 )
    {
        sum = 0;
        for(i=0;i<3;i++)
        {
            if(order[i] == 0){
                sum += bs - b[i]; }
            else if(order[i] == 1){
                sum += cs - c[i]; }
            else if(order[i] == 2){
                sum += gs - g[i]; }
        }

        if(answer > sum)
        {
            answer = sum;
            a[0] = order[0]; a[1] = order[1]; a[2] = order[2];
        }
    }
    for(i=0;i<3;i++)
    {
        if( !check[i] )
        {
            check[i] = 1;
            order[p] = i;
            recur(p+1);
            order[p] = 0;
            check[i] = 0;
        }
    }
}
void Aruray_Mirgon()
{
    //freopen("input.txt","rt",stdin);
    //freopen("output.txt","wt",stdout);
    int i;
    while(scanf("%d %d %d %d %d %d %d %d %d",
        &b[0],&g[0],&c[0],&b[1],&g[1],&c[1],&b[2],&g[2],&c[2]) == 9)
    {
        bs = b[0]+b[1]+b[2]; gs = g[0]+g[1]+g[2]; cs = c[0]+c[1]+c[2];
        answer = 2100000000;
        recur(0);
        for(i=0;i<3;i++)
        {
            if(!a[i])
                printf("B");
            else if(a[i] == 1)
                printf("C");
            else if(a[i] == 2)
                printf("G");
        }
        printf(" %d\n",answer);
    }
}
void main()
{
    Aruray_Mirgon();
}

전형적인 노가다문제라고 볼 수있는데...
한가지 조언을 하자면... 이문제는 왠만하면 함수를 사용하여 소스를 깔끔하게 정리하는 것이 좋다고 생각됩니다.
지저분하게 main에 일일이 다 때려넣어서하면 ... 상당히 오류찾을 때 애를 먹기 때문입니다 ... (경험해봤심 ㅜㅜ)

#include <cstdio>
#include <cstring>
#include <vector>
const int NMAX = 25;
int block[NMAX+10][NMAX+10]; // 지금 블록들의 모임상태
int bcnt[NMAX+10];
int place[NMAX+10]; // 각 블록의 번호가 어떤 위치에 있는지
int name2(char *o) // o가 onto인지 over인지 구별
{
    if(strcmp(o , "onto") == 0)
        return 1;
    else
        return 0;
}
void later_clear( int p ) // p 블록 위에있는 것들을 처리한다
{
    int t = place[p],q;
    int i,k;
    for(i=0;i<bcnt[t];i++){

        if(block[t][i] == p){
           
            k = i;    break;
        }
    }

    for(i=bcnt[t]-1;i>k;i--){
       
        q = block[t][i];
        block[q][bcnt[q]++] = q;
        place[q] = q;
        block[t][--bcnt[t]] = 0;
    }
}
void search_pile( int p1 , int p2 ) // p블록의 위치를 찾아 준다
{
    int t = place[p1], q;
    int i,k;
    for(i=0;i<bcnt[t];i++){

        if(block[t][i] == p1){

            k = i; break;
        }
    }

    q = place[p2];
    for(i=k ; i < bcnt[t] ; i++){
        block[q][bcnt[q]++] = block[t][i];
        place[block[t][i]] = q;
        block[t][i] = 0;
    }
    bcnt[t] = k;
}
void Aruray_Mirgon()
{
    //freopen("input.txt","rt",stdin);
    //freopen("output.txt","wt",stdout);
    int n,p1,p2,i,t,j;
    char s[10],o[10];
   
    scanf("%d",&n);
    for(i=0;i<n;i++){ // 초기화
       
        block[i][bcnt[i]] = i;
        place[i] = i;
        bcnt[i] = 1; }

    while(1)
    {
        scanf("%s",s);
        if(strcmp(s,"quit") == 0)
            break;
        scanf("%d %s %d",&p1,o,&p2);
        if(p1 == p2 || place[p1] == place[p2])
            continue;
        if(strcmp(s,"move") == 0){
           
            if( name2(o) ){ // onto가 입력되면

                later_clear(p1);
                later_clear(p2);
                t = place[p1];
                block[t][--bcnt[t]] = 0;
                t = place[p2];
                block[t][bcnt[t]++] = p1;
                place[p1] = t;
            }

            else{ // over

                later_clear(p1);
                t = place[p1];
                block[t][--bcnt[t]] = 0;
                t = place[p2];
                block[t][bcnt[t]++] = p1;
                place[p1] = t;
            }
        }
        if(strcmp(s,"pile") == 0){
           
            if( name2(o) ){ // onto
               
                later_clear(p2);
                search_pile(p1,p2);
            }

            else{ // over

                search_pile(p1,p2);
            }
        }
    }
    for(i=0;i<n;i++)
    {
        printf("%d:",i );
        for(j=0;j<bcnt[i];j++)
            printf(" %d",block[i][j]);
        printf("\n");
    }
}
void main()
{
    Aruray_Mirgon();
}