Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-02-22SRM393 (Practice)

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