Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-22SRM366 (Practice)

問題結果ポイントその他
250ChangingSoundsAccepted239.50DP
500GuitarConcertWA0.00全探索
1000LateForConcertWA0.00ダイクストラ法

SRM 366 ChangingSounds

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

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

  • [現在位置][音量]でDPする
    • 50 * 1000 = 50,000
  • 書いた。サンプル通った。
    • これはスピード勝負な気がするのでそのまま出した。
public class ChangingSounds {

	public int maxFinal(int[] ci, int beginLevel, int maxLevel) {
		int len = ci.length;
		boolean[][] dp = new boolean[len+1][maxLevel+1];
		dp[0][beginLevel] = true;
		for (int i = 0 ; i < len ; i++) {
			for (int l = 0 ; l <= maxLevel ; l++) {
				if (dp[i][l]) {
					int[] to = {l - ci[i], l + ci[i]};
					for (int d = 0 ; d <= 1 ; d++) {
						if (0 <= to[d] && to[d] <= maxLevel) {
							dp[i+1][to[d]] = true;
						}
					}
				}
			}
		}
		
		int max = -1;
		for (int l = 0 ; l <= maxLevel ; l++) {
			if (dp[len][l]) {
				max = Math.max(max, l);
			}
		}
		return max;
	}
}

SRM 366 GuitarConcert

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

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

  • ギターの数が少ないので、全探索するだけに見える
    • 2^10 *10 * 50 = 500,000 ぐらい
  • ゴリゴリ書く。
    • サンプル通った。
    • 特に間違ってない気がするのでそのまま出した
  • WA
    • そうか、比べる前にソートしなきゃいけないのか
    • 直したら通った。
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class GuitarConcert {
	public boolean isGreater(String[] a, String[] b) {
		int al = a.length;
		int bl = b.length;
		int m = Math.min(al, bl);
		for (int i = 0 ; i < m ; i++) {
			int comp = a[i].compareTo(b[i]);
			if (comp <= -1) {
				return false;
			} else if (comp >= 1) {
				return true;
			}
		}
		return true;
	}
	
	public String[] buyGuitars(String[] gn, String[] gs) {
		int gl = gn.length;
		int sl = gs[0].length();
		boolean[][] graph = new boolean[gl][sl];
		for (int i = 0 ; i < gl ; i++) {
			for (int j = 0 ; j < sl ; j++) {
				if (gs[i].charAt(j) == 'Y') {
					graph[i][j] = true;
				}
			}
		}
		
		boolean[][] compgraph = new boolean[1<<gl][sl];
		int bnum = -1; 
		int bgnum = 0;
		String[] best = null;
		for (int i = 1 ; i < (1<<gl) ; i++) {
			for (int g = 0 ; g < gl ; g++) {
				if ((i & (1<<g)) >= 1) {
					for (int s = 0 ; s < sl ; s++) {
						if (graph[g][s]) {
							compgraph[i][s] = true;
						}
					}
				}
			}
			int cnt = 0;
			for (int s = 0 ; s < sl ; s++) {
				cnt += (compgraph[i][s]) ? 1 : 0;
			}
			if (bnum < cnt) {
				bnum = cnt;
				bgnum = Integer.bitCount(i);
				best = new String[bgnum];
				int idx = 0;
				for (int g = 0 ; g < gl ; g++) {
					if ((i & (1<<g)) >= 1) {
						best[idx] = gn[g];
						idx++;
					}
				}
				Arrays.sort(best);
			} else if (bnum == cnt) {
				int num = Integer.bitCount(i);
				String[] newset = new String[num];
				int idx = 0;
				for (int g = 0 ; g < gl ; g++) {
					if ((i & (1<<g)) >= 1) {
						newset[idx] = gn[g];
						idx++;
					}
				}
				Arrays.sort(newset);
				if (bgnum > num) {
					bgnum = num;
					best = newset.clone();
				} else if (bgnum == num) {
					if (!isGreater(newset, best)) {
						best = newset;
					}
				}
			}
		}

		if (bnum <= 0) {
			return new String[]{};
		}
		
		Arrays.sort(best);
		
		return best;
	}
}

SRM 366 LateForConcert

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

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

  • [現在位置][直前の方向][時間]でダイクストラするだけかな?
    • 50 * 50 * 4 * 100 = 1,000,000
  • 書いた。サンプル通った。
    • 見なおしして出した
  • WA
    • あれ?
      • しばらく原因が分からず・・・
    • 問題を読みなおす。
    • Determine the route that will take you to the concert hall in exactly timeLeft seconds.
      • と書いてある。
    • timeLeftだからtimeLeft以内に着けばいいのかと思ってた
    • ゴールとして採用する状態をtimeLeftぴったりのみに直したら通った。
e a, State b