TopCoder SRM221 Div2 250Pts

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

小文字のみからなるstrが与えられる。このとき二つの文字列x、yを返すようにせよ。ただし、x、yは次の条件を満たす。

• xとyをくっつけるとstrになる
  
• x中の"a"の数と、y中の"b"の数は等しい
  
• 複数のx、yの候補がある場合は、xの長さが最長になるものを返す
  

私の解答は以下の通り。

public class EqualSubstrings {
 public String[] getSubstrings(String str) {
  String[] ret = {"",""};
  for( int i=0 ; i<=str.length() ; i++ ){ // i=str.lengthまで検討が必要
   String first = str.substring(0,i);
   String second = str.substring(i); // 2つの文字列候補を生成
   int na = 0;
   int nb = 0;
   for( int j=0 ; j<first.length() ; j++ ){
    if( first.charAt(j) == 'a' ) na++;
   }
   for( int j=0 ; j<second.length() ; j++){
    if( second.charAt(j) == 'b' ) nb++;
   }
   if( na == nb ){
    ret[0] = first;
    ret[1] = second;
   }
  }
  return ret;
 }
}

得点は127.55/250、中央値は約188点、提出者の正解率は約54%と低めの結果に。文字列は先頭から見ていくのではなく、後ろからみた方が高速化できますね。解の候補が複数あるときに、xをできるだけ長くというのですから、後ろから見れば、最初にna==nbとなった時点で、そのほかの解を検討する必要がなくなりますので。