모두들 메리크리스마스 N 해피뉴이어~ 는 개뿔 -_- PKU 1989. The Cow Lineup. [판정:TLE]

흑흑
같이 바람쐬러 나갈 여친 없는 것도 모자라서
저녁에 [군인놈 1명 공익놈 1명 예비역 1명]들과 모여서 술마시기로 했음

더러운 세상 ㅋㅋㅋㅋㅋㅋ

처음의 CE는 main함수의 return type이 void인 탓에 :(

기본 아이디어는 solving process에 올려서 트랙백을 달든지 하겠구요 -_-;

그 아이디어를 바탕으로 처음 끄적거렸던게 아래의 소스이고,

#include <iostream> int N, K; int *cows; int seek( int ary[] ); void main() { int i; scanf("%d %d", &N, &K); cows = new int[N]; for( i = 0; i < N; i++ ) { scanf("%d", &cows[i]); } printf("%d\n", seek(cows)); } int seek( int ary[] ) { int i, j, k; bool *table; // 1 digit sequence table = new bool[K]; for( i = 0; i < N; i++ ) { table[ ary[i]-1 ] = true; } for( i = 0; i < K; i++ ) if( table[i] != true ) return 1; delete[] table; // 2 digits sequence table = new bool[K*K]; // K square, simplify index for( i = 0; i < N-1; i++ ) // simplify upper bound of i { for( j = i+1; j < N; j++ ) // simplify lower bound of j { table[ (ary[i]-1)*K + (ary[j]-1) ] = true; // simplify index } } for( i = 0; i < K*K; i++ ) if( table[i] != true ) return 2; // simplify upper bound of i delete[] table; // 3 digits sequence table = new bool[K*K*K]; // K cube, simplify index for( i = 0; i < N-2; i++ ) // simplify upper bound of i { for( j = i+1; j < N-1; j++ ) // simplify lower bound of j, upper bound too { for( k = j+1; k < N; k++ ) // simplify lower bound of k { table[ (ary[i]-1)*K*K + (ary[j]-1)*K + (ary[k]-1) ] = true; // simplify index } } } for( i = 0; i < K*K*K; i++ ) if( table[i] != true ) return 3; // simplify upper bound of i delete[] table; //... and so on, to N digits sequence return N+1; }


이것을 부분수열의 길이에 상관없이 돌아가도록 반복문으로 바꾸고, 제출한 소스가 아래의 것입니다
(코드 중간에 C언어용 주석(/* */)으로 처리된 부분은 제출할 때 지웠습니다)

#include <iostream> int N, K; int *cows; int seek( int ary[] ); int main() { int i; scanf("%d %d", &N, &K); cows = new int[N]; for( i = 0; i < N; i++ ) { scanf("%d", &cows[i]); } printf("%d\n", seek(cows)); return 0; } int seek( int ary[] ) { int i, j, k; bool *table; int *dum = new int[N+1]; // N dummy variables, dum[0] is sentinel int power = 1; // K's exponent, caution: overflow for( i = 1; i <= N; i++ ) { for( j = 0; j <= N; j++ ) dum[j] = 0; power *= K; table = new bool[power]; for( j = 1; j <= i; j++ ) { dum[j] = j-1; } while( dum[0] == 0 ) { int tabi = 0; // table index int tabpo = 1; // K's exponent for tabi, caution: overflow for( k = 0; k < i; k++ ) { // calculating tabi tabi += ( ary[dum[i-k]]-1 ) * tabpo; tabpo *= K; } table[tabi] = true; // index addition & arrange dum[i]++; for( k = 0; k < i; k++ ) /* 1st for */ { if( dum[i-k] == N-k ) dum[i-k-1]++; } for( k = 1; k <= i; k++ ) /* 2nd for */ { if( dum[k] == N+k-i ) break; // original condition: dum[k] == N-(K-k)+(K-i) } for( ; k <= i; k++ ) dum[k] = dum[k-1] + 1; /* 3rd for */ /* example N = 5, K = 3 => indices = 0~4 3 digits sequence (i = 3) dum1 = 0~2, dum2 = 1~3, dum3 = 2~4 => [dum1 dum2 dum3] => [0 1 2] => [0 1 3] => [0 1 4] => [0 1 5] => [0 2 5] because 1st for repeatation above => [0 2 3] because 2nd and 3rd for repeatation above => [0 2 3] => [0 2 4] => [0 2 5] => [0 3 5] because 1st for repeatation above => [0 3 4] because 2nd and 3rd for repeatation above => [0 3 4] => [0 3 5] => [0 4 5] because 1st for repeatation above => [1 4 5] because 1st for repeatation above => [1 2 3] because 2nd and 3rd for repeatation above ... and so on, to [2 4 5] => [3 4 5] => dum[0]++ => exit while repeatation */ } for( j = 0; j < power; j++ ) { if( table[j] != true ) return i; } delete[] table; } return N+1; }


천상 TLE 또는 WA를 받을 것 같긴 했지만, 막상 레알로 TLE를 받고 나니 막막하군요 ㅋㅋㅋㅋㅋㅋ