어제 저녁 9시에 열린 매치.. 오랜만에 참여했다.. 시간대도 좋았고..
이번매치에는 문제가 좀 tricky한게 많아서 챌린지의 향연이었다..
나도 간신히 250은 pass했는데.. 챌에서 삽질한게 좀 아쉽다..
사람들이 많이 fail해서그런지.. rating은 생각보다 많이 안떨어졌다..;

사용자 삽입 이미지



Level1 - LampsGrid

more..

0 또는 1로 채워져있는 2차원 matrix가 주어진다.. 임의의 row에 대해서 모든 column의 값이 1이면 그 row의 상태를 on 이라고 한다. 각 column에 대해서 column 전체 값을 뒤집는 operation을 K번 해야할 때 최대 몇개의 row를 on 인 상태로 만들 수 있을까?

정말 삽질끝에 풀어냈다.. 첨에 아이디어가 잘 생각이 안나서.. 그냥 포기할까 했는데.. 끝까지 물고늘어져서.. 기어코 pass했다.. 오호.. 요즘 컨디션이 좀 괜찮나..?

우선 각 row에 대해서 0이 몇개인지 센다.. 0의 개수가 K보다 크거나 K와 parity가 다르면 절대 그 row는 on이 될 수 없다.. 또한 다른 row와 독립적이어서 그냥 지워버리고 생각하면 된다.. 그리고 남은 row에 대해서 똑같은 row가 가장 많은것을 on 시키는 전략으로 하면 된다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <map>
  7 using namespace std;
  8 #define max(x, y) ((x) > (y) ? (x) : (y))
  9
 10 class LampsGrid {
 11 public:
 12
 13 int mostLit(vector <string> initial, int K)
 14 {
 15     int n, m;
 16     int i, j;
 17     int temp, max1;
 18     int row_sum[100];
 19     int check[100];
 20     char board[100][100];
 21     map<string, int> dup;
 22     n = initial.size();
 23     m = initial[0].size();
 24     memset(board, 0, sizeof(board));
 25     for (i = 0; i < n; i++) {
 26         strcpy(&board[i+1][1], initial[i].c_str());
 27     }
 28     memset(row_sum, 0, sizeof(row_sum));
 29     for (i = 1; i <= n; i++) {
 30         for (j = 1; j <= m; j++) {
 31             row_sum[i] += board[i][j] - '0';
 32         }
 33     }
 34     memset(check, 0, sizeof(check));
 35     for (i = 1; i <= n; i++) {
 36         temp = m - row_sum[i];
 37         if (temp > K) {
 38             check[i] = -1;
 39         }
 40         if ((temp & 1) != (K & 1)) {
 41             check[i] = -1;
 42         }
 43     }
 44     max1 = 0;
 45     for (i = 1; i <= n; i++) {
 46         string s = &board[i][1];
 47         if (check[i] == -1)
 48             continue;
 49         if (dup.find(s) == dup.end()) {
 50             dup[s] = 1;
 51         }
 52         else {
 53             dup[s]++;
 54         }
 55         temp = dup[s];
 56         max1 = max(max1, temp);
 57     }
 58     return max1;
 59 }



Level2 - GroupedWord

more..

여러개의 문자열 조각들이 input으로 들어온다.. 이 문자열들을 모두 붙여서 하나의 문자열을 만드는데.. 규칙은 같은 문자는 모두 연속되어야 한다.

예)
ccazzzzbb <--- (O)
aabbbccb <--- (X)

이렇게 문자열을 붙일수 있는 경우가 하나면 만들어진 문자열을 리턴하고 답이 여러개면 "MANY" 불가능하면 "IMPOSSIBLE"을 리턴..


to be updated..


Level 3 - BuildersCountry

more..




to be updated..


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

TCO09 Round 1  (0) 2009.03.08
TCO09 Qual 3 (완료)  (0) 2009.03.05
TCO09 Qual 2  (0) 2009.03.01
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
TopCoder SRM 425 Div 2 (완료)  (0) 2008.11.13
TopCoder SRM 422 Div 1  (4) 2008.10.19
TopCoder SRM 421 Div 1  (0) 2008.10.12

Leave a Comment


to Top