Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-02-22SRM393 (Practice)

SRM 393 InstantRunoffVoting

|  SRM 393 InstantRunoffVoting - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 393 InstantRunoffVoting - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8607

  • 方針を検討
    • 毎投票ラウンドの結果は
      • 勝者が決まる
      • 少なくとも1人が脱落する
      • 引き分けになる
    • のどれかになるはずだ。
    • 制約甘いしシミュレーションするだけでは。
  • 実装
    • 過半数以上に気をつけて実装
    • サンプル通った。
  • 見直しフェーズ
    • 配列の添字チェック
    • 念のため最大ケースでテスト
  • 提出

import java.util.Arrays;

public class InstantRunoffVoting {

	public int winner(String[] voters) {
		int con = voters[0].length();
		int len = voters.length;
		boolean[] available = new boolean[con];
		for (int i = 0 ; i < con ; i++) {
			available[i] = true;
		}
		
		int morethan = len / 2 + 1;
		
		while (true) {
			int[] vote = new int[con];
			for (int i = 0 ; i < len ; i++) {
				for (int j = 0 ; j < con ; j++) {
					int idx = voters[i].charAt(j) - '0';
					if (available[idx]) {
						vote[idx]++;
						break;
					}
				}
			}
			
			int minv = 1001;
			for (int j = 0 ; j < con ; j++) {
				if (!available[j]) {
					continue;
				}
				if (vote[j] >= morethan) {
					return j;
				}
				minv = Math.min(minv, vote[j]);
			}
			
			boolean processed = false;
			for (int j = 0 ; j < con ; j++) {
				if (!available[j]) {
					continue;
				}
				if (vote[j] == minv) {
					available[j] = false;
					processed = true;
				}
			}
			if (!processed) {
				break;
			} else {
				boolean isalive = false;
				for (int j = 0 ; j < con ; j++) {
					if (available[j]) {
						isalive = true;
						break;
					}
				}
				if (!isalive) {
					break;
				}
			}
		}
		return -1;
	}
}