TopCoder SRM420 Div2 250Pts

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

カードのデッキがある。それぞれのカードは黒ないしは赤である。以後、Bという文字を黒のカード、Rという文字を赤のカードとする。デッキの上から下に向かってカードを並べることによって、deckという文字列を生成する(訳注：つまり、deckの中身はRとBという文字列を利用して構成する)。次に、deckのすべてのカードを挿入して新しいデッキを作成したい。まず始めに、新しいデッキは空であるとする。次に古いデッキの上から下に向かってカードを処理していく。deckのi文字目に対応するカードを処理するというのは、古いデッキからカードを取り出し、新しいデッキにabove[i]だけ上にカードがある位置にカードを挿入するということになる。

deckという古いデッキと、above[]という新しいデッキへの挿入位置が与えられたとき、deckと同様な形式の文字列に変換された新しいデッキを表す文字列を返すメソッドを作成せよ。

例えばdeck="BRBRR"、above={0, 0, 1, 0, 3}であれば、"RRBRB"となる。これは初めにBを挿入(状態：B)、次に上に0枚がある位置にRを挿入(状態：RB)、次に上に1枚ある位置にBを挿入(状態：RBB)、...とすることによって得られる結果である。

私の実装はこちら。

public class DeckRearranging {

 public String rearrange(String deck, int[] above) {
  String ret = "";
  for( int i=0 ; i<above.length ; i++ ){
   String first = ret.substring(0, above[i]); // 新しいdeckを分けたときに上にあるカード群
   String second = ret.substring(above[i]); // 新しいdeckを分けたときに下にあるカード群
   ret = first + deck.charAt(i) + second; // 新しいdeckにカードを挟み込む
  }
  return ret;
 }

}

得点は221.63/250、1回のsubmitでシステムテストクリア。中央値は約212点。StringBufferのinsertを利用するのもいいかもしれません。