SRM 498 - WTF!!
Problem Solving/TopCoder logs 2011. 2. 27. 20:27
어제 새벽 2시에 열린 매치..
무려 800명 넘게 참가한 화끈한 매치였는데.. 결정적으로 남들 다 푼 450을 못풀어서 망했다.. ㅠ_ㅠ;;
코드를 보면 간단한데 왜 그렇게 나오는지 모르겠음.. 젠장
Div2 는 난리났구만..~ 무려 114명이 PASS/PASS/PASS 를 기록했음.. -_-;
Level1 - FoxSequence
주어진 sequence 가 처음에 등차수열로 증가하다가 등차수열로 감소하다가 일정하다가 다시 증가 다시 감소
이런식으로 되어있는지 확인하기
n 이 작아서 그냥 무식하게 O(n^4) 로 풀었다.. 모든 a, b, c, d 에 대해서서 위와 같은 형태가 되는지 확인..
그러나 이 문제는 O(n) 으로도 풀 수 있다..
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 FoxSequence {
13 public:
14
15 string isValid(vector <int> seq)
16 {
17 int n;
18 int a, b, c, d, i, dif;
19 n = seq.size();
20 for (a = 1; a < n; a++) {
21 dif = seq[a] - seq[a-1];
22 if (dif <= 0)
23 continue;
24 for (i = 0; i < a; i++) {
25 if (seq[i+1] - seq[i] != dif)
26 break;
27 }
28 if (i != a)
29 continue;
30
31 for (b = a+1; b < n; b++) {
32 dif = seq[b] - seq[b-1];
33 if (dif >= 0)
34 continue;
35 for (i = a; i < b; i++) {
36 if (seq[i+1]-seq[i] != dif)
37 break;
38 }
39 if (i != b)
40 continue;
41
42 for (c = b; c < n; c++) {
43 for (i = b; i < c; i++) {
44 if (seq[i] != seq[i+1])
45 break;
46 }
47 if (i != c)
48 continue;
49
50 for (d = c+1; d < n-1; d++) {
51 dif = seq[d]-seq[d-1];
52 if (dif <= 0)
53 continue;
54 for (i = c; i < d; i++) {
55 if (seq[i+1]-seq[i] != dif)
56 break;
57 }
58 if (i != d)
59 continue;
60
61 dif = seq[n-1]-seq[n-2];
62 if (dif >= 0)
63 continue;
64 for (i = d; i < n-1; i++) {
65 if (seq[i+1]-seq[i] != dif)
66 break;
67 }
68 if (i == n-1)
69 return "YES";
70 }
71 }
72 }
73 }
74 return "NO";
75 }
76
77 };
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 FoxSequence {
13 public:
14
15 string isValid(vector <int> seq)
16 {
17 int n;
18 int a, b, c, d, i, dif;
19 n = seq.size();
20 for (a = 1; a < n; a++) {
21 dif = seq[a] - seq[a-1];
22 if (dif <= 0)
23 continue;
24 for (i = 0; i < a; i++) {
25 if (seq[i+1] - seq[i] != dif)
26 break;
27 }
28 if (i != a)
29 continue;
30
31 for (b = a+1; b < n; b++) {
32 dif = seq[b] - seq[b-1];
33 if (dif >= 0)
34 continue;
35 for (i = a; i < b; i++) {
36 if (seq[i+1]-seq[i] != dif)
37 break;
38 }
39 if (i != b)
40 continue;
41
42 for (c = b; c < n; c++) {
43 for (i = b; i < c; i++) {
44 if (seq[i] != seq[i+1])
45 break;
46 }
47 if (i != c)
48 continue;
49
50 for (d = c+1; d < n-1; d++) {
51 dif = seq[d]-seq[d-1];
52 if (dif <= 0)
53 continue;
54 for (i = c; i < d; i++) {
55 if (seq[i+1]-seq[i] != dif)
56 break;
57 }
58 if (i != d)
59 continue;
60
61 dif = seq[n-1]-seq[n-2];
62 if (dif >= 0)
63 continue;
64 for (i = d; i < n-1; i++) {
65 if (seq[i+1]-seq[i] != dif)
66 break;
67 }
68 if (i == n-1)
69 return "YES";
70 }
71 }
72 }
73 }
74 return "NO";
75 }
76
77 };
Level2 - FoxStones
두 좌표 사이의 거리는 max(|x1-x2|, |y1-y2|) 라고 할때..
input 으로 들어온 layout 과 similar 한 layout 은 몇개인지 구하는 문제
주어진 몇개의 좌표 하나와 그 밖에 임의의 좌표 하나를 pairing 해서 거리가 처음꺼랑 같으면 similar 이다..
그림을 보고 이해해야함.. -_-;
어떤 좌표 (x, y) 와 (x', y') 가 모든 점 (i, j) 에 대해 거리가 같다면 서로 바꿀 수 있다..
이런 거리가 같은 좌표끼리 grouping 하면 각 group 끼리는 서로 disjoint 하다..
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <map>
7 using namespace std;
8 //#define min(x, y) ((x) > (y) ? (y) : (x))
9 #define max(x, y) ((x) > (y) ? (x) : (y))
10 //#define INF 999999999
11 //#define EPS 1e-14
12
13 long long mod;
14
15 class FoxStones {
16 public:
17
18 int getCount(int N, int M, vector <int> sx, vector <int> sy)
19 {
20 int i, j, k;
21 int res;
22 long long fac[50001];
23 map<vector<int>, int> mm;
24 map<vector<int>, int>::iterator it;
25
26 mod = 1000000009;
27 fac[0] = fac[1] = 1;
28 for (i = 2; i < 50000; i++) {
29 fac[i] = (fac[i-1] * i) % mod;
30 }
31 for (i = 1; i <= N; i++) {
32 for (j = 1; j <= M; j++) {
33 vector<int> temp;
34 for (k = 0; k < sx.size(); k++) {
35 temp.push_back(max(abs(sx[k]-i), abs(sy[k]-j)));
36 }
37 if (mm.find(temp) == mm.end()) {
38 mm[temp] = 1;
39 }
40 else {
41 mm[temp]++;
42 }
43 }
44 }
45 res = 1;
46 for (it = mm.begin(); it != mm.end(); it++) {
47 printf("it->scond = %d\n", it->second);
48 res = (res * fac[it->second]) % mod;
49 }
50 return (int)res;
51 }
52
53 };
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <map>
7 using namespace std;
8 //#define min(x, y) ((x) > (y) ? (y) : (x))
9 #define max(x, y) ((x) > (y) ? (x) : (y))
10 //#define INF 999999999
11 //#define EPS 1e-14
12
13 long long mod;
14
15 class FoxStones {
16 public:
17
18 int getCount(int N, int M, vector <int> sx, vector <int> sy)
19 {
20 int i, j, k;
21 int res;
22 long long fac[50001];
23 map<vector<int>, int> mm;
24 map<vector<int>, int>::iterator it;
25
26 mod = 1000000009;
27 fac[0] = fac[1] = 1;
28 for (i = 2; i < 50000; i++) {
29 fac[i] = (fac[i-1] * i) % mod;
30 }
31 for (i = 1; i <= N; i++) {
32 for (j = 1; j <= M; j++) {
33 vector<int> temp;
34 for (k = 0; k < sx.size(); k++) {
35 temp.push_back(max(abs(sx[k]-i), abs(sy[k]-j)));
36 }
37 if (mm.find(temp) == mm.end()) {
38 mm[temp] = 1;
39 }
40 else {
41 mm[temp]++;
42 }
43 }
44 }
45 res = 1;
46 for (it = mm.begin(); it != mm.end(); it++) {
47 printf("it->scond = %d\n", it->second);
48 res = (res * fac[it->second]) % mod;
49 }
50 return (int)res;
51 }
52
53 };
Level3 - FoxJumping
to be updated..
'Problem Solving > TopCoder logs' 카테고리의 다른 글
| TCO11 Qual2 (0) | 2011.05.20 |
|---|---|
| TCO11 Qual1 (2) | 2011.05.15 |
| SRM 504 - unrated event (0) | 2011.04.27 |
| SRM 503 흑흑 ㅠ_ㅠ;; (0) | 2011.04.18 |
| SRM 501 (0) | 2011.04.01 |
| SRM 496 (2) | 2011.02.02 |
| SRM 491 - Blue 복귀.. (0) | 2010.12.21 |
| SRM 490 - Yellow 1차 방어전 성공.. (0) | 2010.12.09 |
| SRM 483 - 처음으로 Petr 이겨본 매치..~ (0) | 2010.09.26 |
| SRM 482 (0) | 2010.09.16 |