이번에도 부진했다. 2008 년 11월 부터는 계속 gray 에 머문듯... ㅠㅠ

Level1 만 간신히 풀고 룸 9등, Div 379/609 였다. Rating 은 799 (+23) 로 소폭 상승했다.

Level1 - KnockoutTourney ( 168.52 Passed System Test )
1 번부터 N 번까지 플레이어를 나열해 놓고 인접한 숫자의 2 명씩 짝지어서 토너먼트를 벌인다. 당신과 당신의 라이벌 번호표가 주어질 때, 당신이 라이벌과 만나는 것은 몇번의 토너먼트 게임이 이루어 진 후인지를 계산하는 문제이다. 실제 SRM 에서는 배열을 잡아놓고 토너먼트를 시뮬레이션 하면서, 같은 게임 군에 속하는 플레이어들을 같은 값으로 매핑하는 형태로 꽤나 복잡하게 풀었다. 사실은 배열도 필요없고, 1-2, 3-4 에서 1-4, 5-8 ... 과 같이 매 게임마다 커버되는 플레이어 번호의 범위를 증가시키면서 당신과 라이벌이 같은 범위에 들어오는 순간만 체크하면 된다.

class KnockoutTourney { public: int meetRival( int N, int you, int rival ) { int idx, r = 2, ret = 1; while(1) { idx = 1; while(1) { if(( you >= idx && you < idx+r ) && ( rival >= idx && rival < idx+r )) return ret; idx += r; if( idx >= N ) break; } r *= 2; ret++; } return ret; } };

포럼을 보니 Petr 은 아래와 같이 간단하게 풀었다. ㅠㅠ
struct KnockoutTourney { int meetRival(int n, int y, int r) { return log2(--y ^ --r) + 1; } };

Level2 - ShufflingMachine ( Opended )
문제 description 이 도통 이해가 안가던 문제. 한참 읽어봐도 이해가 안가다가 helloneo 의 해석을 읽고 겨우 문제를 이해했다. 내용을 이해해보니 단순 시뮬레이션 문제였다. ( 그래서 Div2의 경우 submit 비율은 낮지만 submit 한 사람들의 성공률은 꽤나 높았다. )

카드를 셔플하는 방법이 shuffle 벡터로 주어지고, 최대 셔플 횟수가 주어진다. 당신은 초기 카드 배치를 자유롭게 할 수 있다. ( 이 말이 의미하는 것은 결국 최종적으로 셔플한 후에 받는 카드의 순서는 마음대로 할 수 있다는 뜻이 된다. ) 셔플이 끝난 후 특정 slot 의 카드들을 받는다 할때, 자신이 원하는 카드를 받을 기대값을 구하는 문제이다.

실제 시뮬레이션으로 매번 shuffle 을 하면서, 매 shuffle 마다 카드를 받을 수 있는 slot 에 들어오는 카드의 인덱스들을 카운트 한다. 그리고 난 후 소트하여 ( 소트를 해도 되는 이유는 앞서 말했듯이 원하는 카드의 순서를 자유롭게 배치할 수 있기 때문이다 ) 가장 많이 등장하는 카드들의 숫자를 센 후, shuffle 횟수로 나누면 기대값이 된다. 매번 shuffle 마다 받을 수 있는 카드의 갯수를 구할 수 있으므로, 매 shuffle 하면서 받을 수 있는 가장 많은 카드의 갯수를 모두 더한 후, 이 값을 shuffle 로 전체를 나누면 된다.

