Jolly Jumpers..~ Jolly Jumpers..~

Google Code Jam 2010 Round 1

Problem Solving/GCJ logs 2010. 5. 23. 22:12

어제 오늘에 걸쳐 열렸던 2010 구글 코드잼 1라운드..

3번에 걸쳐 열리는데 각 매치 상위 1000명이 2라운드에 진출한다..~

나는 Round 1C 까지 가는 졸전끝에 겨우 2라운드 진출에 성공했다.. -_-;;;;

이틀동안 컨테스트를 3번이나 치르니.. 무지 힘들군..;;

작년과 비교해보니 참가자들의 실력이 급상승한 느낌이다.. 헐..

올해도 아무래도 3라운드 진출은 힘들듯 하다..~

내가 제출한 코드나 좀 남겨놔야지..~

Round 1A (링크)

A번 small large 만 빨리 풀었어도 2라운드 진출을 확정할 수 있었는데..

코딩에서 말리면서 나락으로 떨여졌다.. ㅠ_ㅠ;

확실히.. 코딩 스피드 정확도 둘다 좋아지기는 커녕 예전보다 더 무뎌진듯.. ㅠ_ㅠ

1A의 특징은 문제가 어렵고 경쟁이 덜 치열한거 같다.. 덕분에 1문제 풀고도 2라운드 진출이 가능하다..~

A. Rotate (small, large)

그냥 시키는데로 90도 회전시키고 가로 세로 대각선을 확인했다.. ㅋㅋ 과연 집념의 코드라 하겠다..

  1 #include <stdio.h>
2 #include <string.h>
3 int n, k;
4 char map[101][101];
5 char map2[101][101];
6 char map3[101][101];
7 int main()
8 {
9     int tc, cn;
10     int i, j, l;
11     int x, y;
12     int cnt;
13     int fl1, fl2;
14     char buf[101];
15     scanf("%d", &tc);
16     for (cn = 1; cn <= tc; cn++) {
17         scanf("%d%d", &n, &k);
18         for (i = 1; i <= n; i++) {
19             scanf("%s", &map[i][1]);
20         }
21
22         memset(map2, 0, sizeof(map2));
23         for (i = 1; i <= n; i++) {
24             l = 0;
25             for (j = n; j > 0; j--) {
26                 buf[l++] = map[j][i];
27             }
28             buf[l] = 0;
29             strcpy(&map2[i][1], buf);
30         }
31
32         memset(map3, '.', sizeof(map3));
33         for (i = 1; i <= n; i++) {
34             l = 0;
35             for (j = n; j >= 1; j--) {
36                 if (map2[j][i] != '.') {
37                     buf[l++] = map2[j][i];
38                 }
39             }
40             for (x = n, y = 0; y < l; y++, x--) {
41                 map3[x][i] = buf[y];
42             }
43         }
44
45 /*
46 for (i = 1; i <= n; i++) {
47 for (j = 1; j <= n; j++) {
48     printf("%c", map3[i][j]);
49 }
50     printf("\n");
51 }
52 */
53
54         fl1 = fl2 = 0;
55         for (i = 1; i <= n ;i++) {
56             cnt = 0;
57             for (j = 1; j <= n; j++) {
58                 if (map3[i][j] == 'B') {
59                     cnt++;
60                 }
61                 else {
62                     cnt = 0;
63                 }
64                 if (cnt >= k) {
65                     fl1 = 1;
66                     goto X;
67                 }
68             }
69         }
70         for (i = 1; i <= n ;i++) {
71             cnt = 0;
72             for (j = 1; j <= n; j++) {
73                 if (map3[j][i] == 'B') {
74                     cnt++;
75                 }
76                 else {
77                     cnt = 0;
78                 }
79                 if (cnt >= k) {
80                     fl1 = 1;
81                     goto X;
82                 }
83             }
84         }
85         for (i = 1; i <= n ;i++) {
86             for (j = 1; j <= n; j++) {
87                 for (x = i, y = j, l = 0; x <= n && y <= n; x++, y++, l++) {
88                     if (map3[x][y] != 'B')
89                         break;
90                 }
91                 if (l == k) {
92                     fl1 = 1;
93                     goto X;
94                 }
95             }
96         }
97         for (i = 1; i <= n ;i++) {
98             for (j = 1; j <= n; j++) {
99                 for (x = i, y = j, l = 0; x <= n && y > 0; x++, y--, l++) {
100                     if (map3[x][y] != 'B')
101                         break;
102                 }
103                 if (l == k) {
104                     fl1 = 1;
105                     goto X;
106                 }
107             }
108         }
109
110 X:
111
112         for (i = 1; i <= n ;i++) {
113             cnt = 0;
114             for (j = 1; j <= n; j++) {
115                 if (map3[i][j] == 'R') {
116                     cnt++;
117                 }
118                 else {
119                     cnt = 0;
120                 }
121                 if (cnt >= k) {
122                     fl2 = 1;
123                     goto Y;
124                 }
125             }
126         }
127         for (i = 1; i <= n ;i++) {
128             cnt = 0;
129             for (j = 1; j <= n; j++) {
130                 if (map3[j][i] == 'R') {
131                     cnt++;
132                 }
133                 else {
134                     cnt = 0;
135                 }
136                 if (cnt >= k) {
137                     fl2 = 1;
138                     goto Y;
139                 }
140             }
141         }
142         for (i = 1; i <= n ;i++) {
143             for (j = 1; j <= n; j++) {
144                 for (x = i, y = j, l = 0; x <= n && y <= n; x++, y++, l++) {
145                     if (map3[x][y] != 'R')
146                         break;
147                 }
148                 if (l == k) {
149                     fl2 = 1;
150                     goto Y;
151                 }
152             }
153         }
154         for (i = 1; i <= n ;i++) {
155             for (j = 1; j <= n; j++) {
156                 for (x = i, y = j, l = 0; x <= n && y > 0; x++, y--, l++) {
157                     if (map3[x][y] != 'R')
158                         break;
159                 }
160                 if (l == k) {
161                     fl2 = 1;
162                     goto Y;
163                 }
164             }
165         }
166
167 Y:
168
169         if (fl1 && fl2) {
170             printf("Case #%d: Both\n", cn);
171         }
172         else if (fl1) {
173             printf("Case #%d: Blue\n", cn);
174         }
175         else if (fl2) {
176             printf("Case #%d: Red\n", cn);
177         }
178         else {
179             printf("Case #%d: Neither\n", cn);
180         }
181     }
182     return 0;
183 }

