수요일 밤 12시에 열렸던 매치.. 완전히 삽질한 매치였다.. 역대 최악의 성적을 기록.. ㅠ_ㅠ 방에서 최하위 디비젼 전체에서도 끝에서 두번째를 기록하고말았다.. ㅠ_ㅠ 흠.. 정말 쪽팔리구만..;; 코딩 시간이 끝나자마자 나는 두문제 다 fail할거라는 것을 직감.. 그냥 챌을 많이하려고했는데.. 블챌이 다 실패하고 말았다.. 젠장.. 그냥 가만히 있어도 중간은 가는데.. ㅠ_ㅠ 문제도 정말 짜증나는 셋이 나왔다.. 1000점짜리 문제를 제외하고.. 이런 문제들 진짜 싫다.. rating은 무려 182점 폭락.. 역대 최고의 하락이었다..;; 그래도 아직 div1 유지한게 신기하다..


사용자 삽입 이미지



Level 1 - ArithmeticProgression

초항이 a0 이고 공차가 d인 등차수열 A가 주어진다..
수열 seq(i) = floor( A(i+1) ) 이라고 한다..
input으로 수열 a0와 seq가 들어올때 가능한 d의 최소값 구하기.. 가능한 d가 없다면 -1 return..

언듯보면 간단한 문제인것 같기도 하면서.. 또 어려운 문제이다.. 나는 도저히 솔루션이 생각이 안나서 binary search를 시도했다.. 사실 floating point number에 대해서 binary search를 시도하는게 상당히  위험한짓이다.. precision을 높이자니 TLE 날것같고.. precision을 낮추면 WA날것같고.. 나중에 다른사람 소스를 보니 의외로 나처럼 binary search를 시도한 사람이 많았다.. 그사람들 다 system test때 fail했다.. 나를 비롯해서.. ㅠ_ㅠ 다들 TLE에 걸렸나보다..

쉽지않은 문제이다.. 솔루션도 생각해내기 힘들고.. 생각해냈더라도 precision error를 피하기가 힘들다..
match editorial을 참고해서 풀었다..

일단 공차 d = (seq[i] - a0) / (i+1) 중에서 가장 큰 값이 되어야 한다.. 고 한다.. -_- 그래야 최악의 경우도 만족시킬 수 있다.. 그리고 이렇게 구한 d가 정말로 다 맞는지 다음 식을 통해 확인해야 한다.

seq[i] == floor(a0 + (i+1) * d)

문제는 precision error인데 부동소수점을 분모와 분자로 나눠서 두개의 integer로 관리해야한다.. 흠.. 이런 방식은 이론으로만 봤는데.. 실제로 이렇게 풀어야 AC가 나는 경우는 처음이군..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <cmath>
  7 using namespace std;
  8
  9 class ArithmeticProgression {
 10 public:
 11
 12 double minCommonDifference(int a0, vector <int> seq)
 13 {
 14     int n, i;
 15     long long no, den;
 16     no = 0;
 17     den = 1;
 18     n = seq.size();
 19     for (i = 0; i < n; i++) {
 20         if (no * (i+1) < (seq[i] - a0) * den) {
 21             no = seq[i] - a0;
 22             den = i+1;
 23         }
 24     }
 25     for (i = 0; i < n; i++) {
 26         if (seq[i] != (int)(a0 + (i+1) * no / den))
 27             return -1;
 28     }
 29     return (double)no / (double)den;
 30 }
 31
 32 };




Level2 - InfiniteSequence2

A(i) =
if i <= 0 then 1
else then A(floor((i / p) - x) + A(floor((i / q) - y)

일때 A(n) 을 구하는 문제..

정말 어이없이 틀렸다.. 젠장.. 쉽게 recursion으로 구할수 있는데.. TLE에 걸렸다.. 처음 TLE도 생각해보았는데.. p, q가 2 이상이므로 i가 최소한 1/2로 감소하므로.. 시간이 별로 안걸릴 줄 알았는데.. 내가 너무 과소평가했다.. ㅠ_ㅠ 이문제 역시 같은 이유로 fail한 사람이 무지 많았다.. 이따위 문제를 내다니.. 문제 출제자 도대체 누구야..

정말 드러운 문제이다.. full memorization을 하면 MLE가 나고.. memorization을 안하면 TLE가 난다.. 헐.. 대략 2000000까지만 memorize해서 풀었다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 int p, q, x, y;
  9 long long memo[2000001];
 10
 11 long long recur(long long u)
 12 {
 13     if (u <= 0)
 14         return 1;
 15     if (u > 2000000)
 16         return recur((u/p)-x) + recur((u/q)-y);
 17     if (memo[u] != -1)
 18         return memo[u];
 19     return memo[u] = recur((u/p)-x) + recur((u/q)-y);
 20 }
 21
 22 class InfiniteSequence2 {
 23 public:
 24
 25 long long calc(long long n, int P, int Q, int X, int Y)
 26 {
 27     long long res;
 28     p = P;
 29     q = Q;
 30     x = X;
 31     y = Y;
 32     memset(memo, -1, sizeof(memo));
 33     res = recur(n);
 34     return res;
 35 }
 36
 37 };




Level3 - TreeCount




to be updated..

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

TopCoder SRM 420 Div 2  (0) 2008.10.03
TopCoder SRM 418 Div 2  (0) 2008.09.21
TopCoder SRM 417 Div 2  (0) 2008.09.13
TopCoder SRM 416 Div2  (0) 2008.09.07
TopCoder SRM 414 Div 1  (0) 2008.08.17
TopCoder SRM 412 Div 1  (0) 2008.08.01
TopCoder SRM 410 Div 1  (2) 2008.07.20
TopCoder SRM 409 Div 1 (완료)  (0) 2008.07.11
TopCoder SRM 408 Div 1  (0) 2008.07.03
TopCoder SRM 407 Div 1  (2) 2008.06.28

to Top