TopCoder SRM380 Div2 250Pts

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

lucky ticketという数字は桁数が2*n(nは自然数)で、前半のn桁と、後半のn桁の各桁の合計が一致する。sという数字のみからなる文字列が与えられたとき、lucky ticketになる部分文字列で最長になるものを求め、その長さを返すメソッドを作成せよ。

私の解答はこちら。

public class LuckyTicketSubstring {

 public int maxLength(String s) {
  int maxlen = 0;
  for( int from=0 ; from<s.length() ; from++ ){
   for( int to=from+1 ; to<s.length() ; to++ ){
    // 切り出す範囲の文字数が奇数なら考える必要なし
    // 添え字がfromからtoまでを切り出して考えることにする
    if( (to-from)%2 == 0 ) continue;
    int half = (to+from)/2;
    String first = s.substring(from, half+1);
    String second = s.substring(half+1, to+1);
    int sum1 = 0;
    int sum2 = 0;
    for( int i=0 ; i<first.length() ; i++ ){ // 前半と後半の数字の合計を計算
     sum1 += first.charAt(i) - '0';
     sum2 += second.charAt(i) - '0';
    }
    int len = first.length()*2;
    if( len > maxlen && sum1 == sum2 ){ // 合致の条件
     maxlen = to - from + 1;
    }
   }
  }
  return maxlen;
 }

}

得点は164.82/250、1回のsubmitでシステムテストクリア。当日の正解率は約85%。Stringの生成が多いので、最初にfrom-to+1がmaxlen以下ならcontinueするという条件を付けた方がいいのかなと思いました。