지난주 토욜날 한번 실패하고나서 Qual2 패자부활전..
이번에는 여유있게 600등 안에 들어서 1라운드 진출에 성공했다..~ ㅎㅎ
작년에는 어처구니없게 Q3 까지 가고도 1라운드 진출에 실패했는데..
일단 작년의 성적은 넘어섰으니 목표는 달성했다..




Level1 - BlackWhiteMagic

W와 B가 섞여있는 string 이 주어지면.. 이걸 WW..WWBB..BB 이런식으로 만들기위해 최소 swap 개수를 구해야되는데.. 제약은 swap 하는 원소끼리의 distance 가 모두 distinct 해야한다..

문제 읽고나서 좀 어리버리 했는데.. 다른사람들이 열라 빨리푸는것을보고..
뭔가 쉬운 솔루션이 있다는걸 간파하고 대략 가장 간단한 방법으로 풀었다..
음.. 이런식으로 문제풀면 안되는데.. -_-;;

n개의 W가 제자리가 아닐 경우 항상 n 번만의 distinct 한 swap 으로 정렬시킬 수 있다.. 증명은 ?

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <queue>
  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 class BlackWhiteMagic {
 14 public:
 15
 16 int count(string creatures)
 17 {
 18     int n;
 19     int w;
 20     int cnt;
 21     int i;
 22     n = creatures.size();
 23     w = 0;
 24     for (i = 0; i < n; i++) {
 25         if (creatures[i] == 'W')
 26             w++;
 27     }
 28     cnt = 0;
 29     for (i = 0; i < w; i++) {
 30         if (creatures[i] == 'B')
 31             cnt++;
 32     }
 33     return cnt;
 34 }
 35
 36 };


Level2 - KindAndCruel

'.' 이면 그냥 지날 수 있고 'K' 일 경우 second % K <> 0 일때, 'C' 일 경우는 second % C = 0 일때 지나갈 수 있다.. 왼쪽 끝에서 오른쪽 끝까지 가는데 걸리는 최소시간..

이문제는 간단히 왼쪽에서 오른쪽으로 한칸씩 simulation 하면서 구할 수 있는데..
나는 귀찮은거 생각하기 싫어서 그냥 무식하게 BFS 로 풀었다..

문제를 잘못 이해해서 2번 sample 답이 왜 -1 인지 한참 고민했음.. -_-;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <queue>
  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 typedef struct _d {
 14     int p, k, c;
 15 } DATA;
 16
 17 int dist[55][55][55];
 18
 19 class KindAndCruel {
 20 public:
 21
 22 int crossTheField(string field, int K, int C)
 23 {
 24     int n;
 25     int i, j, k;
 26     int c, p;
 27     int cost;
 28     DATA d1, d2;
 29     queue<DATA> q;
 30
 31     n = field.size();
 32     for (i = 0; i <= n; i++) {
 33         for (j = 0; j <= K; j++) {
 34             for (k = 0; k <= C; k++) {
 35                 dist[i][j][k] = INF;
 36             }
 37         }
 38     }
 39     dist[0][0][0] = 0;
 40     d1.p = 0;
 41     d1.c = 0;
 42     d1.k = 0;
 43     q.push(d1);
 44     while (!q.empty()) {
 45         d1 = q.front();
 46         q.pop();
 47         p = d1.p;
 48         k = d1.k;
 49         c = d1.c;
 50         cost = dist[p][k][c];
 51 //printf("(%d, %d, %d) = %d\n", p, k, c, cost);
 52
 53         if (p == n-1) {
 54             return cost;
 55         }
 56
 57         d2.p = p;
 58         d2.k = (k+1) % K;
 59         d2.c = (c+1) % C;
 60         if (dist[d2.p][d2.k][d2.c] > cost + 1) {
 61             if (field[d2.p] == '.') {
 62                 dist[d2.p][d2.k][d2.c] = cost + 1;
 63                 q.push(d2);
 64             }
 65             else if (field[d2.p] == 'K' && d2.k != 0) {
 66                 dist[d2.p][d2.k][d2.c] = cost + 1;
 67                 q.push(d2);
 68             }
 69             else if (field[d2.p] == 'C' && d2.c == 0) {
 70                 dist[d2.p][d2.k][d2.c] = cost + 1;
 71                 q.push(d2);
 72             }
 73         }
 74
 75         d2.p = p+1;
 76         d2.k = (k+1) % K;
 77         d2.c = (c+1) % C;
 78         if (field[p+1] == '.') {
 79             if (dist[d2.p][d2.k][d2.c] > cost+1) {
 80                 dist[d2.p][d2.k][d2.c] = cost+1;
 81                 q.push(d2);
 82             }
 83         }
 84         else if (field[p+1] == 'K') {
 85             if (d2.k != 0 && dist[d2.p][d2.k][d2.c] > cost+1) {
 86                 dist[d2.p][d2.k][d2.c] = cost+1;
 87                 q.push(d2);
 88             }
 89         }
 90         else if (field[p+1] == 'C') {
 91             if (d2.c == 0 && dist[d2.p][d2.k][d2.c] > cost+1) {
 92                 dist[d2.p][d2.k][d2.c] = cost+1;
 93                 q.push(d2);
 94             }
 95         }
 96     }
 97     return -1;
 98 }
 99
100 };





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

SRM 521  (0) 2011.10.24
SRM 511  (0) 2011.07.04
TCO11 R1 - 탈락  (0) 2011.06.23
SRM 509 !!  (0) 2011.06.09
SRM 507 - 나이스!  (0) 2011.05.30
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

to Top