현충일 새벽 3시에 열린 매치..
보통 SRM 은 밤12시 또는 새벽 1시에 열리는데..
SRM 472 는 GCJ 2 라운드의 영향으로 시간이 좀 밀렸다..

이번매치는 250 이 좀 tricky 해서 챌로만 대박을 낼수도있었는데..
하필이면 7번방(19번 시드)에 걸리면서 거의 챌을 할수가 없었다..
틀리는사람도 거의 없는데.. 다들 챌이 어찌나 빠르던지.. -_-;;
운도 지지리도 없지.. ㅠ_ㅠ




Level1 - PotatoGame

Taro 와 Hanako 가 게임을 하는데 n 개의 감자가 있고 이중에 4^k 꼴의 개수만큼 가져갈 수 있다..
마지막에 가져가는 사람이 이기는게임.. Taro 가 먼저 시작할 때, 누가 이길까??

처음에 게임이론으로 풀려고하니 상태공간이 너무 커서 당황.. (n 이 최대 10억)

근데 의외로 빨리 푸는 사람이 많아서 그냥 greedy 하게 풀어보았다..
4^k 꼴의 수 중 만들수 있는 가장 큰 수 가져가기..
그러다가 반례 발견..!! 역시.. 이렇게 쉬운문제일리가 없지.. -_-;

그래서 처음 몇단계까지 winning position, losing position 을 mark 해가면서 살펴보니 규칙 발견..
20개 단위로 상태가 반복되는거같아서 대략 다음과 같이 풀었다..~

그러다 나중에 다른사람 코드 보니.. 황당..
5로 나누었을때 나머지가 0 또는 2인지만 검사하면 되는 문제였다.. -_-;;

  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 int map[20];
 13
 14 class PotatoGame {
 15 public:
 16
 17 string theWinner(int n)
 18 {
 19     memset(map, 0, sizeof(map));
 20     map[0] = 1;
 21     map[2] = 1;
 22     map[5] = 1;
 23     map[7] = 1;
 24     map[10] = 1;
 25     map[12] = 1;
 26     map[15] = 1;
 27     map[17] = 1;
 28     n = n % 20;
 29     if (map[n])
 30         return "Hanako";
 31     return "Taro";
 32 }
 33
 34 };



Level2 - TwoSidedCards


to be  updated..



Level3 - ColorfulTiles


to be updated..


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

SRM 482  (0) 2010.09.16
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 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

to Top