설 연휴 직전에 열렸던 매치..~
근래 있었던 매치와는 다르게 이번 매치는 약간 쉽게 나왔다..
그래도 나는 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

first 원소들이 + 또는 - 쪽으로 등속도로 움직일때, first -> second 가 가능한 경우의 수


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

to Top