어제 새벽 1시에 열린 매치.. 이번에도 삽질하면서 rating이 더 떨여졌다.. ㅠ_ㅠ
어제 술좀 마시고 늦게 들어와서 피곤한 상태에서 했더니.. 이거 머리가 안돌아가네..
500점 짜리는 좀 생각해보면 풀수 있었는데.. 아쉽다..
문제가 좀 트리키 했는지.. rating은 생각보다 많이 떨어지지는 않았다..
div1은 다음 기회에.. -_-

사용자 삽입 이미지



Level1 - Towers

나에게 myUnit 만큼의 병사가 있가 numT개의 타워를 부셔야 한다. 각각의 타워는 hpT 만큼 때려야 부술수 있다.. 각 병사가 한번에 1씩 공격한다. 각 병사들은 임의의 타워를 공격하도록 조종할 수 있다.. 이때 최소 몇 round까지 가야 이길수 있는지 구하기.. 못이기면 -1 return

처음에 무슨말인지 몰라서 한참 생각했다.. 각 병사들이 모두 같은 타워를 공격할 필요는 없다는게 핵심..;
나눗셈과 모듈러연산을 이용하여 그냥 시뮬레이션 하면 되는 문제..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 class Towers {
  9 public:
 10
 11 int attack(int myUnits, int hpT, int attackT, int numT)
 12 {
 13     int r, a;
 14     int left;
 15     r = 1;
 16     left = 0;
 17     while (1) {
 18         a = (myUnits+left) / hpT;
 19         left = (myUnits+left) % hpT;
 20         numT -= a;
 21         if (numT <= 0)
 22             break;
 23         myUnits -= numT * attackT;
 24         if (myUnits <= 0)
 25             return -1;
 26         r++;
 27     }
 28 printf("return %d\n", r);
 29     return r;
 30 }
 31
 32 };




Level2 - TwoLotteryGames

1~n 범위의 n개의 숫자중에서 m개를 선택한다. 이렇게 두번 선택했을때 각각의 뽑은 숫자 셋 중에 겹치는 수가 k개 이상일 확률 구하기..

n의 최대 크기가 8인것을 보고 그냥 backtracking을 통해서 모든 경우의 수를 다구해서 계산했는데.. 설마 했더니 time limit에 걸렸다.. ㅠ_ㅠ 젠장.. 그런데 나와 같은방법으로 풀었는데 bitmask를 이용한 녀석은 pass했다.. 흐미.. 뭐 이래~~!!

매치 에디토리얼을 참조하여 풀었다..

n개의 숫자 중에서 m개를 선택하는것을 두번 할때 서로

한개의 숫자가 겹칠 확률은 mC1 * (n-m)C(m-1) / nCm
두개의 숫자가 겹칠 확률은 mC2 * (n-m)C(m-2) / nCm
...
...

아.. 역시 확률은 정말 쥐약이구만.. ㅠ_ㅠ

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <set>
  7 using namespace std;
  8
  9 int combi(int n, int r)
 10 {
 11     int i, j;
 12     int c;
 13     c = 1;
 14     for (i = 1, j = n; i <= r; i++, j--) {
 15         c *= j;
 16         c /= i;
 17     }
 18     return c;
 19 }
 20
 21 class TwoLotteryGames {
 22 public:
 23
 24 double getHigherChanceGame(int n, int m, int k)
 25 {
 26     int p, a;
 27     int i;
 28     p = 0;
 29     a = combi(n, m);
 30     for (i = k; i <= m; i++) {
 31         p += combi(m, i) * combi(n-m, m-i);
 32     }
 33 printf("return %lf\n", (double)p / (double)a);
 34     return (double)p / (double)a;
 35 }
 36
 37 };




Level3 - BarracksEasy




to be updated..

 

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

탑코더 스름 426 디비젼 1  (0) 2008.11.25
TopCoder SRM 425 Div 2 (완료)  (0) 2008.11.13
TopCoder SRM 422 Div 1  (4) 2008.10.19
TopCoder SRM 421 Div 1  (0) 2008.10.12
TopCoder SRM 420 Div 2  (0) 2008.10.03
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 413 Div 1  (0) 2008.08.08
TopCoder SRM 412 Div 1  (0) 2008.08.01

to Top