Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-24SRM364 (Practice)

SRM 364 PowerPlants

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

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

  • 2^16の状態を持ちながらダイクストラするだけ。
  • numPlants以上のplantsが生きてればいい(丁度でなくてもいい)ので注意
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class PowerPlants {

	int INF = 10000000;
	
	class State {
		int stat;
		int cost;
		State(int s, int c) {
			stat = s;
			cost = c;
		}
	}
	
	public int minCost(String[] connectionCost, String plantList, int numPlants) {
		int len = connectionCost.length;
		int[][] graph = new int[len][len];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				char c = connectionCost[i].charAt(j);
				if ('0' <= c && c <= '9') {
					graph[i][j] = c - '0';
				} else {
					graph[i][j] = 10 + c - 'A';
				}
			}
 		}
		
		int[] dp = new int[1<<len];
		Arrays.fill(dp, INF);
		
		
		int initptn = 0;
		for (int i = 0 ; i < len ; i++) {
			if (plantList.charAt(i) == 'Y') {
				initptn |= (1<<i);
			}
		}
		dp[initptn] = 0;
		
		Queue<State> q = new PriorityQueue<State>(4000000, new Comparator<State>(){
			public int compare(State arg0, State arg1) {
				return arg0.cost - arg1.cost;
			}
		});
		q.add(new State(initptn, 0));
		
		while (q.size() >= 1) {
			State s = q.poll();
			for (int i = 0 ; i < len ; i++) {
				if ((s.stat & (1<<i)) == 0) {
					int mcost = 10000;
					int mwake = -1;
					for (int j = 0 ; j < len ; j++) {
						if ((s.stat & (1<<j)) >= 1) {
							if (mcost > graph[j][i]) {
								mcost = graph[j][i];
								mwake = j;
							}
						}
					}
					if (mwake >= 0) {
						int tc = mcost + s.cost;
						int ts = s.stat | (1<<i);
						if (dp[ts] > tc) {
							dp[ts] = tc;
							q.add(new State(ts, tc));
						}
					}
				}
			}
		}
		
		int mcost = INF;
		for (int i = 0 ; i < (1<<len) ; i++) {
			if (Integer.bitCount(i) >= numPlants) {
				mcost = Math.min(mcost, dp[i]);
			}
		}
		return mcost;
	}
}

2012-03-20SRM368, SRM369 (Practice)

SRM 368 JumpingBoard

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

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

  • 方針を検討
    • ダイクストラっぽいことをすればいいよね
    • 同じ所に戻ってきたら-1で
  • いやまて、それじゃダメだ
    • ある場所に到達するのに2つ以上の経路があると詰む
  • 別の方法を考える
    • 幅優先で書いて単純にステップ数が上限(2500ぐらい)を超えたら-1でいいのでは
  • サンプル通ったので出した
    • TLEした
    • ちゃんとメモ化再帰で書かないとダメでした
  • 計算量の見積もりが甘かった・・・
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class JumpingBoard {

	class State {
		int h, w;
		int step = 0;
		State(int i, int j, int s) {
			h = i;
			w = j;
			step = s;
		}
	}
	
	int[] dx = {1, 0, -1, 0};
	int[] dy = {0, 1, 0, -1};
	int[][] done;
	int INF = 1000000;
	String[] board;
	int h, w;
	
	public int dfs(int r, int c) {
		if (r < 0 || c < 0 || c >= w || r >= h) {
			return 0;
		}
		if (done[r][c] >= 0) {
			return done[r][c];
		}
		if (board[r].charAt(c) == 'H') {
			return 0;
		}
		
		done[r][c] = INF;
		int ch = board[r].charAt(c) - '0';
		int max = 0;
		for (int d = 0 ; d < 4 ; d++) {
			int ty = r + dy[d] * ch;
			int tx = c + dx[d] * ch;
			max = Math.max(max, dfs(ty, tx) + 1);
		}
		done[r][c] = max;
		return max;
	}
	
	public int maxJumps(String[] b) {
		board = b;
		h = board.length;
		w = board[0].length();
		done = new int[h][w];
		for (int i = 0 ; i < h ; i++) {
			Arrays.fill(done[i], -1);
		}
		
		int c = dfs(0, 0);
		return (c > 1000000) ? - 1: c;
	}
}

2012-03-15SRM374 (Practice)

