오랜만에 참여한 탑코더.. 미국에 머무는동안 2번이나 빼먹었다.. 이로써 올해안에 1군복귀는 물건너갔다.. 젱장
오늘 문제셋은 평소에비해 쉬운것 같다.. 문제도 나름 명확하고.. 정말 오랜만에 2문제 풀었다.. ㅠ_ㅠ
그동안 하도 부진해서인지.. 이번에는 하수들만 모인방에서 했다.. 인도애들 왜케많아!!
다시 green으로 복귀했고.. volatility도 약간 높아졌다.. 나름 소득이 있는매치..
다음매치는 R 1000을 목표로해서 차근차근히 올라가야겠다.. 그동안 삽질한 영향이 크군..

방 3등 전체 73등..

사용자 삽입 이미지
정말 오랜만에 두문제 해결..;;

사용자 삽입 이미지
오랜만에 약간 가파른 상승곡선을 그렸다..


[250] TwoRotationCypher

more..

a-z 의 알파벳을 임의의 지점에서 나눠서 두개의 그룹으로 만든다.. 주어진 문자열이 첫번째 그룹에 속하면 첫번째 암호화규칙을 따르고 두번째 그룹에 속하면 두번째 암호화규칙을 따른다.. 암호화규칙은 단순히 원래 문제에서 주어진 수만큼 더하면 된다.. 즉 문자가 'a' 이고 rotate 값이 2 라면 암호화된 문자는 'c'가 된다.. 문자가 주어진 그룹의 범위를 넘어가면 다시 그룹의 처음으로 돌아간다..

쉬운문제.. 시키는데로 하면 된다.. 매치 도중 이문제를 내가 방에서 2번째로 빨리 풀었는데 코딩속도가 느린 나는 약간 당황했다..

첫번째 그룹에대해서는 단순히 모듈러 연산을 하면 쉽게 구해진다.. 두번째 그룹에대해서도 모듈러 연산을 포함한 한줄의 수식으로 가능하지만.. 워낙 귀찮은거를 싫어하므로.. 그냥 1씩더해가면서 simulate 했다.. 이런 단순무식한 방법은 코드길이는 늘어나지만 코딩속도는 줄여준다는 특징이 있다..

system test때 #include <cctype> 을 안한거를 알고 당황했는데.. 그대로 pass해버렸다.. 다행..;;

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 class TwoRotationCypher {
      9 public:
     10
     11 string encrypt(int firstSize, int firstRotate, int secondRotate, string message)
     12 {
     13     char buf[100], res[100];
     14     int i, j;
     15     int len, ch;
     16     string ret;
     17     strcpy(buf, message.c_str());
     18     len = strlen(buf);
     19     for (i = 0; i < len; i++) {
     20         ch = buf[i] - 'a';
     21         if (!isalpha(buf[i])) {
     22             res[i] = buf[i];
     23             continue;
     24         }
     25         if (ch < firstSize) {
     26             ch += (firstRotate);
     27             ch %= firstSize;
     28         }
     29         else {
     30             for (j = 0; j < secondRotate; j++) {
     31                 ch++;
     32                 if (ch == 26)
     33                     ch = firstSize;
     34             }
     35         }
     36         res[i] = ch + 'a';
     37     }
     38     res[i] = 0;
     39     ret = res;
     40     return ret;
     41 }
     42
     43 };




[500] TrueStatements

more..

여러개의 숫자가 들어오고 그 숫자의 값만큼의 statement가 true라는 것을 의미한다.. 정말로 true인 statement의 개수.. 답이 여러개면 그중 최대값 구하기..

문제를 본 순간 적잖이 당황했다.. 문제의 솔루션이 직관적으로 바로 떠올랐지만.. 500점이 이렇게 간단할리 없을거라고 생각해서 반례를 찾아보려고 많은 시간을 까먹은게 실수였다.. ㅠ_ㅠ

솔루션은 간단히.. 각 원소에대해서 그 원소의 값과 출현한 개수가 같으면 답이 될 수 있다..

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 class TrueStatements {
      9 public:
     10
     11 int numberTrue(vector <int> statements)
     12 {
     13     int cnt[100];
     14     int n, i;
     15     n = statements.size();
     16     memset(cnt, 0, sizeof(cnt));
     17     for (i = 0; i < n; i++) {
     18         cnt[statements[i]]++;
     19     }
     20     for (i = 50; i >= 0; i--) {
     21         if (cnt[i] == i)
     22             break;
     23     }
     24     return i;
     25 }
     26
     27 };





