TopCoder SRM436 Div2 250Pts

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

あなたはソーシャルネットワークにおいて、もっとも人気のある人を決めたいと思っている。それをするために、"2-friends"というそれぞれの人が持っている数値を数えることにした。AがBという人と2-friendであるというのは、互いに友人である、あるいはAとBの間に共通の友人Cがいる状態をいう。もっとも人気のある人というのは、2-friendsの値が最大の人物のこととする (2-friendsを最大にする人が複数いることもある)。問題ではfriends[]という文字列型配列が与えられる。i番目の文字列のj番目の要素がYであれば、i番目の人とj番目の人は友人であり、Nでなければ直接の友人ではない。ソーシャルネットワークにおいて、もっとも人気のある人の2-friendsの値を返すメソッドを作成せよ。

私の解答はこちら。

import java.util.HashSet;

public class FriendScore {

 public int highestScore(String[] friends) {
  int max = -1;
  HashSet<Integer> hs = new HashSet<Integer>();
  for( int i=0 ; i<friends.length ; i++ ){ // 各人について2-friendsを探索
   for( int j=0 ; j<friends[i].length() ; j++ ){
    if( friends[i].charAt(j) == 'Y' ){ // jはiの直接の友人か?
     hs.add(j);
     for( int k=0 ; k<friends[j].length() ; k++ ){ // iとjの共通の友人を探索
      if( k == i || k == j ) continue; // iとjは探索済(というか既に友人扱い)
      if( friends[j].charAt(k) == 'Y' ) hs.add(k);
     }
    }
   }
   max = Math.max(max, hs.size());
   hs.clear();
  }
  return max;
 }

}

得点は171.47/250、1回のsubmitでシステムテストクリア。この問題も実装より読解に時間がかかった。要は「友人」と「友人の友人」の数を探索しろと言っているのである。ああ、まぎらわしい。