SRM 496
Problem Solving/TopCoder logs 2011. 2. 2. 00:06
설 연휴 직전에 열렸던 매치..~
first 원소들이 + 또는 - 쪽으로 등속도로 움직일때, first -> second 가 가능한 경우의 수
근래 있었던 매치와는 다르게 이번 매치는 약간 쉽게 나왔다..
그래도 나는 1개밖에 못풀었지만.. ㅠ_ㅠ
250 을 모처럼 빨리 풀어서 rating 을 쬐금 올렸다..~
level1 을 230 넘긴게 언제인지 가물가물 하군..~!
챌을 시도했으면 좋은 결과가 나왔을텐데..
300등 안에 들것같아서 그냥 현실과 타협한게 좀 아쉬었다..
근데.. 오늘 매치에서 한국인들의 활약이 대단한데..
Level1 - ColoredStrokes
가로로 칠하면 red, 세로로 칠하면 blue, 겹치면 green 이 될때, 주어진 그림판이 나오려면 최소 몇번을 칠해야하나?
처음에 가로 방향으로 scan => red 다 없애고.. 그담에 세로 방향으로 scan!
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 ColoredStrokes {
13 public:
14
15 int getLeast(vector <string> pic)
16 {
17 int n, m;
18 int i, j, k;
19 int cnt;
20 n = pic.size();
21 m = pic[0].size();
22 cnt = 0;
23 for (i = 0; i < n; i++) {
24 for (j = 0; j < m; j++) {
25 if (pic[i][j] == 'R' || pic[i][j] == 'G') {
26 cnt++;
27 for (k = j; k < m; k++) {
28 if (pic[i][k] == 'R') {
29 pic[i][k] = '.';
30 }
31 else if (pic[i][k] == 'G') {
32 pic[i][k] = 'B';
33 }
34 else {
35 break;
36 }
37 }
38 }
39 }
40 }
41 for (i = 0; i < n; i++) {
42 for (j = 0; j < m; j++) {
43 if (pic[i][j] == 'B') {
44 cnt++;
45 for (k = i; k < n; k++) {
46 if (pic[k][j] == 'B') {
47 pic[k][j] = '.';
48 }
49 else {
50 break;
51 }
52 }
53 }
54 }
55 }
56 return cnt;
57 }
58
59 };
Level2 - OneDimensionalBalls
to be updated..
Level3 - YetAnotherHamiltonianPath
두 string 사이의 거리는 lenth(s1)^2 + length(s2)^2 - (longest common prefix of s1 and s2)^2 일때,
s0 -> s1 으로 가는 최소 거리 구하기
문제의 요점은 shortest path 를 찾는것인데.. cost 가 최소가 되도록 하려면
최대한 lcp 가 큰 쪽으로 가야한다.. 그렇게 하려면 sort 한 다음에 순서대로 가면 되겠다..
문제는 원하는 답은 0번에서 시작해서 1번에서 끝나야하는데.. sort 한 결과는 항상 그렇지 않다는 점이다..
그러나 식을 조금만 고쳐서 원하는 결과를 얻을 수 있는데..
sort 한 처음 node 와 끝 node 의 cost 관계를 적용하고..
원래 0번 node 와 1번 node 의 cost 를 끊어주면 된다..
왜 그렇게 되는지 증명은.. 쩝.. 어려움.. ㅠ_ㅠ;;
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 lcp(string s1, string s2)
13 {
14 int i;
15 i = 0;
16 while (i < s1.size() && i < s2.size()) {
17 if (s1[i] != s2[i])
18 break;
19 i++;
20 }
21 return i;
22 }
23
24 class YetAnotherHamiltonianPath {
25 public:
26
27 int leastCost(vector <string> label)
28 {
29 int n;
30 int i, k;
31 int sum;
32 int c1, c2;
33 n = label.size();
34 sum = 0;
35 sum += label[0].size() * label[0].size();
36 sum += label[1].size() * label[1].size();
37 for (i = 2; i < n; i++) {
38 sum += 2 * label[i].size() * label[i].size();
39 }
40 c1 = lcp(label[0], label[1]);
41 sort(label.begin(), label.end());
42 c2 = lcp(label[0], label[n-1]);
43 for (i = 1; i < n; i++) {
44 k = lcp(label[i-1], label[i]);
45 sum -= k * k;
46 }
47 sum += c1 * c1;
48 sum -= c2 * c2;
49 return sum;
50 }
51
52 };
'Problem Solving > TopCoder logs' 카테고리의 다른 글
| 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 498 - WTF!! (0) | 2011.02.27 |
| 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 |
| SRM 479 - 광복절 새벽에 삽질.. (0) | 2010.08.16 |