어제 새벽 2시에 열린 매치..
졸음을 참으며 억지로 참여했는데.. 결국 또 참패했다..
올해 TCO는 그냥 여기서 접어야겠다.. 흑흑..
rating도 4연속 하락.. 요즘 좀 컨디션이 안좋은때인것 같다..
하필 가장 중요할때 컨디션이 엉망이라니..

그리고 코딩속도도 많이 느려진것 같다..
전에는 쉬운문제는 240점도 나오고 그랬는데..
이번에 250을 겨우 213점에 서밋하다니..

Q1 Q2모두 500만 제대로 풀었으면 여유있게 통과했을텐데..
자꾸 코딩에서 말리네..~~





Level1 - RepaintTheChessboard
n by m 짜리 board가 주어지고 각각의 cell은 black 또는 white로 칠해져있다.. 이 보드를 8 by 8 크기로 짤라서 chess 보드를 만들고 싶을때 최소 다시 칠해야하는 cell의 개수

brute force로 풀었다.. (1, 1) 부터시작해서 (n-8, m-8) 까지 모든 cell을 탑으로 하는 chess보드를 만들어서 맨끝이 black일때, white일때를 각각 계산해서 그중 최소값을 고른다..

매우 간단한 문제인데.. 흠.. 도대체 어디서 시간을 낭비한거지.. 나도 plugin같은거 써볼까..

  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
  9 class RepaintTheChessboard {
 10 public:
 11
 12 int minimumChanges(vector <string> board)
 13 {
 14     int i, j, k, l;
 15     int r, c;
 16     int min1, cnt1, cnt2;
 17     char map[100][100];
 18     r = board.size();
 19     c = board[0].size();
 20     for (i = 0; i < r; i++) {
 21         strcpy(map[i], board[i].c_str());
 22     }
 23     min1 = 1000000000;
 24     for (i = 0; i < r; i++) {
 25         if (i+8 > r)
 26             break;
 27         for (j = 0; j < c; j++) {
 28             if (j + 8 > c)
 29                 break;
 30             cnt1 = cnt2 = 0;
 31             for (k = 0; k < 8; k++) {
 32                 for (l = 0; l < 8; l++) {
 33                     if ((k+l) % 2 == 0) {
 34                         if (map[i+k][j+l] == 'B')
 35                             cnt1++;
 36                         else
 37                             cnt2++;
 38                     }
 39                     else {
 40                         if (map[i+k][j+l] == 'B')
 41                             cnt2++;
 42                         else
 43                             cnt1++;
 44                     }
 45                 }
 46             }
 47             min1 = min(min1, min(cnt1, cnt2));
 48         }
 49     }
 50     return min1;
 51 }
 52
 53 };



Level2 - PageNumbers
1부터 n까지의 수를 차례로 쓸때.. '0' ~ '9' digit이 각각 몇번나왔는지 구하는 문제..

참고로 LA 3261 - The Counting Problem 문제와 같다..


match editorial을 참고하여 풀었다..
풀이방법에는 여러가지가 있는데 가장 무난한 방법은 각 자리수에서 digit d가 몇번 나오는지를 세는 방법이다..

1234567 이라는 수가 있으면
첫번째자리 1 에서 '0' ~ '9' 가 각각 몇번 나오는지..
두번째자리 2 에서 '0' ~ '9' 가 각각 몇번 나오는지..
...
...
일곱번째자리 7 에서 '0' ~ '9' 가 각각 몇번 나오는지..
를 세서 다 더하면 된다..

예를들어 현재 3번째 자리를 계산한다고 하면
left = 12, right = 4567 이라고 놓고.. left, right 값을 이용해서 세번째 자리에서 각 digit이 몇번 나오는지 알 수 있다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 class PageNumbers {
  9 public:
 10
 11 vector <int> getCounts(int N)
 12 {
 13     int i, j, k;
 14     int len;
 15     int left, right, cur;
 16     char buf[100];
 17     vector<int> res;
 18
 19     sprintf(buf, "%d", N);
 20     len = strlen(buf);
 21
 22     res.resize(10);
 23     k = 1;
 24     for (i = 0; i < len; i++) {
 25         left = N / k / 10;
 26         right = N % k;
 27         cur = (N / k) % 10;
 28         for (j = 0; j < 10; j++) {
 29             if (j < cur) {
 30                 if (j == 0)
 31                     res[j] += left * k;
 32                 else
 33                     res[j] += (left+1) * k;
 34             }
 35             else if (j > cur) {
 36                 res[j] += left * k;
 37             }
 38             else {
 39                 if (j == 0)
 40                     res[j] += ((left-1) * k) + right + 1;
 41                 else
 42                     res[j] += (left * k) + right + 1;
 43             }
 44         }
 45         k *= 10;
 46     }
 47
 48     return res;
 49 }
 50
 51 };



Level3 - DigitalCounter



to be updated..


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

TopCoder SRM 440 Div 1 - 드디어 Yellow 등극..  (0) 2009.05.14
말많고 탈많았던 SRM 438  (4) 2009.04.20
TopCoder SRM 437 Div 1  (0) 2009.03.25
TCO09 Round 1  (0) 2009.03.08
TCO09 Qual 3 (완료)  (0) 2009.03.05
TCO09 Qual 1  (0) 2009.02.25
TopCoder SRM 434 Div 1  (0) 2009.02.10
TopCoder SRM 432 Div 1  (0) 2009.01.07
TopCoder SRM 428 Div 1  (0) 2008.12.03
탑코더 스름 426 디비젼 1  (0) 2008.11.25

to Top