2013年7月7日日曜日

TopCoder SRM469 Div2 250Pts

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

ジョンとブラスはとても面白い映画を見に行こうとしている。彼らは同じ並びの隣り合った席に座りたいと思っている。映画館はn行m列のシートからなる。行方向は先頭から最後尾へ向けて1からnと番号づけられ、左から右に1からmと順に番号づけられている。いくつかのシートは既に埋まっており、ジョンとブラスは任意の空いている席を予約することができる。row、seatという整数型の配列が与えられ、そのi番目の要素row[i]、seat[i]は予約された席の位置を示している。すべての残りの席は空いている。ジョンとブラスが同じ並びで隣り合って座ることができる場合の数を返せ。なお、ジョンとブラスの位置までは考慮しないものとする。つまりジョンとブラスが逆に座っても同じ席の予約なので1通りとしてカウントするということである。

私の解答はこちら。

public class TheMoviesLevelOneDivTwo {

 public int find(int n, int m, int[] row, int[] seat) {
  boolean[][] isReserved = new boolean[n][m];
  for( int i=0 ; i<row.length ; i++ ){
   isReserved[row[i]-1][seat[i]-1] = true;
  }
  int nSeat = 0;
  boolean isPrevReserved = true;
  int nFree = 0;
  for( int i=0 ; i<n ; i++ ){
   nFree = 0;
   isPrevReserved = true;
   for( int j=0 ; j<m ; j++ ){
    if( isReserved[i][j] ) {
     isPrevReserved = true;
     nFree = 0;
    }else{
     isPrevReserved = false;
     nFree++;
    }
    if( nFree >= 2 ) nSeat++;
   }
  }
  return nSeat;
 }

}

得点は220.85/250、1回のsubmitでシステムテストクリア。「並び」、「行」と訳したのですが、まとめた方がよかったですかねぇ。

0 件のコメント:

コメントを投稿

フォロワー

ページビューの合計