Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-05-21SRM300台を練習していく part3

SRM 308 HuffmanDecoding

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

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

ハフマン符号化の逆をやる。200とだけあって簡単。


public class HuffmanDecoding {
	public String decode(String archive, String[] dictionary) {
		String result = "";
		int idx = 0;
		while (idx < archive.length()) {
			for (int i = 0 ; i < dictionary.length ; i++) {
				int len = dictionary[i].length();
				if (idx+len <= archive.length()) {
					if (archive.substring(idx, idx+len).equals(dictionary[i])) {
						result += (char)('A' + i);
						idx += len;
						break;
					}
				}
			}
		}
		return result;
	}
}



SRM 307 PartSorting

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

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

swap可能な範囲で大きな数を前に持ってこようと試みる。


public class PartSorting {

	public int[] process(int[] data, int nSwaps) {
		int len = data.length;
		for (int x = 0 ; x < len ; x++) {
			int max = data[x];
			int maxidx = x;
			for (int i = x + 1 ; i < len ; i++) {
				if (max < data[i] && i - x <= nSwaps) {
					max = data[i];
					maxidx = i;
				}
			}
			nSwaps -= maxidx - x;
			for (int j = maxidx ; j >= x + 1 ; j--) {
				int tmp = data[j];
				data[j] = data[j-1];
				data[j-1] = tmp;
			}
		}
		return data;
	}
}




SRM 308 CornersGame

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

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

意外なことに全探索(BFS)でいけた。キューを使う。

はじめは左と上へ動かす場合のみを考慮し、ゴールできないようなら右と下も解禁する。


import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class CornersGame {
	public static final int X = 6;
	public static final int Y = 6;
	public int[][] _board;
	public Map<Long, Integer> _memo;

	public class State {
		int[][] data;
		int moves;
		int jumps;

		public long tolong() {
			long t[] = new long[4];
			for (int d = 0 ; d < 4 ; d++) {
				t[d] = data[d][0] * 6 + data[d][1];
			}
			java.util.Arrays.sort(t);
			long res = 0;
			for (int d = 0 ; d < 4 ; d++) {
				res *= 36;
				res += t[d];
			}
			return res;
		}
		public boolean check() {
			boolean[][] map = new boolean[6][6];
			int okcnt = 0;
			for (int d = 0 ; d < 4 ; d++) {
				int x = data[d][0];
				int y = data[d][1];
				if (!map[x][y] && x <= 1 && y <= 1) {
					map[x][y] = true;
					okcnt++;
				}
			}
			return (okcnt == 4);
		}

		public State(int[][] d, int mv, int j) {
			data = new int[4][2];
			int ct = 0;
			for (int da = 0 ; da < 4 ; da++) {
				for (int xy = 0 ; xy < 2 ; xy++) {
					data[da][xy] = d[da][xy];
					ct += d[da][xy];
				}
			}

			moves = mv;
			jumps = j;
		}
	}


	public int countMoves(String[] board) {
		_board = new int[Y][X];
		_memo = new HashMap<Long, Integer>();
		for (int i = 0 ; i < Y ; i++) {
			for (int j = 0 ; j < X ; j++) {
				char x = board[i].charAt(j);
				if (x == 's') {
					_board[i][j] = 1;
				} else if (x== 'r') {
					_board[i][j] = 2;
				}
			}
		}


		for (int maxd = 2 ; maxd <= 4 ; maxd += 2) {
			_memo.clear();
			int[][] st = new int[4][2];
			st[0][0] = 5; st[0][1] = 5;
			st[1][0] = 5; st[1][1] = 4;
			st[2][0] = 4; st[2][1] = 5;
			st[3][0] = 4; st[3][1] = 4;

			int[] dx = {-1, 0, 1, 0};
			int[] dy = {0, -1, 0, 1};
			Queue<State> q = new PriorityQueue<State>(1000000, new Comparator<State>(){
				public int compare(State a, State b) {
					return a.moves - b.moves;
				}
			});
			q.add(new State(st, 0, 0));

			while (q.size() >= 1) {
				State state = q.poll();
				long ln = state.tolong();
				if (_memo.containsKey(ln)) {
					continue;
				}
				_memo.put(ln, state.moves);

				int[][] dr = state.data;
				int nmv = state.moves + 1;

				for (int i = 0 ; i < 4 ; i++) {
					int bx = dr[i][0];
					int by = dr[i][1];

					// up,left
					for (int d = 0 ; d < maxd ; d++) {
						int nbx = bx + dx[d];
						int nby = by + dy[d];
						if (nbx <= -1 || nby <= -1 || nbx >= 6 || nby >= 6) continue;
						if (_board[nby][nbx] == 0) {
							boolean isok = true;
							for (int j = 0 ; j < 4 ; j++) {
								if (dr[j][0] == nbx && dr[j][1] == nby) {
									isok = false;
									break;
								}
							}
							if (isok) {
								dr[i][0] += dx[d];
								dr[i][1] += dy[d];
								State nst = new State(dr, nmv, state.jumps);
								if (nst.check()) {
									return nst.moves;
								}
								q.add(nst);
								dr[i][0] -= dx[d];
								dr[i][1] -= dy[d];
							}
						}
					}

					// jump
					for (int d = 0 ; d < maxd ; d++) {
						int nbx = bx + dx[d] * 2;
						int nby = by + dy[d] * 2;
						if (nbx <= -1 || nby <= -1 || nbx >= 6 || nby >= 6) continue;
						if (_board[nby][nbx] == 2) continue;
						boolean isok = false;
						if (_board[by+dy[d]][bx+dx[d]] == 1) isok = true;
						if (_board[nby][nbx] == 0) {
							for (int j = 0 ; j < 4 ; j++) {
								if (dr[j][0] == nbx && dr[j][1] == nby) {
									isok = false;
									break;
								}
								if (dr[j][0] == bx+dx[d] && dr[j][1] == by+dy[d]) {
									isok = true;
								}
							}
							if (isok) {
								dr[i][0] += dx[d] * 2;
								dr[i][1] += dy[d] * 2;
								State nst = new State(dr, nmv, state.jumps + 1);
								if (nst.check()) {
									return nst.moves;
								}
								q.add(nst);
								dr[i][0] -= dx[d] * 2;
								dr[i][1] -= dy[d] * 2;
							}
						}
					}
				}
			}
		}
		return -1;
	}
}