TopCoder SRM263 Div2 250Pts

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

あなたは、全員が互いの名前を知らないパーティーに出席している。二人が握手するたびに、二人は互いを紹介試合、パーティでこれまでに知った人たちの名前を共有し合う。nというパーティの出席者数と、personA[]、personB[]という人々を表す数字が0から始まる配列が与えられる。この配列は誰が握手しあったのかということを時系列的に表している(つまり先頭から後方に向かって後のことを表すようになっている)。personAとpersonBの添え字が同じものが1つの握手を表している。パーティで知った人数の平均値を返せ。ただし、自分の名前はそれに含めないものとする。また、personA[i]とpersonB[i]は0からn-1の値を取り、かつ1つの添え字に着目したとき、同じ値は入らない。

私の解答はこちら。

public class Party {

 public double averageNames(int n, int[] personA, int[] personB) {
  // i行j列の要素はiという人がjという人を知っているか否かを表す
  boolean[][] known = new boolean[n][n]; // falseで初期化される。falseは知らないを意味する。
  for( int i=0 ; i<personA.length ; i++ ){
   int A = personA[i];
   int B = personB[i];
   known[A][B] = true; // 互いを紹介
   known[B][A] = true;
   for( int j=0 ; j<n ; j++ ){ // これまでに知った人を互いに共有
    // known[B][B]は常にfalseなのでj!=Bが必要
    if( known[A][j] && j!=B ){ // AがBに教える
     known[B][j] = true;
    }
    if( known[B][j] && j!=A ){ // BがAに教える
     known[A][j] = true;
    }
   }
  }
  int cnt = 0; // 知っている人数を合計
  for( int i=0 ; i<n ; i++ ){
   for( int j=0 ; j<n ; j++ ){
    if( known[i][j] ) cnt++;
   }
  }
  return (double)cnt/n; // 知っている人数の平均はnで割って求まる
 }

}

得点は75/250。相手を知っているというデータ構造を考え付くのに、2次元配列という発想が出なかったため、何週間か考えて解答。