2012年2月29日水曜日

TopCoder SRM338 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題についておおまかに説明する。

賭けの戦略として以下のことを考えている。最初の勝負では1ドル賭ける。もし賭けにかてば、1ドルを得て、次の勝負では1ドルかける。負けた場合は、1ドルを失って次の勝負で2ドルを書ける(少なくとも手元に2ドル持っているものとする)。もし勝てば2ドルを得て、3回目の勝負では1ドルを賭ける。これでも負ければ2ドルを失い、3回目の勝負では4ドルを賭ける(少なくとも手元に4ドル持っているものとする)。つまり、負けたときは、いつでも次の勝負では掛け金を倍にするということである。勝ったときは1ドルを次の勝負で賭けることになる。

問題ではinitSumという最初の所持金が与えられる。またoutcomeという文字列が与えられる。outcomeのi番目の文字はW(勝利)またはL(敗北)で与えられる。文字はi番目の勝負の結果を表している。すべての勝負を終えた後の残っている金額を返せ。もし、次に賭けようとした額が賭けられない場合は、そこでやめ、そのときに持っているお金の額を返せ。

例えば10ドル手元にあって、勝ち、負け、負け、勝ちの場合は10+1-1-2+4=12ドルとなる。

私の解答はこちら。

public class BettingStrategy {

 public int finalSum(int initSum, String outcome) {
  int nBet = 1;
  int nMoney = initSum;
  for( int i=0 ; i<outcome.length() ; i++ ){
   if( nMoney < nBet ){
    break; // これ以上賭けられない
   }
   if( outcome.charAt(i) == 'W' ){
    nMoney += nBet;
    nBet = 1;
   }else{
    nMoney -= nBet;
    nBet *= 2;
   }
  }
  return nMoney;
 }

}

得点は240.50。

0 件のコメント:

コメントを投稿

フォロワー

ページビューの合計