새벽 1시에 있었던 매치.. 결과는 조금 아쉬웠다.. 1000번은 뭔가 떠올라서 계속 시도했는데 결국 솔루션이틀렸고 안드로를 가고 말았다..

방 5등 전체 154등


사용자 삽입 이미지


사용자 삽입 이미지



[250] RussianSpeedLimits

more..

제한속도가 city안에는 60 밖은 90 특별지역은 임의의 숫자로 표기.. 인풋이 순서대로 들어올때 마지막의 제한속도를 구하는문제..

문제가 너무 쉬워서 문제해석을 잘못했나.. 하고 한참 들여다본 문제..
마지막이 숫자이면 그게 답이고.. 나머지는 city가 몇번나왔는지 세서 그 parity를 체크하면 된다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 class RussianSpeedLimits {
  9 public:
 10
 11 int getCurrentLimit(vector <string> signs)
 12 {
 13     int i, k, fl;
 14     char buf[100];
 15     int size = signs.size();
 16     fl = 0;
 17     for (i = 0; i < size; i++) {
 18         strcpy(buf, signs[i].c_str());
 19         if (*buf == 'c') {
 20             fl = (fl + 1) % 2;
 21             if (fl == 1)
 22                 k = 90;
 23             else
 24                 k = 60;
 25         }
 26         else if (*buf == 'd') {
 27             if (fl == 1)
 28                 k = 90;
 29             else
 30                 k = 60;
 31         }
 32         else {
 33             k = atoi(buf);
 34         }
 35     }
 36     return k;
 37 }
 38
 39 };




[500] UnderscoreJustification

more..

문장이 주어지고 문장을 width 칸에 딱 맞게 배치하도록 underscore를 단어 사이에 삽입하기.. 단 삽입되는 underscore는 각각 길이가 최대 1 차이나야하고.. 답이 여러개일 경우 lexy-smallest 로 삽입하기..
단, ascii 순서는 대문자 < underscore < 소문자 순이다..

우선 단어 사이에 삽이되는 underscore개수를 구하고.. 경우에따라 1개 더 추가해야하는게 몇개인지 구한다.. 그 다음부터는 greedy하게 삽입하면 된다.. 뒤에 단어가 소문자이면 삽이.. 대문자이면 건너뛰고.. 그래도 남으면.. 뒤에서부터 안채운거를 채운다.. (맞나?)
나같은경우 복잡한거 생각하는거 매우 싫어하므로.. 그냥 next_permutation으로 모든 가능한 경우를 다 구했다..
그중에 젤 앞서는 문자열 선택..

이문제는 특히 기억에 남는게.. 디버깅도 안하고 한번에 짠게 pass 했다.. 그런 경우가 거의 없었는데.. -_-
fail이 많을줄알았는데.. submit한사람은 거의 pass했다.. 흠.. 덕분에 내 등수만 하락.. ㅠ_ㅠ
그러고보니.. 35~40 줄은 필요가없는 코드이군.. -_-;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <set>
  7 using namespace std;
  8
  9 char word[20][20];
 10
 11 void get_underscore(int u, char* str)
 12 {
 13     int i;
 14     for (i = 0; i < u; i++)
 15         str[i] = '_';
 16     str[i] = 0;
 17 }
 18
 19 class UnderscoreJustification {
 20 public:
 21
 22 string justifyLine(vector <string> words, int width)
 23 {
 24     int n, sum;
 25     int i, k, left;
 26     int cnt[20];
 27     char buf[10000], str[100];
 28     set<string> s;
 29     n = words.size();
 30     sum =0;
 31     for (i = 0; i < n; i++) {
 32         strcpy(word[i], words[i].c_str());
 33         sum += strlen(word[i]);
 34     }
 35     if (((width-sum) % (n-1)) == 0) {
 36         k = (width-sum) / (n-1);
 37         for (i = 0; i < n-1; i++) {
 38             cnt[i] = k;
 39         }
 40     }
 41     else {
 42         k = (width-sum) / (n-1);
 43         left = (width-sum) % (n-1);
 44         for (i = 0; i < n-1; i++) {
 45             if (left) {
 46                 cnt[i] = k + 1;
 47                 left--;
 48             }
 49             else {
 50                 cnt[i] = k;
 51             }
 52         }
 53     }
 54     sort(cnt, cnt+n-1);
 55     do {
 56         strcpy(buf, word[0]);
 57         for (i = 0; i < n-1; i++) {
 58             get_underscore(cnt[i], str);
 59             strcat(buf, str);
 60             strcat(buf, word[i+1]);
 61         }
 62         s.insert(buf);
 63     } while (next_permutation(cnt, cnt+n-1));
 64
 65     set<string>::iterator it;
 66     it = s.begin();
 67     cout << "buf = " << *it << endl;
 68     return *it;
 69 }
 70
 71 };