Round 1B (링크)

흠.. A번을 비교적 빨리 풀었음에도 불구하고 B번 문제가 해석이 안되서 말린 매치.. ㅠ_ㅠ

차라리 C번 large 를 더 생각해봤으면 하는 아쉬움이 남는다..~

올해 GCJ 문제 description 이 왜이랴..~~

역시 1B 가 문제 난이도도 적당하면서 참가자도 많아서 가장 치열한 매치가 아닌가 생각된다..~

A. File Fix-it (small, large)

내가 올해 GCJ 서밋한 코드중에 가장 맘에 드는 코드이다..~ recursion 의 진수를 보여준 문제..~

C. Your Rank is Pure (small)

처음에 sample I/O 보고 설마 Fibonacci 수열인가..? 하고 서밋했다가 wrong try 그럼 그렇지.. -_-;;

좀 규칙을 찾아보려다가 일단 빨리 서밋하는게 나을거같아서..

small 에 대해서는 그냥 backtracking 으로 풀었다..~~

Round 1C (링크)

1A, 1B 다 실패하고 결국 1C까지 왔다..;;

다행히 이미 진출할만한 사람은 다 진출했기때문에.. 조금 여유있는 매치가 됐다..~

더욱이 B번 문제해석이 무지 까다로웠던게 오히려 도움이 됐다..~ ㅋㅋㅋ (완전 1B - B번 보상임)

문제 의미를 정확히 파악한 나는 (correct 나왔으니깐 정확히 파악한거같음..ㅎㅎ) 쉽게 풀었는데..

이 문제 파악을 잘 못해서 못 푼 사람이 많은거 같다..~

A. Rope Intranet (small)

상당히 tricky 한 문제가 될 수 있을거같아서 (sample input 과 small input 으로는 거의 test 가 안됨)

일단 천천히 생각해볼 요양으로 small 에 대해서는 다음과 같이 어처구니 없게 풀었다.. -_-;;

N 이 최대 2 이므로.. 그냥 case by case

A. Rope Intranet (large)

일단 A 에 대해서 sort 하고 순서대로 확인하면 교차점이 몇개인지 알 수 있다..~

