2012年5月8日火曜日

TopCoder SRM383 Div2 250Pts

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

あなたは新しい家を建築中で、ある部屋に床板を敷こうとしている。設計師は床板のレイアウトをデザインしており、それに対し何枚のボードを買う必要があるか知りたいと思っている。各板は1単位の幅を持ち、すべて任意の正の整数の値をとり得る。部屋は長方形の形状をしており、板は壁とは平行に、1単位の正方形の格子の位置に配置するものとする。 layout[]という、床板のレイアウトを表す文字列が与えられる。i番目の文字列のj番目の要素は正方形の格子の(i, j)番目の位置を表しており、その内容は"-"または"|"になる。それらは床板の方向を表している。もし"-"という2文字がi番目の文字列に隣り合っていれば、それは東西方向の床板1枚を表す。同様に"|"については、jが同じで隣り合う配置であれば、南北方向の床板1枚を表すことになる。レイアウト通りに配置するときに必要となる床板の枚数を返せ。

public class FloorLayout {
 public int countBoards(String[] layout) {
  int nBoard = 0;
  nBoard += count(layout, '-');
  String[] transpose = new String[layout[0].length()]; // layoutを転置した後の文字列
  for( int i=0 ; i<layout[0].length() ; i++ ){
   StringBuilder sb = new StringBuilder();
   for( int j=0 ; j<layout.length ; j++ ){
    sb.append(layout[j].charAt(i));
   }
   transpose[i] = sb.toString();
   sb.delete(0, sb.length());
  }
  nBoard += count(transpose, '|');
  return nBoard;
 }
 // typeという文字の板が何枚必要になるか、平行方向についてのみカウント
 // "-"にはそのまま適用可能、"|"についてはlayoutを転置することで適用可能。
 private int count(String[] layout, char type){
  int nBoard = 0;
  for( int i=0 ; i<layout.length ; i++ ){
   char prev = ' ';
   for( int j=0 ; j<layout[0].length() ; j++ ){
    char c = layout[i].charAt(j);
    if( c == type ){
     if( prev != type ) nBoard++;
    }
    prev = c;
   }
  }
  return nBoard;
 }
}

得点は181.76/250、1回のsubmitでシステムテストクリア。中央値は約173点。

0 件のコメント:

コメントを投稿

フォロワー

ブログ アーカイブ

ページビューの合計