TopCoder SRM371 Div2 250Pts

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

選挙における試みの1つに、候補者を順位づけするということがある。候補者Aが候補者Bより「好ましい候補者」であるというのは、AがBより高い順位をつけた人が、その逆より多いということを指す。コンドルセ勝者というのは、他のすべての候補者よりも「好ましい候補者」である候補者のことを言う。コンドルセ勝者は選挙においては最大で一人いるが、0人になることもある。

問題ではvotes[]というi番目の要素のj番目の文字がiさんが候補者jに対して評価した結果が小文字のアルファベットで格納されている。"a"に近いほど好評価で、"z"に近いほど低評価になる。コンドルセ勝者を表す数字を、先頭を0とするインデックスで返せ。もし、コンドルセ勝者が存在しない倍は-1を返すようにせよ。

私の解答はこちら。

public class CondorcetVoting {

 public int winner(String[] votes) {
  int nCandidates = votes[0].length();
  // iがjに勝ち越せば正、負け越せば負の値がi行j列に入る。j行i列はその-1倍の値になる。
  int[][] win = new int[nCandidates][nCandidates];
  for( int i=0 ; i<votes.length ; i++ ){
   for( int j=0 ; j<nCandidates ; j++ ){
    for( int k=j+1 ; k<nCandidates ; k++ ){
     if( votes[i].charAt(j) < votes[i].charAt(k) ){
      win[j][k]++;
      win[k][j]--;
     }else if( votes[i].charAt(j) > votes[i].charAt(k) ){
      win[j][k]--;
      win[k][j]++;
     }
    }
   }
  }

  // コンドルセ勝者の探索
  for( int i=0 ; i<nCandidates ; i++ ){
   boolean isCondorcetWinnerExist = true;
   for( int j=0 ; j<nCandidates ; j++ ){
    if( i==j ) continue; // 対角成分はiさんがiさんに勝ったか?を評価するので無視
    if( win[i][j] <= 0){ // コンドルセ勝者は対角成分以外が全部正の値である
     isCondorcetWinnerExist = false; // ここに入ったら失敗
     break;
    }
   }
   if( isCondorcetWinnerExist ) return i;
  }
  return -1;
 }

}

得点は132.43/250、1回のsubmitでシステムテストクリア。2次元配列で勝ち負けを格納するという方法を思いつくのに時間がかかりました。また、最初に人を固定して候補者を比較するという順序が大事なようです。