이번 매치는 완전.. 역대 최악이었다.. 이보다 더 안좋을수도있을까..?
-25점이란 역대 최악의 점수로 방 꼴찌 전체 508등.. ㅠ_ㅠ
덕분에 rating도 폭락하면서 역대 최저 rating(1086)을 마크했다..
250점짜리는 만만해보였는데.. 500점짜리도 쉬워보여서 더 사람들이 못풀것같은 500점짜리 먼저 시도..
근데 코딩에서 삽질하는바람에 한시간 다 보내고 500점짜리도 망쳐버렸다.. ㅠ_ㅠ
괜히 블챌하다가 25점만 더 잃었다.. 흑흑.. ㅠ_ㅠ;
sysfail과 challenge가 난무했는데도 불구하고.. 난 test case를 구리게 만들어서 실패했다.. 젠장 두고봐!!!!

사용자 삽입 이미지
젠장.. 공동꼴찌.. 완전 굴욕이다..

사용자 삽입 이미지
쭉쭉 폭락하는구나.. DIV1에서 한문제라도 풀려고했지만.. 다음으로 미뤄야겠다.. 우선 상금매치를위해 rating관리 들어가야겠다..

[250] JumpingBoard
이 문제는 (0,0)에서 시작해서 그 칸에 적혀있는 숫자만큼 위아래좌우로 이동할 수 있다.. 단 H에 빠지면 안되고 밖으로 나가서도 안된다.. 최대 몇번을 이동할 수 있는지 구하는 문제.. cycle이 생기는 경우 -1을 return

역시 젤 만만한 문제였다.. longest path를 구하는문제.. dfs로 search하면서 각 노드에서 갈수있는 최대 길이를 memorization했다.. 그러고보니 교내 프로그래밍 경진대회때 내가 낸 문제랑 비슷하군.. 물론 이게 더 어렵다..
근데.. 왜케 코드가 길지.. -_-;

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 int n, m;
      9 int is_cycle;
     10 int dp[51][51];
     11 char map[51][51];
     12 char check[51][51];
     13
     14 int dfs(int u, int v)
     15 {
     16     int i, j, k;
     17     int max1 = 1;
     18
     19     k = map[u][v] - '0';
     20     if (v+k < m && map[u][v+k] != 'H') {
     21         if (check[u][v+k] == 1) {
     22             is_cycle = 1;
     23             return -1;
     24         }
     25         if (dp[u][v+k]) {
     26             max1 = max(max1, dp[u][v+k]+1);
     27         }
     28         else {
     29             check[u][v+k] = 1;
     30             dp[u][v+k] = dfs(u, v+k);
     31             max1 = max(max1, dp[u][v+k]+1);
     32             check[u][v+k] = 2;
     33         }
     34     }
     35     if (v-k >= 0 && map[u][v-k] != 'H') {
     36         if (check[u][v-k] == 1) {
     37             is_cycle = 1;
     38             return -1;
     39         }
     40         if (dp[u][v-k]) {
     41             max1 = max(max1, dp[u][v-k]+1);
     42         }
     43         else {
     44             check[u][v-k] = 1;
     45             dp[u][v-k] = dfs(u, v-k);
     46             max1 = max(max1, dp[u][v-k]+1);
     47             check[u][v-k] = 2;
     48         }
     49     }
     50     if (u-k >= 0 && map[u-k][v] != 'H') {
     51         if (check[u-k][v] == 1) {
     52             is_cycle = 1;
     53             return -1;
     54         }
     55         if (dp[u-k][v]) {
     56             max1 = max(max1, dp[u-k][v]+1);
     57         }
     58         else {
     59             check[u-k][v] = 1;
     60             dp[u-k][v] = dfs(u-k, v);
     61             max1 = max(max1, dp[u-k][v]+1);
     62             check[u-k][v] = 2;
     63         }
     64     }
     65     if (u+k < n && map[u+k][v] != 'H') {
     66         if (check[u+k][v] == 1) {
     67             is_cycle = 1;
     68             return -1;
     69         }
     70         if (dp[u+k][v]) {
     71             max1 = max(max1, dp[u+k][v]+1);
     72         }
     73         else {
     74             check[u+k][v] = 1;
     75             dp[u+k][v] = dfs(u+k, v);
     76             max1 = max(max1, dp[u+k][v]+1);
     77             check[u+k][v] = 2;
     78         }
     79     }
     80     return dp[u][v] = max1;
     81 }
     82
     83 class JumpingBoard {
     84 public:
     85
     86 int maxJumps(vector<string> board)
     87 {
     88     int i, j, max1;
     89     m = board[0].size();
     90     n = board.size();
     91     for (i = 0; i < n; i++) {
     92         strcpy(map[i], board[i].c_str());
     93     }
     94     memset(dp, 0, sizeof(dp));
     95     memset(check, 0, sizeof(check));
     96
     97     is_cycle = 0;
     98     check[0][0] = 1;
     99     dfs(0, 0);
    100     if (is_cycle)
    101         return -1;
    102
    103     max1 = 0;
    104     for (i = 0; i < n; i++) {
    105         for (j = 0; j < m; j++) {
    106             max1 = max(max1, dp[i][j]);
    107         }
    108     }
    109     return max1;
    110 }
    111
    112 };

이방법 말고 Bellman-Ford를 이용하는 기발한 방법이 여기 설명되어 있다..




[500] PolylineUnion 인풋으로 점또는 선분 또는 서로 이어진 선분(polyline)이 들어온다.. 총 몇개의 picture로 구성되어있는지 구하는 문제.. 즉, connected component가 몇개인지..

선분교차를 구현한게 있어서 거져먹기위해 이문제를 덥석 물었다.. 헐.. 근데 코딩하다가 꼬이더니.. 결국 못풀었다.. 답이 이상하게 나오길래.. 나중에 확인해보니 '=' 을 '=='으로 잘못쓴게있었다.. OTL .. ㅠ_ㅠ;;
고쳐서 submit해봤는데 역시 아직도 sysfail이다.. 뭐.. 고치기는 귀찮고.. 아마도 input parsing을 잘못한듯 싶다..

결국 선분교차 알고리즘을 이용하여 해결..~

1) single point로 주어진 경우 (x1, y1) - (x1, y1) 이라는 선분으로 생각하면 쉽다..
2) parsing이 열라 짜증나는데.. strtok 를 이중으로 쓰면 안되더군.. 새로운사실..?



[1000] BinaryCodes 각 문자를 나타내는 2진 코드가 주어진다. 어떤 encoding된 코드가 3개 이상의 문자열로 decoding된다면 "really ambiguous"라고 한다. "really ambiguous"한 가장 짧은 코드를 찾는 문제

음.. 모르겠다.. -_-;;



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

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
TopCoder SRM 370 Div2  (0) 2007.10.14
TopCoder SRM369 DIV2  (6) 2007.10.05
TopCoder SRM 368 Div 1  (0) 2007.10.03
TopCoder SRM 367 Div 2 (완료)  (10) 2007.09.27
TopCoder SRM 366 DIV 1  (2) 2007.09.18
TopCoder SRM 365 Div 1  (0) 2007.09.13
TopCoder SRM 364 Div 1  (0) 2007.09.09
TopCoder SRM 363 Div 2 (완료)  (0) 2007.08.12

Leave a Comment


to Top