TopCoder SRM429 Div2 250Pts

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

AAAAとBBというポリオミノ(複数の正方形をつなげた図形)が無限に与えられている。"."あるいは"X"という文字で埋められたregionという文字列が与えられる。あなたはこれに対し、Xという文字を与えられたポリオミノで隙間なく覆わなければならない(ポリノミオが重なってもならない)。残された"."はいじることなく、Xという文字はAあるいはBという文字で覆った結果の文字列を返すようにせよ。もし、そのような結果が返せないようであれば、"impossible"という文字列を返せ。もし、複数の解答があるようであれば、辞書順で値が最も小さくなるような文字列を選ぶようにせよ。

私の解答はこちら。

public class LinearPolyominoCovering {

 public String findCovering(String region) {
  StringBuilder sb = new StringBuilder();
  int nX = 0;
  for( int i=0 ; i<region.length() ; i++ ){
   if( region.charAt(i) == '.' ){
    if( nX % 2 != 0 ) return "impossible";
    while( nX > 0 ){
     if( nX >= 4 ){
      sb.append("AAAA");
      nX -= 4;
     }else if( nX >=2 ){
      sb.append("BB");
      nX -= 2;
     }
    }
    sb.append('.');
    continue;
   }else{
    nX++;
   }
  }

  if( nX % 2 != 0 ) return "impossible";
  while( nX > 0 ){
   if( nX >= 4 ){
    sb.append("AAAA");
    nX -= 4;
   }else if( nX >=2 ){
    sb.append("BB");
    nX -= 2;
   }
  }
  return sb.toString();
 }

}

得点は229.55/250、1回のsubmitでシステムテストクリア。辞書順で値が最小になるというのは、できるだけAでregionを埋めろということに言い換えればOKです。同じコードが繰り返しているので、そこはリファクタリングの余地があるかもしれません(速度を競う競技プログラミングではリファクタリングしている余裕が無いといえば無いのですが)。