class ShufflingMachine { public: double stackDeck( vector <int> shuffle, int maxShuffles, vector <int> cardsReceived, int K ) { int a, b, get, sum; get = sum = 0; vector<int> count(shuffle.size(), 0); vector<int> card(shuffle.size(), 0); vector<int> card1(shuffle.size(), 0); for( a = 0; a < shuffle.size(); a++ ) card[a] = a; for( a = 0; a < maxShuffles; a++ ) { // shuffle for( b = 0; b < shuffle.size(); b++ ) card1[shuffle[b]] = card[b]; card = card1; // 셔플이 끝난 후, cardsReceived 슬롯에 있는 카드의 갯수를 센다. for( b = 0; b < cardsReceived.size(); b++ ) { count[card[cardsReceived[b]]]++; } } sort(count.begin(), count.end()); for( a = count.size()-1; a >= 0 && K > 0; a--, K-- ) { get += count[a]; } return (double) get / (double) maxShuffles; } };
Level3 - DistinctDigits ( Opened )
Not Yet.

이올린에 북마크하기

개인적으로 대단히 기억에 남는 SRM 이다.
우선, ACM-ICPC 대회 예비소집일에 있던 SRM 이란 점.
이날 어찌나 바쁘던지... 낮부터 저녁까지 예비소집에 다녀온 후에, 밤에는 학교에 가서 특별 세미나 수업을 듣고, 8시에 끝나자마자 바로 부랴부랴 집에와서 TopCoder Arena 에 접속해 보니 이미 SRM 은 시작한지 10 여분이 지난 상태였다.

어쨌든 이날 나온 문제들이 쉬운 편이라 나름 기대를 하면서 열심히 풀었지만... 결과는 씁쓸하다.
Level 1 통과, Level 2 는 한가지 착각을 해서 첼 당하고, Level 3 도 시간만 있었으면 충분히 풀수 있었는데...

특히나 Level 2 를 첼린지 한 사람이 학교 후배이자 ACM-ICPC 대회장에서 만날 녀석이란 점에서 무척이나 부담이 되었다. -0-;; 
( 그래서 ACM-ICPC 대회 성적이 아쉽게 나왔나?? 그나마 위안? 이 되는 건 이 후배는 ACM-ICPC 대회 성적으로 이겼다 -0- )

룸 11등, Div 438/740, Rating 은 824(-19) 로 다시 하락했다... ㅋ

Level 1 - MagicSpell ( Coding Time 09:33, 225.55 Passed System Test )
쉬운 문제인데 파악에 시간이 좀 걸렸다.
간단한 형태의 encryption 과 decryption 하는 것을 묻는데, 임의의 스트링 spell 이 주어졌을 때, 이 스트링 내의 모든 A 와 Z 만 추출하여 이 A 와 Z 의 순서를 reverse 한 후에, 원래 스트링의 A 와 Z 가 위치한 자리에 끼워넣는 것이 문제이다. A 와 Z 를 추출한 후에 reverse 하고, 다시 spell 에 끼워넣기 위해서 tmp 스트링 한개를 사용해서 쉽게 해결이 가능하다.
class MagicSpell { public: string fixTheSpell( string spell ) { int a, cnt = 0; string tmp; for( a = 0; a < spell.size(); a++ ) { if( spell[a] == 'A' || spell[a] == 'Z' ) { tmp += spell[a]; } } reverse(tmp.begin(), tmp.end()); for( a = 0; a < spell.size(); a++ ) { if( spell[a] == 'A' || spell[a] == 'Z' ) { spell[a] = tmp[cnt++]; } } return spell; } };

Level 2 - ProductOfDigits  ( Coding Time 19:04, 362.48 Challenge Succeeded )
쉬운 문제인데 참 아까웠다. 숫자 N 이 주어질 때, 제곱수의 형태로 N 을 만들 수 있는 digits 의 제곱승이 최소가 되도록 구하는 것이다. 즉, N 의 모든 소인수 중에서 1 ~ 9 의 숫자가 이루는 지수의 최소값을 구하는 문제이다. 처음에는 2 부터 9 까지 N 에 대해 나누어보면서 얻을 수 있는 모든 소인수들을 구해서, 이 소인수들의 지수승을 구했는데, 이렇게 할 경우 6 = 2^1*3^1 보다는 6 = 6^1 으로 구하는 것이 지수의 값이 최소가 되도록 할 수 있게 된다. 그러므로 역으로 9 부터 2까지 N 에 대해서 brute force 하게 나누어 보면서 구할 수 있는 지수승을 모두 더하면 답이 된다.
class ProductOfDigits { public: int smallestNumber( int N ) { int a, ret = 0; if( N == 1 ) return 1; for( a = 9; a >= 2; a-- ) { while( N%a == 0 ) N /= a, ret++; } if( N > 1 ) return -1; return ret; } };

Level 3 - BestRoads ( Opened )
MST 문제.
N 개의 도시를 연결하는 도로 상태가 연결("Y") 또는 연결되지 않음("N") 으로 주어지는 N*N 크기의 string 벡터가 입력으로 주어지고, index 가 낮을 수록 우선순위가 높다고 할 때, 전체 도시에서 우선순위가 높은 M 개의 도로를 뽑아낸다고 할 때 각각의 도시마다 몇개의 도로가 포함되어 있는지를 출력하는 문제이다.

일반적인 MST 와는 달리 도시간의 도로에 직접 값이 주어지는 것이 아니라 index 가 작은 도시가 우선순위가 높으며, 도시간에 도로를 연결하는 것이 아니라 이미 연결되어 있는 도시간의 도로중에서 숫자를 카운트 하는 것이므로 우선순위 순서대로 연결된 도로를 하나씩 카운트하면서 M 값을 하나씩 빼면서 도로를 제거해 나간다. 만약 도로를 전부 카운트 했음에도 M 이 남는다면 답을 찾을 수 없는 경우이므로 -1 을 출력한다. 이 문제에서 이미 연결되어 있는 도시들의 그래프 중에서 MST 를 찾기 위해 Kruskal 알고리즘을 돌릴 때 N*N 벡터를 루프 돌면서 먼저 등장한 도시간에 연결이 되어 있다면 이 도로를 하나씩 카운트 해 나간다.
class BestRoads { public: vector <int> numberOfRoads( vector <string> roads, int M ) { vector<int> ret; int N = roads.size(); vector<string> c; for( int i = 0; i < N; i++ ) c.push_back(roads[i]); // kruskal's algorithm vector<int> id; for( int i=0; i < N; i++ ) id.push_back(i); int compCnt = N; vector<int> deg(N,0); for( int i = 0; i < N; i++ ) for( int j = i+1; j < N; j++ ) { // id[i] == id[j] 가 의미하는 것은 사이클 발생 if( c[i][j] == 'N' || id[i] == id[j] ) continue; // connected from i to j, it makes MST, idi 와 idj 는 연결된 두 선이 기존에 연결한 선들을 union 하기 위함 int idi = id[i]; int idj = id[j]; M--; compCnt--; c[i][j] = 'N'; c[j][i] = 'N'; deg[i]++; deg[j]++; for( int t = 0; t < N; t++ ) if(id[t] == idi ) id[t] = idj; // 같은 노드를 포함하고 있는지를 확인 } if( compCnt > 1 ) return ret; for( int i = 0; i < N; i++ ) // MST 를 구성하고 난 이후 roads 추가 for( int j = i+1; j < N; j++ ) if( c[i][j] == 'Y' && M > 0 ) { M--; c[i][j] = c[j][i] = 'N'; deg[i]++, deg[j]++; } if( M != 0 ) return ret; return deg; } };

이올린에 북마크하기