TopCoder SRM223 Div2 500Pts

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

半分赤、半分黒のデッキ（カードの集まり）のカードゲームをしている。友人はカードをシャッフルして、あなたはデッキをどこかで切る(デッキを切るというのは途中で分けて、上にあるカードをそのまま下に置くということである)。友人は切られたところから順番にカードを表にし、もし途中で赤が出た回数が黒が出た回数を上回ったらあなたは負けとなる。一度もそのようなことが起こらなければあなたの勝ちになる。何度か連続して負けたあなたはずるがしたくなった。そこでルールを破ってカードをこっそり見て、どこで切れば勝てるか見た。さて、deckというR(赤)、B(黒)という文字からなる文字列型変数が与えられる。文字列の先頭がデッキの一番上を示している。デッキを切った後にある一番上のカードを示すインデックスを返すメソッドを作成せよ。もし、複数勝てる方法があるのであれば、インデックスが最小になるものを返せ。

例えばdeck="BRBRBR"であれば0(つまりカードの順序は不変)、2(2枚最後尾に動かす)、4が条件を満たすが、最小の値として0を返すことになる。

私の解答は以下の通り。

public class BlackAndRed {
 public int cut(String deck) {
  int[] rNum = new int[deck.length()];
  int[] bNum = new int[deck.length()];

  for( int i=0 ; i<deck.length() ; i++ ){
   if( deck.charAt(i) == 'R' ){ // R,Bの累積枚数をカウント
    rNum[i]++;
   }else{
    bNum[i]++;
   }
  }
  int idx = 0;
  for( int i=0 ; i<deck.length() ; i++ ){
   boolean isOK = true;
   int[] rr = new int[deck.length()-i];
   int[] bb = new int[deck.length()-i];
   rr[0] = rNum[i];
   bb[0] = bNum[i];
   // i番目以降の部分配列で、R、Bの累積枚数を配列で表現
   for( int j=1 ; j<rr.length ; j++ ){
    rr[j] = rNum[j+i]+rr[j-1];
    bb[j] = bNum[j+i]+bb[j-1];
   }
   for( int j=0 ; j<rr.length ; j++){
    if( bb[j] - rr[j] < 0){ // Rの枚数がBの枚数より多くなった
     isOK = false;
     break;
    }
   }
   if( isOK ){
    idx = i;
    break;
   }
  }
  return idx;
 }
}

得点は180.37/500。部分配列の累積和をとる関数でバグを出していて、printデバッグを行う羽目に。問題はブルートフォース的に解いている。i番目で切ると仮定して、その後のRとBの累積枚数を数え、途中でRの枚数が上回ればダメ、そうでなければOKという方針で回答している。