Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-05-27

[][] Project Euler Problem 109 08:49 はてなブックマーク -  Project Euler Problem 109 - 練習帳

問題文

 http://projecteuler.net/index.php?section=problems&id=109

要約

 ダーツで次の条件を満たすポイントの組み合わせの数を求めよ。

  • 3 投以内
  • ポイントの合計は 100 点未満
  • 最後の 1 投はダブル(50 点のインナーブルも含む)
  • 最後の 1 投以外は順不同(順序を変えて同じになる組み合わせは 1 通りとみなす)
    • S1, D2, D4 と D2, S1, D4 は同じ組み合わせ
    • S1, D4, D2 と S1, D2, D4 は異なる組み合わせ

方針

 ダブって数えないようにするのが難しい所,例えば 5 の分割は

5 = 5
    4 + 1
    3 + 2
      + 1 + 1
    2 + 2 + 1
      + 1 + 1 + 1
    1 + 1 + 1 + 1 + 1

のように降順に並べればダブらずに数えられる。今回もこれと同じように取りうるポイントを適当な順番に並べ,遡らずにとれば良い。ただし,最後の 1 投は順不同でないので個別に考える。

コード例(c++)

#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int n = 100;
int memo[100][4][100] = {}; // memoization

// container of points. each is represented as (original point, factor)
vector<pair<int, int> > p; 

bool comp(pair<int ,int> a, pair<int ,int> b){
  if(a.first * a.second != b.first * b.second) 
    return a.first * a.second < b.first * b.second;
  return a.first < b.first;
}

// resp = residual point 
// resa = residual attempt
int check(int resp, int resa, int pos){
  if(resp < 0) return 0;
  if(resp == 0) return 1;
  if(resp > 0 && resa == 0) return 0;
  if(memo[resp][resa][pos] >= 0) return memo[resp][resa][pos];
  
  int ret = 0;
  for(size_t i = pos;i < p.size();i++){
    ret += check(resp-p[i].first * p[i].second, resa - 1, i);    
  }  
  return memo[resp][resa][pos] = ret;
}

int main(){
  memset(dp, -1, sizeof(dp));  

  // preparation to sort points
  for(int i = 1; i <= 20; i++){
    for(int j = 1; j <= 3; j++){
      p.push_back(make_pair(i, j));
    }
  }
  p.push_back(make_pair(25,1));
  p.push_back(make_pair(50,1)); 
  sort(p.rbegin(), p.rend(), comp);
  
  int ans = 0;
  for(int i = 0; i < n; i++){
    for(int j = 1; j <= 20; j++){
      ans += check(i - 2 * j, 2, 0);
    }
    ans += check(i - 2 * 25, 2, 0);
  }
  cout << ans << endl;  
  return 0;
}

分析

 ダブらないで数えるのが大変だった。はじめのコードでは,最後に獲得した点数と倍率を記憶し「同じ点数ならば最後に獲得したポイントより倍率が同じか小さくなければならないが,真に点数が下がっていたら倍率は何でもよい」を自分で実装していた。上のコードではポイント間に順序を定めることで,それをすべて sort に任せている。STL様々。