Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-02-22SRM393 (Practice)

500が簡単なセット。

293/581位

問題結果ポイントその他
250InstantRunoffVotingAccepted206.59やるだけ
500NSegmentDisplayOpened0.00各segmentごとに独立で考える
1000AirlineInternetOpened0.00 -

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;
	}
}


SRM 393 NSegmentDisplay

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

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


コーディングフェーズ

  • 英語読めなくて眠くて寝落ち

その後

  • 英語を読む
    • これは各segmentごとに独立で処理できるのでは?
  • 方針を検討
    • patternsの配列で '1' になっている箇所は確実に壊れていない
    • その他の箇所について
      • '動いている' と仮定して問題なければ '?'
      • 問題あれば 'N' にすればよい
  • 実装
    • 特に問題なくサクサク
  • サンプル合わない。
    • pattern[] で distinctだっけ?
      • 特にそのようなことは書いてない
    • ロジックを修正。
  • 提出

public class NSegmentDisplay {

	
	public boolean isok(String[] input, String[] output, boolean[] ok) {
		int len = input[0].length();
		int il = input.length;
		int ol = output.length;
		int cnt = 0;
		
		boolean[] outcovered = new boolean[ol];
		for (int i = 0 ; i < il ; i++) {
			for (int o = 0 ; o < ol ; o++) {
				boolean chk = true;
				for (int x = 0 ; x < len ; x++) {
					char expected = input[i].charAt(x);
					if (!ok[x]) {
						expected = '0';
					}
					if (output[o].charAt(x) != expected) {
						chk = false;
						break;
					}
				}
				if (chk) {
					if (!outcovered[o]) {
						outcovered[o] = true;
						cnt++;
					}
				}
			}
		}
		return (cnt == ol);
	}
	public String brokenSegments(String[] symbols, String[] patterns) {
		int len = patterns[0].length();
		int sl = symbols.length;
		int pl = patterns.length;
		boolean[] ok = new boolean[len];
		for (int i = 0 ; i < pl ; i++) {
			for (int x = 0 ; x < len ; x++) {
				if (patterns[i].charAt(x) == '1') {
					ok[x] = true;
				}
			}
		}
		
		
		if (!isok(symbols, patterns, ok)) {
			return "INCONSISTENT";
		}
		
		String ans = "";
		for (int x = 0 ; x < len ; x++) {
			if (ok[x]) {
				ans += 'Y';
			} else {
				ok[x] = true;
				if (isok(symbols, patterns, ok)) {
					ans += '?';
				} else {
					ans += 'N';
				}
				ok[x] = false;
			}
		}
		return ans;
	}
}