[SRM 453] 탑코더 아레나 폭발 -> unrated event

Problem Solving/TopCoder logs 2009. 11. 18. 23:06
18일 새벽 1시에 열렸던 매치..

나같은 경우 좀 오랜만에 참여하는 매치라.. 좀 집중해서 함 해볼라고했는데..
어이없게도 매치 중간에 탑코더 아레나가 뻗어버리는 바람에.. 결국 unrated event 가 되고 말았다..

덕분에 몇시간 전부터 SRM 하려고 기다린사람들..
몇달만에 큰맘먹고 참여하려던 사람들..
새벽에 졸음을 참으며 기다린 사람들..
모두 아쉬움을 뒤로한채 다음을 기약하게 됐다..

지난번 SRM 438 사태 이후에 active match 동안에는 SRM practice room 을 막아놓았는데..
몇번 무사히 매치를 치루다가 이번에 또한번 아레나가 뻗었다..
아무래도 서버좀 업그레이드 해야할텐데.. SRM 도 반으로 줄고 editorial 도 못쓰는판에 서버 살 돈은 있을런지..

아레나가 한참 후에 돌아와서 가봤는데.. 여전히 매치가 진행중이었다..
그래서 다운되어있던동안 풀었던 문제를 그냥.. 서밋하고 잤는데.. 나중에 확인해 보니..


캬캬캬 4등이다..~  -_-;;



Level1 - TheBasketballDivOne
n개의 팀이 서로 2번씩 매치를 치룬다.. (리그전이라고 해야하는데 문제에서 토너먼트라고 써놓아서 헷갈릴만한다..)  1등 한 팀이 m 번 이겼을때.. 2등부터 n등까지 팀이 각각 몇번 이겼는지를 나열할때 나올 수 있는 경우의 수 구하기..

250 치고는 생각보다 쉽지 않은 문제가 나왔다..
즉, 수열 (W1, W2, ..., Wn) 을 만드는데 W1 >= W2 >= ... >= Wn 의 조건을 만족해야 한다..
그래서.. 어..? 이런거 랑 비슷한 문제인가..? 생각하다가..
다시 생각해보니 앞의 수가 뭐냐에 따라 뒤에 수는 어쩔수없이 결정되는 경우도 있다..
(한팀이 승리하면 다른한팀은 패하는 것이므로)

그래서 방법을 바꿔서 backtracking 을 시도.. 모든 경우를 다 시도해보았다..
나올수있는 상태공간은 3^(n*(n-1)/2) 이다..

코딩을 좀 쉽게하려고 pruning 을 하지 않았다.. 그래서 좀 비효율적인 코드..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <set>
  7 using namespace std;
  8 //#define min(x, y) ((x) > (y) ? (y) : (x))
  9 //#define max(x, y) ((x) > (y) ? (x) : (y))
 10 //#define INF 999999999
 11
 12 int n, start;
 13 int check[100];
 14 int sum[100];
 15 int map[10][10];
 16 set<vector<int> > ss;
 17
 18 void print_map(int map[10][10])
 19 {
 20     int i, j;
 21     for (i = 0; i < n; i++) {
 22         for (j = 0; j  < n; j++) {
 23             printf(" %d", map[i][j]);
 24         }
 25         printf("\n");
 26     }
 27 }
 28
 29 void dfs(int u, int cnt)
 30 {
 31     int i, j, k;
 32     check[cnt] = u;
 33     if (cnt == n*(n-1)/2-1) {
 34         k = 0;
 35         memset(map, 0, sizeof(map));
 36         for (i = 0; i < n; i++) {
 37             for (j = i+1; j < n; j++) {
 38                 map[i][j] = check[k];
 39                 map[j][i] = 2 - check[k];
 40                 k++;
 41             }
 42         }
 43         memset(sum, 0, sizeof(sum));
 44         for (i = 0; i < n; i++) {
 45             for (j = 0; j < n; j++) {
 46                 sum[i] += map[i][j];
 47             }
 48         }
 49         if (sum[0] != start) {
 50             return ;
 51         }
 52         for (i = 1; i < n; i++) {
 53             if (sum[i] > sum[i-1])
 54                 return ;
 55         }
 56         vector<int> vt;
 57         for (i = 0; i < n; i++) {
 58             vt.push_back(sum[i]);
 59         }
 60         ss.insert(vt);
 61         return ;
 62     }
 63     dfs(0, cnt+1);
 64     dfs(1, cnt+1);
 65     dfs(2, cnt+1);
 66 }
 68 class TheBasketballDivOne {
 69 public:
 70
 71 int find(int N, int M)
 72 {
 73     int i, res;
 74     n = N;
 75     start = M;
 76
 77     ss.clear();
 78     memset(check, -1, sizeof(check));
 79
 80     dfs(0, 0);
 81     dfs(1, 0);
 82     dfs(2, 0);
 83
 84     res = ss.size();
 85     printf("res = %d\n", res);
 86
 87     return res;
 88 }
 89
 90 };





Level2 - TheBasketballDivOne


to be updated..



Level3 - TheSoccerDivOne


to be updated..


'Problem Solving > TopCoder logs' 카테고리의 다른 글

TopCoder SRM 457 Div 1  (0) 2010.01.06
[SRM 456] 2009년 마지막 SRM  (0) 2009.12.23
TopCoder SRM 455 Div 1  (0) 2009.12.19
TopCoder SRM 454 Div 1  (0) 2009.12.07
TopCoder SRM 453.5 (??) Div 1  (0) 2009.11.26
TopCoder SRM 450 Div 1  (0) 2009.10.19
TopCoder Member Pilot 2  (0) 2009.10.01
TopCoder SRM 449 Div 1  (0) 2009.09.24
TopCoder SRM 448 Div 1  (0) 2009.09.11
Beta SRM (Member-Run Round)  (0) 2009.08.19
  • By helloneo

to Top

티스토리툴바