[1000] HanoiState

more..

하노이타워에서 초기상태가 "AAA...AA" 일때.. moves번의 이동을 통해 target 을 만들고자 할때 최종 하노이타워의 상태를 구하는 문제.. (당연히 moves가 충분히 크면 답은 target과 같다) 문자열의 왼쪽이 위에있는 원반.. 오른쪽이 아래쪽에있는 원반이다.. 세개의 타워는 각각 'A', 'B', 'C' 로 표기..

시간이 많이 남아있었는데.. 결국 아쉽게도 못풀었다.. 나중에 1등한사람의 코드를 보니 내가 짜다포기한 코드와 거의 90%가 같았다.. 아쉽군..!! 하노이타워에대한 이해가 아직 부족하다..

우선 아래쪽 원반부터 top-down으로 생각한다.. 최종 이동지점만 찾으면 되므로 recursion을 돌릴필요가 없다.. 어떤 원반을 다른타워로 옮기기 위해서는 2^n 번의 이동이 필요하다는점을 이용하여 moves에서 2^n씩을 빼면서 target으로 조작해나간다.. 만약에 moves가 2^n보다 작으면.. target을 바꾸면 된다?! (왜그런지 모르겠다..)

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 class HanoiState {
      9 public:
     10
     11 string partwayState(string target, int moves)
     12 {
     13     int i, j, k;
     14     int n, len, p;
     15     char buf[100], cur[100];
     16     char ch;
     17     string ret;
     18
     19     n = moves;
     20     len = target.size();
     21     strcpy(buf, target.c_str());
     22     for (i = 0; i < len; i++) {
     23         cur[i] = 'A';
     24     }
     25     cur[len] = 0;
     26     for (i = len-1; i >= 0; i--) {
     27         ch = buf[i];
     28         if (ch == cur[i]) {
     29             continue;
     30         }
     31         p = 1 << i;
     32         if (p > n) {
     33             for (j = 0; j < i; j++) {
     34                 if ((ch == 'A' && cur[i] == 'B') || (ch == 'B' && cur[i] == 'A')) {
     35                     buf[j] = 'C';
     36                 }
     37                 else if ((ch == 'A' && cur[i] == 'C') || (ch == 'C' && cur[i] == 'A')) {
     38                     buf[j] = 'B';
     39                 }
     40                 else if ((ch == 'B' && cur[i] == 'C') || (ch == 'C' && cur[i] == 'B')) {
     41                     buf[j] = 'A';
     42                 }
     43             }
     44         }
     45         else {
     46             for (j = 0; j < i; j++) {
     47                 if ((ch == 'A' && cur[i] == 'B') || (ch == 'B' && cur[i] == 'A')) {
     48                     cur[j] = 'C';
     49                 }
     50                 else if ((ch == 'A' && cur[i] == 'C') || (ch == 'C' && cur[i] == 'A')) {
     51                     cur[j] = 'B';
     52                 }
     53                 else if ((ch == 'B' && cur[i] == 'C') || (ch == 'C' && cur[i] == 'B')) {
     54                     cur[j] = 'A';
     55                 }
     56             }
     57             cur[i] = ch;
     58             n -= p;
     59         }
     60     }
     61     ret = cur;
     62     return ret;
     63 }
     64
     65 };

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

TopCoder SRM 383 Div 2 (완료)  (0) 2007.12.14
TopCoder SRM382 DIV2  (2) 2007.12.13
TopCoder SRM381 DIV2 (완료)  (2) 2007.12.09
TopCoder SRM380 DIV2 (완료)  (0) 2007.12.08
TopCoder SRM 379 Div2 (완료)  (0) 2007.11.29
TopCoder SRM378 DIV2 (완료)  (0) 2007.11.21
TopCoder SRM375 DIV2 (Complete)  (6) 2007.11.11
TopCoder SRM374 DIV2  (3) 2007.11.07
TopCoder SRM 373 Div 2  (0) 2007.10.24
TopCoder SRM 372 Div 2  (8) 2007.10.18
TopCoder SRM 371 Div2 (완료)  (2) 2007.10.14

Leave a Comment


to Top