Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-03SRM389 (Practice)

SRM 389 GuitarChords

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

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

  • 方針を検討
    • ギターを鳴らす問題
    • 難易度の一番低い引き方をする時、その難易度を求めろ、か
    • よく見ると制約が甘い N <= 6  これは全探索しろということか
  • 実装
    • 予め、音と音に関するフレットのマップを作っておく。
    • next_permutationをして、string を chord にマッピングする
    • その対応を全部調べ、一番難易度が低いのを返す
  • サンプルが全然通らない。
    • 問題に戻る
      • そうか、stringは全部鳴らさなきゃいけないのか。
      • そして鳴らした結果chordのうちのどれかにならなければならない。
      • その上で、chordは最低でも一つのstringによって鳴らされる必要がある。
  • 実装
    • じゃあ、6^6の全パターンを調べてしまおう
    • 書き換え。
  • サンプル3だけが通らない。
    • 詳しく見る。
    • なるほど、あえて1オクターブ高い音にしたほうが簡単な場合もあるのか
      • サンプルが親切。
    • それなら、2^6パターン(高いのを鳴らすかどうか)をすべて調べてしまおう
  • サンプル通った。
    • 特殊な場合でテスト。1音しか鳴らさない場合とか
    • 問題なし。
  • 出した

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class GuitarChords {

	String[] notes = {
		"A", "A#", "B", "C", "C#", "D", "D#", "E", "F", "F#", "G", "G#",
		"A", "A#", "B", "C", "C#", "D", "D#", "E", "F", "F#", "G", "G#",
	};
	
	
	public boolean next_permutation(int[] num) {
		int len = num.length;
		int x = len - 2;
		while (x >= 0 && num[x] >= num[x+1]) {
			x--;
		}
		if (x == -1) return false;

		int y = len - 1;
		while (y > x && num[y] <= num[x]) {
			y--;
		}
		int tmp = num[x];
		num[x] = num[y];
		num[y] = tmp;
		java.util.Arrays.sort(num, x+1, len);
		return true;
	}

	
	public int stretch(String[] strings, String[] chord) {
		Map<String, Integer> map = new HashMap<String, Integer>(); 
		for (int i = 0 ; i < 12 ; i++) {
			String play = notes[i];
			for (int j = 0 ; j < 12 ; j++) {
				String sound = notes[j];
				int cnt = 0;
				for (int k = i ; k < i + 12 ; k++) {
					if (notes[k].equals(sound)) {
						break;
					}
					cnt++;
				}
				map.put(play + " " + sound, cnt);
			}
		}
		
		int sl = strings.length;
		int cl = chord.length;
		
		int mindiff = Integer.MAX_VALUE;
		int cl6 = (int)Math.pow(cl, sl);
		for (int ptn = 0 ; ptn < cl6 ; ptn++) {
			int[] match = new int[sl];
			boolean[] hit = new boolean[cl];
			int xptn = ptn;
			for (int i = 0 ; i < sl ; i++) {
				match[i] = xptn % cl;
				xptn /= cl;
				hit[match[i]] = true;
			}
			boolean isok = true;
			for (int i = 0 ; i < cl ; i++) {
				if (!hit[i]) {
					isok = false;
					break;
				}
			}
			if (!isok) {
				continue;
			}
			
			for (int fp = 0 ; fp < (1<<sl) ; fp++) {
				int mxflet = -1;
				int miflet = 100;
				for (int i = 0 ; i < sl ; i++) {
					String ws = strings[i] + " " + chord[match[i]];
					int flet = map.get(ws) + (((fp & (1<<i)) >= 1) ? 12 : 0);
					if (flet > 0) {
						mxflet = Math.max(mxflet, flet);
						miflet = Math.min(miflet, flet);
					}
				}
				if (mxflet == -1) {
					mindiff = 0;
				} else {
					mindiff = Math.min(mindiff, mxflet - miflet + 1);
				}
			}
			
		}
		return mindiff;
	}
}