[1000] SummingArithmeticProgressions

more..

k개의 항으로 이루어진 등차수열의 합이 left와 right 사이에 몇개들어가는지..

ACM-ICPC 준비할때도 그랬지만.. 나는 이런 류의 문제에 가장 취약한것같다.. 그냥 침착하게 하나부터 쭉 구해나가면서 규칙을 찾아야하는데 급하게 한번에 나오는 식을 찾으려고하다가 매번 삽질하는것 같다..

이 문제의 경우 k가 2~5 사이 이므로.. 각각에 대해서 규칙을 찾아보면 쉽다..

k = 2 일때: 3, 4, 5, 6, 7, ...
k = 3 일때: 6, 9, 12, 15, ...
k = 4 일때: 10, 14, 16, 18, 20, ...
k = 5 일때: 15, 20, 25, 30, ...

해당하는 k 에 대해서 몇개의 만족하는 수를 나열하면 쉽게 규칙을 찾아낼 수 있다..
그리고.. 조만간에 모듈러 합동에대한 것도 공부해봐야겠다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 int f(int limit, int k)
  9 {
 10     if (k == 2) {
 11         if (limit <= 2)
 12             return 0;
 13         return limit-2;
 14     }
 15     else if (k == 3) {
 16         if (limit <= 5)
 17             return 0;
 18         return (limit / 3) - 1;
 19     }
 20     else if (k == 4) {
 21         if (limit <= 9)
 22             return 0;
 23         if (limit >= 10 && limit <= 13)
 24             return 1;
 25         return (limit-10) / 2;
 26     }
 27     if (limit <= 14)
 28         return 0;
 29     return (limit-10) / 5;
 30 }
 31
 32 class SummingArithmeticProgressions {
 33 public:
 34
 35 int howMany(int left, int right, int k)
 36 {
 37     int a, b;
 38     a = f(left-1, k);
 39     b = f(right, k);
 40     printf("a = %d, b = %d\n", a, b);
 41     return b-a;
 42 }
 43
 44 };

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

TopCoder SRM 390 Div1  (2) 2008.02.03
TopCoder SRM 389 Div1  (0) 2008.01.25
TopCoder SRM 388 Div1  (2) 2008.01.16
TopCoder SRM 387 Div1  (4) 2008.01.10
TopCoder SRM 386 Div 2  (4) 2008.01.06
TopCoder SRM 385 Div2 (완료)  (4) 2007.12.30
TopCoder SRM 384 Div2 (완료)  (2) 2007.12.20
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

Comments

  1. 2008.01.02 05:14 Permalink Modify/Delete Reply

    비밀댓글입니다

    • helloneo 2008.01.02 16:54 신고 Permalink Modify/Delete

      앗.. 답변 감사합니다.. Rada님도 탑코더 후기를 포스팅하시네요.. 종종 가서 배워야겠습니다.. ^^

  2. nocut98 2008.01.02 11:31 Permalink Modify/Delete Reply

    일단 k항에 대한 합을 구하면 하나의 식으로 나옵니다.
    (시그마n = n*(n+1)/2 라는 걸 이용하면 되죠)
    k*x + k*(k-1)/2*d
    k가 몇 개 안되므로 그냥 손으로 풉니다.
    k=1 : x
    k=2 : 2x + d : 3,4,5,6,7...
    k=3 : ...
    보통 배수가 되므로 숫자를 쭈욱 늘어놓고 몇 개가 들어갈지 계산식을 세우면 됩니다.
    예를 들면 k=2는 1,2만 빠지면 되니까, x-2가 됩니다. 1,2일 때는 답이 없구요.
    그러면 코드가 아래처럼 간단해 지더군요.
    int calc(int x, int k) {
    switch(k) {
    case 2:
    return max(0, x - 2);
    case 3:
    return max(0, x/3-1);
    case 4:
    if (x<10) return 0;
    else if(10<=x && x<14) return 1;
    else return max(0, x/2-5);
    case 5:
    return max(0, x/5-2);
    }
    }
    int howMany(int left, int right, int k) {
    return calc(right, k) - calc(left-1, k);
    }

    • helloneo 2008.01.02 16:55 신고 Permalink Modify/Delete

      앗..! 답변 감사합니다.. 누군가 답변해줄거라고는 생각도 못했는데.. ^^ 새해복많이 받으세요..~

Leave a Comment


to Top