TopCoder SRM 420

http://www.topcoder.com/stat?c=round_overview&er=5&rd=13511

한국시간으로 10월 2일 오후 8시에 SRM420이 열렸다.
개인적으로 SRM 417 이후로 3주만에 참가하는 SRM이기도 하고 ACM-ICPC예선을 제외하곤 최근 알고리즘 문제풀이를 거의 한적이 없어 약간 긴장이 되었지만 크게 부담갖지 않고 했던것 같다.

한국인이 이렇게 많이 참가한 SRM은 개인적으로 처음!!

250 - SolitaireSimulation

Problem Statement

Consider the following solitaire game: We have a deck of identical cards. Initially, these cards are split into several heaps, with heaps[i] cards on the i-th heap. Each step of the game looks as follows: Pick one card from each of the heaps and make a new heap out of these cards. When describing a position in the game, only the heap sizes matter, their order does not. Clearly, sooner or later a position will repeat and the game will become periodic from that point on. Write a method that takes a int[] heaps and returns the length of the shortest period of the game. In other words, find the smallest number of steps S such that for some X the positions after X and X+S steps are equal.

Notes
-	After some finite number of moves the game must always become periodic.
Constraints
-	heaps will contain between 1 and 50 elements, inclusive.
-	Each element in heaps will be between 1 and 50, inclusive.
-	The sum of all elements in heaps will be between 1 and 50, inclusive.

Solving

Note에서 이 게임이 언젠가는 주기를 가지게 된다고 명시되어 있지만 인풋에 따라 그 주기가 얼마나 커질지는 미지수라는 점이 이 문제의 어려운 점이었던것 같다. 다만 모든 카드의 갯수의 합이 50이하라는 것에 기대를 걸고(주기가 엄청나게 커지지는 않을 것이라는..) 문제에서 설명한데로 구현을 하였다. (250 이니깐...)


#incluce <vector> #include <algorithm> using namespace std; class SolitaireSimulation { public: int periodLength(vector <int> heaps) { int i,j,k; sort(heaps.begin(), heaps.end()); vector<int> deck = heaps; vector<vector<int> > history; history.push_back(heaps); do { int zeros = 0; vector<int> newdeck(deck.size()+1); for (i = 0; i < deck.size(); i++) { newdeck[i] = deck[i]-1; if (newdeck[i] == 0) zeros++; } newdeck[i] = deck.size(); sort(newdeck.begin(), newdeck.end()); deck.assign(newdeck.size() - zeros, 0); for (i = zeros; i < newdeck.size(); i++) deck[i-zeros] = newdeck[i]; for (i = 0; i < history.size(); i++) { if (deck == history[i]) return history.size()-i; } history.push_back(deck); } while(true); return 1; } };

500 - Red Is Good

Problem Statement

You have a deck that contains R red and B black cards. You are playing the following game: You shuffle the deck, and then begin dealing the cards one by one. For each red card you flip you get a dollar, and for each black card you flip you have to pay a dollar. At any moment (including the beginning of the game) you are allowed to stop and keep the money you have. Write a method that will take the ints R and B, and return the expected amount you will gain if you play this game optimally.

Notes
-	During the game, your balance may be negative.
-	We assume that each permutation of the cards in the deck is equally likely.
-	Your return value must have a relative or absolute error less than 1e-9.
Constraints
-	R will be between 0 and 5,000, inclusive.
-	B will be between 0 and 5,000, inclusive.

Solving

V(r, b)를 r개의 레드카드와 b개의 블렉카드가 남아있는 상태에서의 기대값을 나타내는 함수라고 정의하자.
r개의 레드카드와 b개의 블렉카드가 남아있는 상태를 가정하면, 이 상태에서 한 장의 카드를 선택했을 때 레드카드일 가능성은 r/(r+b)이고 블렉카드가 나올 가능성은 b/(r+b)이다. 뽑은 카드가 레드카드라면 기대치는 V(r-1, b) + 1이 되고 블렉카드인 경우에는 V(r, b-1) -1 이 된다. 따라서 V(r, b) = max(0, r/(r+b) * (V(r-1, b) + 1) + b/(r+b) * (V(r, b-1) -1))이라는 점화식을 얻을 수 있다.
이제 DP로 코딩하는 일만 남았다.
double 형으로 5000*5000의 배열이 메모리제약으로 할당되지 않는다. 하지만 V(r, b)는 V(r-1,b)와 V(r, b-1)만을 사용하기 때문에 일차원 배열만을 사용하여 문제를 해결할 수 있다.

#include <algorithm> using namespace std; double D[2][5005]; struct RedIsGood { double getProfit(int R, int B) { int r,b,s; for (r=1; r<=R; r++) { s=(r&1); D[s][0]=D[!s][0]+1.0; for (b=1; b<=B; b++) D[s][b]=max(0, r/double(r+b)*(D[!s][b]+1)+b/double(r+b)*(D[s][b-1]-1)); } return D[s][B]; } };


1000 - 1000을 풀 수 있는 날이 언제 올까요