## SRM 470

Problem Solving/TopCoder logs 2010.05.28 22:43

석탄절 연휴때 열린 매치..~

최근에 컨테스트가 너무 많이 열려서.. 정신이 없다.. @.@

이번 매치는 나름 까다로울수도 있었던 250을 적당히 풀어서..

rating 5연속 하락을 저지했다.. -_-;;

내 rating 이 코스피도 아니고.. 이거 뭐 왜자꾸 떨어져.. -_-

Level1 - DoorsGame

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 };

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

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 |