TopCoder SRM427 Div2 250Pts

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

女の子が好きな男の子の一人とデートしたいと思っているが、誰を選んでいいか分かっていない。幸いにして、女の子はLove Calculatorという、二人が愛し合っている確率を計算できるものを持っている。Love Calculatorは二人の名前を受け取り、以下のアルゴリズムに沿って、愛し合っている確率を計算する。

• Lは二人の名前に登場する'L'の出現回数
• Oは二人の名前に登場する'O'の出現回数
• Vは二人の名前に登場する'V'の出現回数
• Eは二人の名前に登場する'E'の出現回数

以上のように置いたとき、二人の愛し合っている確率は((L+O)*(L+V)*(L+E)*(O+V)*(O+E)*(V+E))%100で求めることができる。女の子の名前を表すgirlという文字列型変数と、彼女の好きな男の子の名前が含まれるboys[]という配列が与えられたとき、女の子と最も愛し合っている可能性が高い男の子の名前を返すメソッドを作成せよ。もし、複数の男の子が候補にある場合は、アルファベット順に並べたとき最初に来る名前を返すようにすること。

私の解答はこちら。

public class LoveCalculator {

 public String findBoy(String girl, String[] boys) {
  long maxprob = -1;
  int[] freq_girl = new int[4]; // LOVEという文字の出現回数を記録

  String bestBoy = "";
  for( int i=0 ; i<girl.length() ; i++ ){
   if( girl.charAt(i) == 'L' ) freq_girl[0]++;
   if( girl.charAt(i) == 'O' ) freq_girl[1]++;
   if( girl.charAt(i) == 'V' ) freq_girl[2]++;
   if( girl.charAt(i) == 'E' ) freq_girl[3]++;
  }
  for( int i=0 ; i<boys.length ; i++ ){
   int[] freq_boy = new int[4];
   for( int j=0 ; j<[i].length() ; j++){
    if( boys[i].charAt(j) == 'L' ) freq_boy[0]++;
    if( boys[i].charAt(j) == 'O' ) freq_boy[1]++;
    if( boys[i].charAt(j) == 'V' ) freq_boy[2]++;
    if( boys[i].charAt(j) == 'E' ) freq_boy[3]++;
   }
   int[] fr = new int[freq_girl.length];
   for( int j=0 ; j<.length ; j++ ){
    fr[j] = freq_girl[j] + freq_boy[j];
   }
   long prob = ((fr[0]+fr[1])*(fr[0]+fr[2])*(fr[0]+fr[3])*
                (fr[1]+fr[2])*(fr[1]+fr[3])*(fr[2]+fr[3]))%100;
   if( prob > maxprob ){
    bestBoy = boys[i];
    maxprob = prob;
   }else if( prob == maxprob ){
    if( bestBoy.compareTo(boys[i]) > 0 ){
     bestBoy = boys[i];
    }
   }
  }
  return bestBoy;
 }

}

点数は183点台でした。配列よりもハッシュの方が綺麗に書けるんでしょうかね。probを計算するときは、6つの値を順に掛ける度に100で割っておけばオーバーフローを気にしなくてもよさそうです。すべて掛け算すると、最大で40^6まで値を取り得るので、上の実装では念のためlongにしています。