어제 새벽 2시에 열린 매치..
무려 800명 넘게 참가한 화끈한 매치였는데.. 결정적으로 남들 다 푼 450을 못풀어서 망했다.. ㅠ_ㅠ;;
코드를 보면 간단한데 왜 그렇게 나오는지 모르겠음.. 젠장

Div2 는 난리났구만..~ 무려 114명이 PASS/PASS/PASS 를 기록했음.. -_-;






 Level1 - FoxSequence


주어진 sequence 가 처음에 등차수열로 증가하다가 등차수열로 감소하다가 일정하다가 다시 증가 다시 감소
이런식으로 되어있는지 확인하기

n 이 작아서 그냥 무식하게 O(n^4) 로 풀었다.. 모든 a, b, c, d 에 대해서서 위와 같은 형태가 되는지 확인..
그러나 이 문제는 O(n) 으로도 풀 수 있다..

  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 //#define max(x, y) ((x) > (y) ? (x) : (y))
  9 //#define INF 999999999
 10 //#define EPS 1e-14
 11
 12 class FoxSequence {
 13 public:
 14
 15 string isValid(vector <int> seq)
 16 {
 17     int n;
 18     int a, b, c, d, i, dif;
 19     n = seq.size();
 20     for (a = 1; a < n; a++) {
 21         dif = seq[a] - seq[a-1];
 22         if (dif <= 0)
 23             continue;
 24         for (i = 0; i < a; i++) {
 25             if (seq[i+1] - seq[i] != dif)
 26                 break;
 27         }
 28         if (i != a)
 29             continue;
 30
 31         for (b = a+1; b < n; b++) {
 32             dif = seq[b] - seq[b-1];
 33             if (dif >= 0)
 34                 continue;
 35             for (i = a; i < b; i++) {
 36                 if (seq[i+1]-seq[i] != dif)
 37                     break;
 38             }
 39             if (i != b)
 40                 continue;
 41
 42             for (c = b; c < n; c++) {
 43                 for (i = b; i < c; i++) {
 44                     if (seq[i] != seq[i+1])
 45                         break;
 46                 }
 47                 if (i != c)
 48                     continue;
 49
 50                 for (d = c+1; d < n-1; d++) {
 51                     dif = seq[d]-seq[d-1];
 52                     if (dif <= 0)
 53                         continue;
 54                     for (i = c; i < d; i++) {
 55                         if (seq[i+1]-seq[i] != dif)
 56                             break;
 57                     }
 58                     if (i != d)
 59                         continue;
 60
 61                     dif = seq[n-1]-seq[n-2];
 62                     if (dif >= 0)
 63                         continue;
 64                     for (i = d; i < n-1; i++) {
 65                         if (seq[i+1]-seq[i] != dif)
 66                             break;
 67                     }
 68                     if (i == n-1)
 69                         return "YES";
 70                 }
 71             }
 72         }
 73     }
 74     return "NO";
 75 }
 76
 77 };





Level2 - FoxStones

두 좌표 사이의 거리는 max(|x1-x2|, |y1-y2|) 라고 할때..
input 으로 들어온 layout 과 similar 한 layout 은 몇개인지 구하는 문제
주어진 몇개의 좌표 하나와 그 밖에 임의의 좌표 하나를 pairing 해서 거리가 처음꺼랑 같으면 similar 이다..
그림을 보고 이해해야함.. -_-;

어떤 좌표 (x, y) 와 (x', y') 가 모든 점 (i, j) 에 대해 거리가 같다면 서로 바꿀 수 있다..
이런 거리가 같은 좌표끼리 grouping 하면 각 group 끼리는 서로 disjoint 하다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <map>
  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 long long mod;
 14
 15 class FoxStones {
 16 public:
 17
 18 int getCount(int N, int M, vector <int> sx, vector <int> sy)
 19 {
 20     int i, j, k;
 21     int res;
 22     long long fac[50001];
 23     map<vector<int>, int> mm;
 24     map<vector<int>, int>::iterator it;
 25
 26     mod = 1000000009;
 27     fac[0] = fac[1] = 1;
 28     for (i = 2; i < 50000; i++) {
 29         fac[i] = (fac[i-1] * i) % mod;
 30     }
 31     for (i = 1; i <= N; i++) {
 32         for (j = 1; j <= M; j++) {
 33             vector<int> temp;
 34             for (k = 0; k < sx.size(); k++) {
 35                 temp.push_back(max(abs(sx[k]-i), abs(sy[k]-j)));
 36             }
 37             if (mm.find(temp) == mm.end()) {
 38                 mm[temp] = 1;
 39             }
 40             else {
 41                 mm[temp]++;
 42             }
 43         }
 44     }
 45     res = 1;
 46     for (it = mm.begin(); it != mm.end(); it++) {
 47 printf("it->scond = %d\n", it->second);
 48         res = (res * fac[it->second]) % mod;
 49     }
 50     return (int)res;
 51 }
 52
 53 };



Level3 - FoxJumping



to be updated..


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

TCO11 Qual2  (0) 2011.05.20
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 496  (2) 2011.02.02
SRM 491 - Blue 복귀..  (0) 2010.12.21
SRM 490 - Yellow 1차 방어전 성공..  (0) 2010.12.09
SRM 483 - 처음으로 Petr 이겨본 매치..~  (0) 2010.09.26
SRM 482  (0) 2010.09.16

to Top