SRM 374 PlayerExtraction

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

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

  • ごちゃごちゃ書いてあるが、要はbfsでthreshold以上の連結エリアを探して中心座標を求めるだけらしい
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class PlayerExtraction {

	public class Result implements Comparable<Result>{
		int x, y;
		public Result(int a, int b) {
			x = a;
			y = b;
		}
		public int compareTo(Result arg0) {
			if (x == arg0.x) {
				return y - arg0.y;
			}
			return x - arg0.x;
		}
	}
	public String[] extractPlayers(String[] photo, int k, int threshold) {
		threshold = (threshold + 3) / 4;
		threshold *= 4;
		List<Result> results = new ArrayList<Result>();
		int h = photo.length;
		int w = photo[0].length();
		char[][] ch = new char[h*2+2][w*2+2];
		boolean[][] visited = new boolean[h*2+2][w*2+2];
		int[] x4 = {0, 1, 0, 1};
		int[] y4 = {0, 0, 1, 1};
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				int fi = i * 2;
				int fj = j * 2;
				char c = photo[i].charAt(j);
				for (int d = 0 ; d < 4 ; d++) {
					ch[1+fi+y4[d]][1+fj+x4[d]] = c;
				}
			}
		}
		
		h *= 2;
		w *= 2;
		int[] dx = {1, 0, -1, 0};
		int[] dy = {0, 1, 0, -1};
		char search = (char)('0' + k);
		for (int i = 1 ; i <= h ; i++) {
			for (int j = 1 ; j <= w ; j++) {
				if (ch[i][j] == search && !visited[i][j]) {
					int cnt = 0;
					Queue<Integer> q = new ArrayBlockingQueue<Integer>(100000);
					q.add(i*200+j);
					int minx = 10000;
					int maxx = -10000;
					int miny = 10000;
					int maxy = -10000;
					while (q.size() >= 1) {
						cnt++;
						int stat = q.poll();
						int nx = stat % 200;
						int ny = stat / 200;
						minx = Math.min(minx, nx);
						maxx = Math.max(maxx, nx);
						miny = Math.min(miny, ny);
						maxy = Math.max(maxy, ny);
						for (int d = 0 ; d < 4 ; d++) {
							if (!visited[ny+dy[d]][nx+dx[d]] && ch[ny+dy[d]][nx+dx[d]] == search) {
								visited[ny+dy[d]][nx+dx[d]] = true;
								q.add((ny+dy[d])*200+nx+dx[d]);
							}
						}
					}
					if (cnt >= threshold) {
						int midx = (minx + maxx) / 2;
						int midy = (miny + maxy) / 2;
						results.add(new Result(midx, midy));
					}
				}
			}
		}
		
		Collections.sort(results);
		String[] res = new String[results.size()];
		for (int i = 0 ; i < res.length ; i++) {
			res[i] = "" + results.get(i).x + " " + results.get(i).y;
		}
		return res;
	}
}

2012-03-13SRM375 (Practice)

SRM 375 DivisibleByDigits

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

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

  • 数論ゲーきたこれ
    • 割るべき数は1〜9のどれかだから、まず出現する数字のLCMを求めてしまおう
  • 方針を考える
    • 初期状態で割り切れればそれで終了
    • そうでなければ、数字を1つずつ追加していくとして・・・
      • 10^a倍すると、残り必要な数も自動的に分かるから、それが0〜(10^a-1)に収まってるかで判定すればよさそう
  • 書けた。サンプル通った。
    • 小さめの数で変なことが起こらないか確認する。
    • 大丈夫。
  • 出した
public class DivisibleByDigits {
	public long lcm(long a, long b) {
		long g = gcd(a, b);
		return a * b / g;
	}
	
	public long gcd(long a, long b) {
		return (b != 0) ? gcd(b, a%b) : a;
	}
	
	public long getContinuation(int n) {
		String l = String.valueOf(n);
		int len = l.length();
		long d = 1;
		for (int i = 0 ; i < len ; i++) {
			int z = l.charAt(i) - '0';
			if (z >= 1) {
				d = lcm(d, z);
			}
		}
		System.out.println(d);
		if (n % d == 0) {
			return n;
		}
		long ln = n;
		for (int ad = 1 ; ad <= 15 ; ad++) {
			long df = (ln * (long)Math.pow(10, ad)) % d;
			long maxadd = (long)Math.pow(10, ad) - 1;
			if (df == 0) {
				return (ln * (long)Math.pow(10, ad));
			} else if ((d - df) <= maxadd) {
				return (ln * (long)Math.pow(10, ad)) + (d - df);
			}
		}	
		return 0;
	}
}

2012-03-10SRM380,SRM381,SRM382 (Practice)

SRM 380 CompilingDecksWithJokers

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

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

  • 圧倒的数学ゲー
    • いい問題
  • カードの残り数でソート
    • 一番小さな数 a が n個あって、その次に大きな数がb個あったら・・・
    • aとbが等しくなるには何枚ジョーカーを使う必要があるかで式を立ててゴニョゴニョ
  • n=1かつa=0のときに注意する
import java.util.Arrays;

public class CompilingDecksWithJokers {

	public int maxCompleteDecks(int[] cards, int jokers) {
		int len = cards.length;
		if (len == 1) {
			return cards[0] + jokers;
		}
		
		long cnt = 0;
		Arrays.sort(cards);
		while (jokers >= 1 && (cards[0] >= 1 || cards[1] >= 1)) {
			int samecnt = 0;
			long secondcnt = Integer.MAX_VALUE;
			for (int i = 0 ; i < len ; i++) {
				if (cards[i] == cards[0]) {
					samecnt++;
				}
			}
			if (samecnt < len) {
				secondcnt = cards[samecnt];
			}
			long willdo = Math.min(Math.min(secondcnt, jokers), (0L + secondcnt - cards[0]) * samecnt);
			if (samecnt >= 2) {
				willdo = Math.min(willdo, 1L * cards[0] * samecnt / (samecnt - 1));
			}
			long dec = 0, mod = 0;
			dec = willdo - willdo / samecnt;
			mod = willdo % samecnt;
			for (int i = 0 ; i < len ; i++) {
				if (i < samecnt) {
					cards[i] -= ((i < mod) ? (dec - 1) : dec);
				} else {
					cards[i] -= willdo;
				}
			}
			jokers -= willdo;
			cnt += willdo;
			Arrays.sort(cards);
		}
		Arrays.sort(cards);
		return (int) (cnt + cards[0]);
	}
}