석탄절 연휴때 열린 매치..~
최근에 컨테스트가 너무 많이 열려서.. 정신이 없다.. @.@
이번 매치는 나름 까다로울수도 있었던 250을 적당히 풀어서..
rating 5연속 하락을 저지했다.. -_-;;
내 rating 이 코스피도 아니고.. 이거 뭐 왜자꾸 떨어져.. -_-






Level1 - DoorsGame

more..


0 번부터 n 번까지 n+1 개의 방이 있고 각 방은 door 로 연결되어있는데 door 마다 색깔이 있다
두사람이 서로 색깔 하나씩을 번갈아가면서 선택하는데 선택한 색깔의 door 가 open 된다
먼저 trophy 번째 방에 갈수 있는사람이 이기는 게임.. 둘다 동시에 간다면 draw

처음에 문제 보고 게임이론인줄 알고 황당해했지만.. 자세히 생각해보니 그냥 simulation 문제였다.

1. 두 player 는 각각 서로 자신만 필요로하는 색깔을 선택해야한다..
2. 그게 다 떨어졌을 경우 상대방이 필요로하더라도 내가 goal 에 도달하기 위한 색깔을 선택해야한다.

1번은 직관적이지만.. 2번은 직관적이지가 않았다..
틀릴걸 각오하고 서밋하고.. 반례를 찾아보려고했는데.. 반례 찾는데 실패..;;
왜 이 전략이 optimal 인지 더 생각해봐야겠다..~


  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 //#define EPS 1e-14
 11
 12 class DoorsGame {
 13 public:
 14
 15 int determineOutcome(string doors, int trophy)
 16 {
 17     int i;
 18     int s1, s2;
 19     int cnt, fl;
 20     s1 = s2 = 0;
 21     for (i = 0; i < trophy; i++) {
 22         s1 |= (1 << (doors[i]-'A'));
 23     }
 24     for (i = doors.size()-1; i >= trophy; i--) {
 25         s2 |= (1 << (doors[i]-'A'));
 26     }
 27
 28     fl = 1;
 29     cnt = 0;
 30     while (s1 && s2) {
 31         if (fl) {
 32             for (i = 0; i < 16; i++) {
 33                 if (s1 & (1 << i)) {
 34                     if (s2 & (1 << i))
 35                         continue;
 36                     break;
 37                 }
 38             }
 39             if (i < 16) {
 40                 s1 -= (1 << i);
 41                 cnt++;
 42             }
 43             else {
 44                 for (i = 0; i < 16; i++) {
 45                     if (s1 & (1 << i)) {
 46                         break;
 47                     }
 48                 }
 49                 s1 &= ~(1 << i);
 50                 s2 &= ~(1 << i);
 51                 cnt++;
 52             }
 53         }
 54         else {
 55             for (i = 0; i < 16; i++) {
 56                 if (s2 & (1 << i)) {
 57                     if (s1 & (1 << i))
 58                         continue;
 59                     break;
 60                 }
 61             }
 62             if (i < 16) {
 63                 s2 -= (1 << i);
 64                 cnt++;
 65             }
 66             else {
 67                 for (i = 0; i < 16; i++) {
 68                     if (s2 & (1 << i))
 69                         break;
 70                 }
 71                 s1 &= ~(1 << i);
 72                 s2 &= ~(1 << i);
 73                 cnt++;
 74             }
 75         }
 76
 77         fl = (fl+1) % 2;
 78     }
 79
 80     if (s1 == 0 && s2 == 0)
 81         return 0;
 82     if (s1 == 0)
 83         return cnt;
 84     return -cnt;
 85 }
 86
 87 };




Level2 - DrawingLines

more..



to be updated..



Level3 - BuildingRoads

더보기



to be updated..


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

SRM 479 - 광복절 새벽에 삽질..  (0) 2010.08.16
SRM 478  (2) 2010.08.08
SRM 477  (0) 2010.07.29
SRM 476 - GOOD  (0) 2010.07.20
SRM 472 - 현충일 새벽에 삽질..  (0) 2010.06.07
SRM 470  (0) 2010.05.28
TCO10 Qual3 - 이런 젠장  (0) 2010.05.25
TCO10 Qaul2  (2) 2010.05.13
SRM 469  (0) 2010.05.05
[SRM 468] 보람이 없구만..  (0) 2010.04.21
SRM 466  (0) 2010.04.05

Leave a Comment


to Top