Hatena::Grouptopcoder

hotokuの日記@topcoder部 このページをアンテナに追加 RSSフィード

 | 

2012-07-09

SRM 549

| 23:31

easyのみ。

easy BallAndHats

  • DPで解いた。p[i][j]は、ボールの入った帽子の入れ替えをj回行った後にiにボールがある確率
  • 問題の条件をよく考えると、ボールの入った帽子の入れ替えを1回行う毎に「1にボールがある」と「0 or 2にボールがある」の状態を交互に繰り返すだけなので、DPで確立を明示的に計算しなくても解けたようだ。
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;

double p[3][1010];


class BallAndHats{
public:
  int getHat(string hats, int numSwaps);
};


int BallAndHats::getHat(string hats, int numSwaps){
  for(int i = 0; i < 3; ++i){
    p[i][0] = hats[i]=='o' ? 1 : 0;
  }
  for(int i = 1; i <= numSwaps; ++i){
    p[0][i] = 0.5*p[1][i-1];
    p[1][i] = p[0][i-1] + p[2][i-1];
    p[2][i] = 0.5*p[1][i-1];
  }
  int ret=0;
  for(int i = 0; i < 3; ++i){
    if(p[i][numSwaps]>p[ret][numSwaps]) ret = i;
  }
  return ret;
}

Medium

Div1 easyと同問題っぽい。要復習。

 |