2012年3月27日火曜日

TopCoder SRM350 Div2 250Pts

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

文字列のある1文字に関する距離は(n1-n2)^2で定義される。n1とn2はそれぞれ1番目と2番目の文字列の文字の出現回数(大文字と小文字を区別しない)である。これら2つの文字列に対する距離に関する3番目の文字列とは、3番目の文字列に現れた文字についてのみ2つの文字列の距離の総和をとったものである。問題ではa、b、letterSetという3つの文字列が与えられる。letterSetは各文字が異なっている。このときletterSetに登場する文字について、aとbの文字列の距離を計算してその値を返せ。

私の解答はこちら。

public class DistanceBetweenStrings {

 public int getDistance(String a, String b, String letterSet) {
  int dist = 0;
  a = a.toLowerCase(); // 大文字と小文字の区別をなくす
  b = b.toLowerCase();
  // letterSetの各文字について距離を計算する
  for( int i=0 ; i<letterSet.length() ; i++ ){
   char c = letterSet.charAt(i);
   int na = 0;
   for( int j=0 ; j<a.length() ; j++ ){
    if( a.charAt(j) == c ) na++;
   }
   int nb = 0;
   for( int j=0 ; j<b.length() ; j++ ){
    if( b.charAt(j) == c ) nb++;
   }
   dist += (na-nb)*(na-nb);
  }
  return dist;
 }

}

得点は208.34/250、中央値は約187点。全部小文字として扱えという条件を見落として2回目のsubmitでシステムテストクリア。

0 件のコメント:

コメントを投稿

フォロワー

ブログ アーカイブ

ページビューの合計