지난 일요일 새벽1시에 열렸던 매치...
이번 매치에서 우리방에 한국사람이 세명이나 모이는 흔치않은 일이 벌어졌다..
근데 결과는 셋다 성적이 안좋았다.. -_-
나는 250 쉬운문제를 두번이나 리서밋하는 삽질끝에 결국 낮은 점수를 얻고말았다.. ㅠ_ㅠ;
그리고 오랜만에 펼쳐진 챌린지 매치였는데.. 한개도 성공시키지 못해서.. 좀 아쉬움이 남는 매치이다..





Level1 - OrderedNim
일반 nim game과 같이 여러개의 pile of stone 이 있는데.. 임의의 pile 하나에서 한개 이상의 돌을 꺼내갈 수 있다.. 일반 nim game 과 다른점은 앞의 pile 부터 차례로 가져가야 한다는 점이다.. alice 가 먼저 시작할때, alice와 bob 중에 누가 이기겠는가.?

쉬운문제임에도 불구하고 코딩 실수로 인하여.. 두번의 리서밋 때문에 좌절한 문제이다..

곰곰히 생각해보면 각 pile에 대해서 취할 수 있는 최적의 전략은..
한개 남기거나.. 다 가져가거나.. 이 두가지 중의 하나이다..

그럼 현재 상태에서 돌을 다 가져가야하는지 한개 남겨야 하는지는 어떻게 알수있을까..?
잘 생각해보면 앞에서부터 1개만 있는 pile 을 세면 대략 알 수 있다..
매치중에 잘 생각이 안나서.. 그냥 memorizaion 을 이용하여 모든 상태를 다 시도해보았다..
쥐잡는데 소잡는 칼을 쓴 꼴.. -_-;;

나머지는 게임이론을 적용하여 현재 상태가 이기는 상태인지 지는상태인지를 mark 하면 된다..
Game Theory에 대한 자세한 내용은 여기에 포스팅 한 적이 있다..
http://apnetwork.tistory.com/110

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7 #define min(x, y) ((x) > (y) ? (y) : (x))
  8 //#define max(x, y) ((x) > (y) ? (x) : (y))
  9 //#define INF 999999999
 10
 11 int num[100];
 12 int n;
 13 int memo[100][3];
 14
 15 int recur(int u, int v)
 16 {
 17     int a, b;
 18     if (u == n-1) {
 19         return 1;
 20     }
 21     if (memo[u][v] != 0)
 22         return memo[u][v];
 23
 24     if (v == 1) {
 25         a = recur(u+1, num[u+1]);
 26         return memo[u][v] = -1 * a;
 27     }
 28     a = recur(u, 1);
 29     b = recur(u+1, num[u+1]);
 30     if (a == 1 && b == 1)
 31         return memo[u][v] = -1;
 32     return memo[u][v] = 1;
 33 }
 34
 35 class OrderedNim {
 36 public:
 37
 38 string winner(vector <int> layout)
 39 {
 40     int i, res;
 41     n = layout.size();
 42     for (i = 0; i < n; i++) {
 43         num[i] = min(2, layout[i]);
 44     }
 45     if (n == 1) {
 46         return "Alice";
 47     }
 48     memset(memo, 0, sizeof(memo));
 49     res = recur(0, num[0]);
 50     if (res == 1)
 51         return "Alice";
 52     return "Bob";
 53 }



Level2 - StrongEconomy
한달동안 만들 수 있는 gold 는 factory 개수 * specialist 수 이다.. factory 또는 specialist 를 하나 늘리는데는 price 만큼의 gold가 든다.. target 이상의 gold 를 모으기 위해 최소 몇달이 걸리겠는가?

아.. 어처구니없는 문제.. -_-;;
그냥 simulation 해봤는데.. 의외로 답이 잘 나와서 그냥 서밋했는데.. 역시.. 쉬운문제가 아니었다..
우선 n 과 k 의 최대 범위가 10^12 라서 n * k 는 64 bit integer 범위를 훌쩍 넘어가버린다.. ㅠ_ㅠ;;
이런 간단한 사항을 확인하지 못해서 챌 당한 문제..


to be updated..



Level3 - RowGame



to be updated..


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

[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
[SRM 453] 탑코더 아레나 폭발 -> unrated event  (4) 2009.11.18
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
[SRM 446] 매치가 뭐 이래..?! (Unchallengeable Match)  (6) 2009.08.09

Leave a Comment


to Top