2012年1月25日水曜日

TopCoder SRM320 Div2 250Pts

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

文字列はいくつかの同一の文字の最大の集まりから構成されると考えられる。"aaabbaacc"は"aaa","bb","aaa","cc"からなると言える。文字列sが与えられたとき、その文字列のセグメントの長さの平均長を返せ。先ほどの例では(3+2+3+2)/4=2.5である。

私の解答はこちら。

public class StringSegment {

 public double average(String s) {
  int nSeg = 1;
  char c = s.charAt(0);
  for( int i=0 ; i<s.length() ; i++){
   if( s.charAt(i) != c){ // これまでと違う文字なら
    nSeg++; // セグメントは1つ増える
    c = s.charAt(i);
   }
  }
  // 文字列をセグメント数で割れば、1セグメント当たりの長さが求まる
  return (double)s.length()/nSeg;
 }

}

得点は241.02/250、中央値は約233点。実は1つ1つのセグメントの長さに関する情報は不要で、いくつのセグメントがあるかをカウントすればよいというだけの話。

0 件のコメント:

コメントを投稿

フォロワー

ブログ アーカイブ

ページビューの合計