TopCoder SRM457 Div2 250Pts

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

ジョンとブラスはパズルが好きである。彼らは正方形の盤面にチェッカーを置く新しいゲームをしている。盤面は格子状で同じ数の行と列を持つ。ゲームはジョンがチェッカーを盤面のセルに置くことから始まる。つぎにR[i]が各行iに対して計算される。R[i]はi番目の行にあるチェッカーの数である。盤面のi列目のチェッカーの数がR[i]になるようにブラスはチェッカーを動かさなければならない。R[i]はチェッカーの初期配置から計算され、途中で修正されないことに注意。1回のターンでブラスはチェッカーを上下左右の空いているセルに動かすことができる。目標に届くまで必要なターンを使うであろう。board[]という文字列型配列が与えられる。i番目の要素のj番目が'C'であれば盤面のi行j列のセルにチェッカーがあり、そうでなければ'.'となっている。最後の配置の状態を入力と同じ形式を使って返せ。配収的な配置は多い可能性があるので、辞書順で最も早くなるものを返せ。

私の解答はこちら。

public class TheSquareDivTwo {

 public String[] solve(String[] board) {
  int size = board.length; // 行、列のサイズ
  char[][] cells = new char[size][size]; // i行j列のセルに入る値を記録
  int[] nC = new int[size]; // 各列方向にいくつ置くかを記録する
  for( int i=0 ; i<board.length ; i++ ){
   for( int j=0 ; j<size ; j++ ){
    if( board[i].charAt(j) == 'C' ) nC[i]++;
   }
  }
  // 列ごとに配置。辞書順で最初に来る物ということなので、上に'.'、下に'C'が
  // 来るようにする必要がある。'C'の数はnC[i]を参照すればよい。
  for( int j=0 ; j<size ; j++ ){
   for( int i=0 ; i<size ; i++ ){
    if( size - nC[j] - i > 0 ){
     cells[i][j] = '.';
    }else{
     cells[i][j] = 'C';
    }
   }
  }
  for( int i=0 ; i<size ; i++ ){ // 文字型配列を文字列に変換
   board[i] = String.valueOf(cells[i]);
  }
  return board;
 }

}

得点は169.41、1回のsubmitでシステムテストクリア。本文は分かりにくかったのですが、出力例を見てアルゴリズムをようやく理解。