Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-03SRM389 (Practice)

149/552位。全体的に簡単な回

問題結果ポイントその他
250ApproximateDivisionAccepted220.45拍子抜け
500GuitarChordsAccepted287.96全探索
1000LittleSquaresOpened0.00Grundy数

SRM 389 ApproximateDivision

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

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

  • 方針を検討
    • 何やら数式が書いてある・・・
    • 読む。b以上の2の乗数tを使い計算せよ、と。
    • やるだけ?
  • 実装
  • サンプル通る。
    • こんなに簡単なわけがない
      • きっと何か罠があるに違いない。
    • しばらく変なケースを探す。
      • 特に見つからない。
  • 出した

public class ApproximateDivision {
	public double quotient(int a, int b, int terms) {
		double ans = 0.0d;
		
		long t = 1;
		while (t < b) {
			t *= 2;
		}
		long c = t - b;
		
		long cc = 1;
		long tt = t;
		double val = (double) cc /tt;
		for (int z = 0 ; z < terms ; z++) {	
			ans += val;
			val = (val * c) / t;
		}
		return ans * a;
	}
}




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



SRM 389 LittleSquares

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

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

  • 珍しく時間が余った(25分)ので、hardをオープン。
  • 方針を検討
    • ゲームでDPする系か
    • でかいブロックは置ける場所が予め決まっている
    • でかいブロックが置けない場合は、残りのマスの偶奇で勝敗が決まる。
    • 「でかいブロックが後いくつ置けるか」「残りマス数」でdfsできそう・・・
bool dfs(int big, int left) {
  if (big == 0) {
    return (left % 2);
  }
  dfs(big, left-1)
  dfs(big-1, left-4)
}
    • なんとなくこんな(↑)雰囲気で計算できそう
    • 問題は、でかいブロックの置き方によって、残り置けるでかいブロックの数が変わってくるところだ
      • 例えば、
□□□□
□□□□
      • このようなマスでは、でかいブロックはあと2個置けるが
□■■□
□■■□
      • でかいブロックを真ん中に配置するとこれ以上置けなくなる。
    • この状態をどう処理するかがミソな気がする・・・
      • うーん
  • 方針立たずに時間切れ。

その後

  • 解説を読む。
    • どうやら盤面を Nx2 マスずつに区切って、Grundy数というのを求めるといいらしい
    • Grundy数については要学習。蟻本に載ってた気がするので理解を深める。