B. Load Testing (small, large)

문제 해석을 잘 안되지만.. 원하는 값을 binary search 로 찾는데 최악의 경우 몇번 걸리느냐.. 를 묻는거 같다..

log2(n) 이 답이라는거..~

small 과 다른거는 long long 으로 casting 한거밖에 없으므로.. 그냥 하나만 남긴다..~

C. Making Chess Boards (small)

주어진 판때기에서 채스보드 몇개를 만들수있냐는건데..

또하나의 집념의 코드가 나왔다..~ ㅋㅋㅋ 잘 보면 5중 loop 인듯.. -_-;;

large input 에 대해서는 어떻게 풀면 될까..?

1 #include <stdio.h>

2 #include <string.h>

4 char map[513][513];

5 char used[513][513];

6 int row, col;

7 int res[513];

9 int get_val(char ch)

10 {

11 if (ch >= '0' && ch <= '9')

12 return ch - '0';

13 return ch - 'A' + 10;

14 }

15 int main()

16 {

17 int tc, cn;

18 int i, j, k, l, x;

19 int len, temp, cnt;

20 int fl;

21 char cur;

22 char buf[1000];

24 scanf("%d", &tc);

25 for (cn = 1; cn <= tc; cn++) {

26 scanf("%d%d", &row, &col);

27 for (i = 0; i < row; i++) {

28 scanf("%s", buf);

29 k = 0;

30 for (j = 0; j < col; j += 4, k++) {

31 temp = get_val(buf[k]);

32 for (l = 3, x = 0; l >= 0; l--, x++) {

33 if (temp & (1 << l))

34 map[i][j+x] = 1;

35 else

36 map[i][j+x] = 0;

37 }

38 }

39 }

41 memset(res, 0, sizeof(res));

42 memset(used, 0, sizeof(used));

44 cnt = 0;

45 for (len = col; len >= 1; len--) {

46 for (i = 0; i < row; i++) {

47 if (i+len-1 >= row)

48 break;

49 for (j = 0; j < col; j++) {

50 if (j+len-1 >= col)

51 break;

52 fl = 1;

53 for (k = 0; k < len && fl; k++) {

54 for (l = 0; l < len; l++) {

55 if (used[i+k][j+l]) {

56 fl = 0;

57 break;

58 }

59 cur = map[i+k][j+l];

60 if (l > 0 && cur == map[i+k][j+l-1]) {

61 fl = 0;

62 break;

63 }

64 if (k > 0 && cur == map[i+k-1][j+l]) {

65 fl = 0;

66 break;

67 }

68 }

69 if (!fl)

70 break;

71 }

73 if (fl) {

74 res[len]++;

75 for (k = 0; k < len; k++) {

76 for (l = 0; l < len; l++) {

77 used[i+k][j+l] = 1;

78 }

79 }

80 }

81 }

82 }

83 if (res[len] > 0)

84 cnt++;

85 }

87 printf("Case #%d: %d\n", cn, cnt);

88 for (i = 512; i >= 1; i--) {

89 if (res[i] > 0) {

90 printf("%d %d\n", i, res[i]);

91 }

92 }

93 }

94 return 0;

95 }

참고: http://www.go-hero.net/jam/

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

Google Code Jam 2016 - Qualification Round (0)	2016.04.23
Google Code Jam Korea 2012 본선 라운드 - 역대 최고성적? (0)	2012.03.03
Google Code Jam Korea 2012 Qual. (0)	2012.03.01
Goodbye GCJ 2011 (0)	2011.05.27
GCJ 2011 Qual (0)	2011.05.19
GCJ 2010 Qual1 가볍게(?) 통과..~ (0)	2010.05.11
Google Code Jam 2010 is in Dublin! (0)	2010.03.01
Goodbye GCJ 2009..~~ (0)	2009.09.29
Google Code Jam 2009 Round 1 (2)	2009.09.12
Google Code Jam 2009 Qualification Round 후기..~ (2)	2009.09.06

By helloneo

이전 1 ··· 441 442 443 444 445 446 447 ··· 780 다음

Jolly Jumpers..~

Google Code Jam 2010 Round 1

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

Category

Recent Post

Recent Comments

Tags

Archive

Calendar

티스토리툴바

« 2024/11 »
일	월	화	수	목	금	토
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30