어제 새벽 2시에 있었던 TCO09 온라인 1라운드..
역시 예상대로 그냥 가볍게 탈락하고 말았다..~ 흑흑.. ㅠ_ㅠ
작년같은경우 -25점이라는 어처구니없는 점수로 탈락했는데..
이번에는 나름 250도 pass하고.. 작년보다는 훨씬 발전했다는 생각이 든다..

이번에 참가하면서 느낀점은..
경쟁이 작년에 비해 엄청나게 치열해졌다는것..
그 결과.. 나름 실력있는 사람들도 고전한 경우가 많았다.. ㅎㅎ

그리고 역시 직장인의 한계를 많이 느낀다..
예전처럼 대회를 위해 올인해서 공부한 경우와..
지금처럼 짬을내서 취미로 하는것은 많은 차이가 있는것 같다.. 쩝

이번 문제셋은 500보다 1000이 더 쉬워보이는데.. 그냥 나만의 착각인가..? ㅋ
500은 도저히 모르겠고 1000 open할까 말까 하다가 열어서 봤는데..
대략 DP 솔루션이 떠올라서 코딩하다가 결국 시간내에 완료하지 못했다..
다른 사람들 보면 대략 500에서 말린 사람들 많은거같은데.. ㅎㅎ

사용자 삽입 이미지
우리 방 사람들인데.. 이렇게 red랑 yellow가 많은 방에서 참가해본게 처음인듯.. ㅋㅋ
특히나 ardiankp나 krzysan은 UVa에서도 매우 유명한 id인데..
게다가 acm-icpc world finalist에 빛나는 한국인 한명도 있다..~~
아.. 잘하는사람들이 도대체 왜이리 많은거야..

사용자 삽입 이미지
사용자 삽입 이미지



Level1 - SequenceSums
N과 L이 주어질때, 연속된 L개 이상의 수의 합이 N이 되는 최소의 리스트 구하기..

예를들어 N = 18,  L = 2 일때..
18 = 3 + 4 + 5 + 6 도 되고.. 18 = 5 + 6 + 7 도 되는데..
L 보다 크거나 같으면서 크기가 최소인 리스트는 {5, 6, 7} 이 된다

이 문제는 다양한 풀이법이 있는듯 하다..
나같은 경우 길이를 고정시켜놓고 등차수열의 초항을 binary search해서 찾았다..
이런 방법을 parametric search 라고 하는 것 같다..

문제 풀다가 중간에 등차수열의 합 공식이 생각이 안나서.. 예전에 정리해둔 팀노트를 급 찾아보았다..
아.. 중딩 수학이 기억이 안나.. ㅠ_ㅠ;;

n항 까지의 합 = n * (2 * 초항 + (n-1) * 공차) / 2

  1 #include <iostream>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 class SequenceSums {
  9 public:
 10
 11 vector <int> sequence(int N, int L)
 12 {
 13     long long left, right, mid, k;
 14     int i, j, sol;
 15     vector<int> res;
 16     sol = -1;
 17     for (i = L; i <= 100; i++) {
 18         left = 0;
 19         right = N;
 20         while (left <= right) {
 21             mid = (left+right) / 2;
 22             k = ((long long)i*(2*mid+(i-1))) / 2;
 23             if (k == N) {
 24                 sol = mid;
 25                 break;
 26             }
 27             else if (k < N) {
 28                 left = mid+1;
 29             }
 30             else {
 31                 right = mid-1;
 32             }
 33         }
 34         if (sol == -1)
 35             continue;
 36         else
 37             break;
 38     }
 39 printf("sol = %d\n", sol);
 40     res.clear();
 41     if (sol == -1)
 42         return res;
 43     for (j = 0; j < i; j++) {
 44         res.push_back(sol+j);
 45     }
 46     return res;
 47 }
 48
 49 };



Level2 - KthProbableElement
lowerBound와 upperBound 사이의 수 중에 M개를 뽑을때 (중복순열), K번째 작은 수가 N과 같을 확률 구하기..


to be updated..



Level3 - Unicorn
chess에서 unicorn이 움직이는 방법은 knight의 update버전으로 한방향으로 3칸 이상 그리고 그 직각 방향으로 2칸 이상 움직일 수 있다.. 즉, 주위의 몇칸만을 제외하고 모든 칸을 갈 수 있다는 의미..
input으로 체스판과 string이 주어질때, string 순서대로 unicorn을 이동시킬 수 있는 경우의 수 구하기..
맨 처음에는 아무칸에서 시작할 수 있다..


to be updated..

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

TopCoder SRM 442 Div 1  (11) 2009.06.14
[SRM 441] 탑코더 아레나.. 중국 뉴비들에게 DDOS공격 받고 사망..  (0) 2009.05.28
TopCoder SRM 440 Div 1 - 드디어 Yellow 등극..  (0) 2009.05.14
말많고 탈많았던 SRM 438  (4) 2009.04.20
TopCoder SRM 437 Div 1  (0) 2009.03.25
TCO09 Qual 3 (완료)  (0) 2009.03.05
TCO09 Qual 2  (0) 2009.03.01
TCO09 Qual 1  (0) 2009.02.25
TopCoder SRM 434 Div 1  (0) 2009.02.10
TopCoder SRM 432 Div 1  (0) 2009.01.07

to Top