2012年12月16日日曜日

TopCoder SRM444 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文についておおまかに説明する。画像があるので、必要に応じて本文を見て欲しい。

"4Blocks"は、特別な盤で二人のプレーヤーが協調するゲームである。盤は1*1の正方形のセルからなる格子である。格子は高さが2である。2種類の異なるブロックがある。1と4というブロックである。1は1*1、4は2*2のサイズである。あなたはブロックを辺が格子の辺に沿うように配置し、二つのブロックが重ならないようにしなければならない。最終スコアは各セルにある値の和である。1は1ポイントの価値があり、4は、セルが4つを各セルが4ポイントの価値で覆われることから、16ポイントの価値がある。あなたの友人は自分の番で盤に1のブロックをいくつか置く。現在の設定はgrid[]という文字列型配列で与えられる。i番目の文字列のj番目の要素はi行j列の上京を表しており、"."であれば空、"1"であれば、友人が1をそのセルに置いたということになる。あなたの番がやってきて、1と4のブロックを置くことができるが、既に置かれたブロックは除去できないものとする。 達成可能な点数の最高点を返せ。

私の解答はこちら。

public class FourBlocksEasy {

 public int maxScore(String[] grid) {
  int score = 0;
  int hPos = 0; // 現在注目する位置(ここと下、右、右下に注目する)
  int width = grid[0].length(); // 盤面の横幅
  while( true ){
   if( hPos >= width ) break; // 右端まで見たら終了
   if( grid[0].charAt(hPos) == '.' && grid[1].charAt(hPos) == '.' ){
    if( hPos == width-1 ){ // 右端まで来ていたら1を上下に置いて終了
     score += 2;
     break;
    }
    if( grid[0].charAt(hPos+1) == '.' && grid[1].charAt(hPos+1) == '.' ){
     score += 16; // 2*2のスキマがあるので4のブロックを置ける
     hPos += 2;
    }else{ // そうでなければ、1のブロックを上下において一つ右へ進める
     // 4足して二つ右に進めても良かったですね...
     score += 2;
     hPos++;
    }
   }else{ // 上下のどちらかに1が既に埋まっていた場合
    score += 2;
    hPos++;
   }
  }
  return score;
 }

}

得点は233.05/250、1回のsubmitでシステムテストクリア。左から順に4が置けるかチェックしていくだけでOK。

0 件のコメント:

コメントを投稿

フォロワー

ページビューの合計