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ぴったりのみに直したら通った。
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class LateForConcert {
	int[] dx = {1, 0, 0, -1};
	int[] dy = {0, 1, -1, 0};
	class State {
		int nx;
		int ny;
		int time;
		int prev;
		double fine;
		State(int x, int y, int t, int p, double f) {
			nx = x;
			ny = y;
			time = t;
			fine = f;
			prev = p;
		}
	}
	
	public double bestRoute(String[] cityMap, int timeLeft, double speedingTicket, double redLight) {
		int h = cityMap.length;
		int w = cityMap[0].length();
		
		char[] cmap = new char[512];
		cmap['Y'] = cmap['.'] = 1;
		cmap['C'] = 2;
		cmap['T'] = 3;
		cmap['S'] = 4;
		
		
		int sx = 0;
		int sy = 0;
		int cx = 0;
		int cy = 0;
		int[][] map = new int[h+2][w+2];
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				map[i+1][j+1] = cmap[cityMap[i].charAt(j)];
				if (cityMap[i].charAt(j) == 'Y') {
					sx = j+1;
					sy = i+1;
				}
				if (cityMap[i].charAt(j) == 'C') {
					cx = j+1;
					cy = i+1;
				}
			}
		}
		
		Queue<State> q = new PriorityQueue<State>(1000000, new Comparator<State>(){
			public int compare(State a, State b) {
				return Double.compare(a.fine, b.fine);
			}
		});
		q.add(new State(sx, sy, 0, -1, 0.0d));
		
		
		double[][][][] dp = new double[51][51][5][151];
		for (int i = 0 ; i < 51 ; i++) {
			for (int j = 0 ; j < 51 ; j++) {
				for (int d = 0 ; d < 5; d++) {
					Arrays.fill(dp[i][j][d], Double.MAX_VALUE);
				}
			}
		}
		dp[sx][sy][4][0] = 0.0d;
		
		while (q.size() >= 1) {
			State s = q.poll();
			if (map[s.ny][s.nx] == 2) {
				continue;
			}
			for (int d = 0 ; d < 4 ; d++) {
				if (3 - d == s.prev) {
					continue;
				}
				int tx = s.nx + dx[d];
				int ty = s.ny + dy[d];
				if (map[ty][tx] != 0) {
					int tt = s.time + 1;
					double tf = s.fine;
					if (map[ty][tx] == 4) {
						tf += speedingTicket;
					}
					if (map[s.ny][s.nx] == 3) {
						if (dp[tx][ty][d][tt+1] > tf && tt+1 <= timeLeft) {
							dp[tx][ty][d][tt+1] = tf;
							q.add(new State(tx, ty, tt+1, d, tf));
						}
						tf += redLight * 0.7;
						if (dp[tx][ty][d][tt] > tf && tt <= timeLeft) {
							dp[tx][ty][d][tt] = tf;
							q.add(new State(tx, ty, tt, d, tf));
						}
					} else {
						if (dp[tx][ty][d][tt] > tf && tt <= timeLeft) {
							dp[tx][ty][d][tt] = tf;
							q.add(new State(tx, ty, tt, d, tf));
						}
					}
				}
			}
		}
		
		double minfine = Double.MAX_VALUE;
		for (int t = timeLeft ; t <= timeLeft ; t++) {
			for (int d = 0 ; d < 4 ; d++) {
				if (dp[cx][cy][d][t] < minfine) {
					minfine = dp[cx][cy][d][t];
				}
			}
		}	
		return (minfine > Double.MAX_VALUE / 10) ? -1.0d : minfine;
	}
}