TopCoder SRM239 Div2 300Pts

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

家族でバーベキューをし、肉は皆に1切れずつということになっていた。肉を食べる前にサッカーをしてバーベキューをする場所に戻ってきたところ、犬が肉を1切れ食べてしまっていた。そこで、長兄は投票をして、1人犬を散歩に連れて遊ばせることにし、その他の人は肉を食べるということにした。家族はn人で0からn-1の添え字で一人一人を表す。voter[]は投票者を表す配列であり、値は家族のメンバーを表す0からn-1の数字が入っている。excluded[]はバーベキューから追い出したい人を表す。こちらも家族のメンバーを表す0からn-1の数字が入っている。

バーベキューからの追い出すルールは、次のルールに従う。

1. 最多得票者が追い出される
   
2. 最多得票者数が複数いたら、最多得票者の中で最も多く投票した人が追い出される
   
3. 最多投票者が複数いたら、添え字の小さい方が追い出される
   

このとき、追い出される人を表す添え字を返すメソッドを作成せよ。

私の解答はこちら。

import java.util.*;
import java.lang.*;

public class Barbecue {
 public int eliminate(int n, int[] voter, int[] excluded) {
  int[] nVote = new int[n];
  int[] nVoted = new int[n];
  for( int i=0 ; i<voter.length ; i++ ){
   nVote[voter[i]]++;
   nVoted[excluded[i]]++;
  }
  int maxVoted = maxArray(nVoted);
  //int maxVoter = maxArray(nVote);
  ArrayList<Integer> maxVotedList = new ArrayList();
  ArrayList<Integer> maxVoterList = new ArrayList();
  for( int i=0 ; i<n ; i++ ){
   if( nVoted[i] == maxVoted ){
    maxVotedList.add(i);
   }
  }
  System.out.println("-------");
  for( int i=0 ; i<n ; i++ ){
   System.out.println(nVote[i]);
  }

  // 最多得票者
  if( maxVotedList.size() == 1) return maxVotedList.get(0);
  // 得票最多数がタイだった場合
  // 該当者の中で投票数が最多だった人が選ばれる
  // それでも同じなら先に出てきた人。
  Collections.sort(maxVotedList); // ソートしておく
  //ArrayList<Integer> maxVoterVotedList = new ArrayList();
  int[] candidate = new int[maxVotedList.size()];
  int idx = 0;
  for( Integer i : maxVotedList ){ // 得票を得た人を対象に出現回数を集計
   candidate[idx] = nVote[i.intValue()];
   idx++;
  }
  int maxVoter = maxArray(candidate); // 最多得票数
  boolean flg = false;
  int res = 0;
  for( int i=0 ; i<candidate.length ; i++ ){
   if( candidate[i] == maxVoter ){
    maxVoterList.add(i); // 一番投票した人一覧作成
    if( flg == false ){
     flg = true;
     res = maxVotedList.get(i);
    }
   }
  }
  return res;
 }
 private int maxArray(int a[]){
  int max = -1;
  for( int i=0 ; i<a.length ; i++ ){
   max = Math.max(max,a[i]);
  }
  return max;
 }
}

得点は90/300。結局2時間かけて解きました。正解率は私の予想よりも高く、約72%もあるようです。