Hatena::Grouptopcoder

prosho奮闘記 RSSフィード

2011-12-20

SRM 527 Div2

11:58 | はてなブックマーク - SRM 527 Div2 - prosho奮闘記

結果は 224.28+0+0+(50-25)=249.28で144位。877→968(+91)。

Easyで慎重になりすぎたのとMediumでメモ化再帰の実装を時間に追われてミスったのが反省点。

P8XGraphBuilder (Medium解き直し)

class P8XGraphBuilder {
public:
vector <int> SCORES;
int memo[52][52][110];

int rec(int d, int num, int rest){ 
  
  if(memo[d][num][rest] != -1) return memo[d][num][rest];
  int res;
  if(rest == 0 && num == 0){ 
      res = 0;  
  } 
  else if(rest <= 0 || num <= 0 || d <= 0) res = -INF; 

  else{ 
     res = max(rec(d-1, num, rest), rec(d, num-1, rest-d) + SCORES[d-1]); 
  } 
  return memo[d][num][rest] = res;
} 

int solve(vector <int> scores) { 
  int n = scores.size()+1; 
  memset(memo, -1, sizeof(memo)); 
  SCORES = scores; 
  int res = rec(n-1, n, 2*(n-1)); 
  return res;
}
};


プロコンを始めて四ヶ月、ようやくメモ化再帰とDPが実装できるようになって来ました。

基本は、

全探索のコードを考える→(TLEの可能性)→メモ化→(スタックオーバーフローの可能性)→DP

の順番で考えること。

最初の「全探索のコードを考える」のが一番重要で難しい。