Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-05-01SRM336,SRM337,SRM338 (Practice)

SRM 336 ServiceNames

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

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

  • ん?問題の意図するところがわからない・・・
    • サンプルから察するにやるだけっぽい
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class ServiceNames {

	class Ret implements Comparable<Ret> {
		String service;
		List<String> items;
		Set<String> done;
		Ret(String a) {
			service = a;
			items = new ArrayList<String>();
			done = new HashSet<String>();
		}
		
		public void add(String item) {
			if (done.contains(item)) {
				return;
			}
			done.add(item);
			items.add(item);
			Collections.sort(items);
		}

		public int compareTo(Ret arg0) {
			return service.compareTo(arg0.service);
		}
		
		public String toString() {
			StringBuffer b = new StringBuffer(service);
			b.append(" ==> " + items.get(0));
			for (int j = 1 ; j < items.size() ; j++) {
				b.append(", ").append(items.get(j));
			}
			return b.toString();
		}
	}
	
	public String[] makeList(String[] services) {
		int len = services.length;
		List<Ret> list = new ArrayList<Ret>();
		Map<String, Ret> servmap = new HashMap<String, Ret>();
		for (int i = 0 ; i < len ; i++) {
			String[] x = services[i].split(" ");
			String item = x[0];
			for (int j = 1 ; j < x.length ; j++) {
				String serv = x[j];
				if (!servmap.containsKey(serv)) {
					servmap.put(serv, new Ret(serv));
					list.add(servmap.get(serv));
				}
				servmap.get(serv).add(item);
			}
		}
		
		Collections.sort(list);
		
		String[] r = new String[list.size()];
		for (int i = 0 ; i < list.size() ; i++) {
			r[i] = list.get(i).toString();
		}
		return r;
	}
}

SRM 337 CardStraights

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

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

  • し、しまった・・・(無能)
    • ジョーカーが余るパターンで、左に配置するパターンを考慮してなかった
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CardStraights {

	public int longestStraight(int[] cards) {
		Arrays.sort(cards);
		
		int len = cards.length;
		int js = 0;
		List<Integer> normals = new ArrayList<Integer>();
		for (int i  = 0 ; i < len ; i++) {
			if (cards[i] == 0) {
				js++;
			} else {
				if (!normals.contains(cards[i])) {
					normals.add(cards[i]);
				}
			}
		}
		
		int cl = normals.size();
		
		int max = js;
		for (int i = 0 ; i < cl ; i++) {
			int left = js;
			int cont = 1;
			int from = normals.get(i);
			for (int j = i ; j < cl - 1 ; j++) {
				int x = normals.get(j+1) - normals.get(j) - 1;
				if (x <= left) {
					left -= x;
					cont += x + 1; 
				} else {
					cont += left;
					left = 0;
					break;
				}
			}
			
			if (i == 0 && from >= 2) {
				cont += Math.min(from - 1, left);
				left -= Math.min(from - 1, left);
			} else if (i >= 1 && left >= 1) {
				int d = normals.get(i) - normals.get(i-1) - 1;
				cont += Math.min(d, left);
				left -= Math.min(d, left);
			}
			if (left >= 1) {
				int yetanother = 1000000 - normals.get(cl-1);
				cont += Math.min(yetanother, left);
			}
			max = Math.max(max, cont);
		}
		return max;
	}
}

SRM 338 ImprovingStatistics

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

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

  • 二分探索するだけ
public class ImprovingStatistics {

	public int calcRate(long p, long w) {
		return (int)(w * 100 / p);
	}
	
	public long INF = 2000000000;
	
	public int howManyGames(int played, int won) {
		long pl = played;
		long wl = won;
		int rate = calcRate(pl, wl);
		int obj = rate + 1;
		
		if (calcRate(pl + INF, wl + INF) < obj) {
			return -1;
		}
		
		long max = INF;
		long min = 0;
		for (int c = 0 ; c < 100 ; c++) {
			long mid = (max + min) / 2;
			if (calcRate(pl + mid, wl + mid) >= obj) {
				max = mid;
			} else {
				min = mid;
			}
		}
		return (int)max;
	}
}

2012-04-30SRM339 (Practice)

SRM 339 BusTrip

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

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

  • 問題文のとおりにシミュレーションするだけ。
import java.util.Arrays;

public class BusTrip {
	class Bus {
		int total;
		int id;
		int[] begins;
		int[] next;
		Bus(String input, int i) {
			String[] strs = input.split(" ");
			begins = new int[101];
			next = new int[101];
			Arrays.fill(begins, -1);
			Arrays.fill(next, -1);
			int len = strs.length;
			
			total = 0;

			// total distance
			int prev =  Integer.valueOf(strs[0]);
			for (int j = 0 ; j < len ; j++) {
				int dg = Integer.valueOf(strs[j]);
				int diff = Math.abs(prev - dg);
				total += diff;
				begins[dg] = total;
				prev = dg;
			}
			total += Math.abs(prev - Integer.valueOf(strs[0]));

			// next
			for (int j = 0 ; j < len - 1 ; j++) {
				int from = Integer.valueOf(strs[j]);
				int to = Integer.valueOf(strs[j+1]);
				next[from] = to;
			}
			next[Integer.valueOf(strs[len-1])] = Integer.valueOf(strs[0]);
			
			id = i;
		}
	}

	public int returnTime(int N, String[] buses) {
		int bl = buses.length;
		Bus[] b = new Bus[bl];
		for (int i = 0 ; i < bl ; i++) {
			b[i] = new Bus(buses[i], i);
		}
		
		int time = -1;
		int now = 0;
		while (time <= 1000) {
			int bestbus = -1;
			int besttime = 100000;
			for (int i = 0 ; i < bl ; i++) {
				if (b[i].begins[now] == -1) {
					continue;
				}
				for (int c = 0 ; c < 1000 ; c++) {
					int cometime = b[i].begins[now] + b[i].total * c;
					if (cometime > time) {
						if (besttime > cometime) {
							besttime = cometime;
							bestbus = i;
						}
						break;
					}
				}
			}
			if (bestbus == -1) {
				System.out.println("err");
			}
			
			int go = b[bestbus].next[now];
			time = besttime + Math.abs(go - now);
			now = go;
			if (now == 0) {
				break;
			}
		}
		return (time >= 1001) ? -1 : time;
	}
}

2012-04-24SRM340, SRM341, SRM342 (Practice)

SRM 340 ProblemsToSolve

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

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

  • 動的計画法
    • 座標圧縮して [現在位置][最大][最小] でDPする
import java.util.Arrays;

public class ProblemsToSolve {
	public int minNumber(int[] pn, int variety) {
		int len = pn.length;
		int[] pmap = new int[1001];
		int[] idxscore = new int[1001];
		Arrays.fill(pmap, -1);
		int pidx = 0;
		for (int x : pn) {
			if (pmap[x] == -1) {
				pmap[x] = pidx;
				idxscore[pidx] = x;
				pidx++;
			}
		}
		
		int[][][] dp = new int[len][pidx][pidx];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < pidx ; j++) {
				Arrays.fill(dp[i][j], 10000);
			}
		}
		dp[0][pmap[pn[0]]][pmap[pn[0]]] = 1;
		
		int min = len;
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < pidx ; j++) {
				for (int k = 0 ; k < pidx ; k++) {
					if (dp[i][j][k] >= 10000) {
						continue;
					}
					for (int go = i + 1 ; go <= i + 2 ; go++) {
						if (go >= len) {
							continue;
						}
						
						int solve = dp[i][j][k] + 1;
						int wmin = Math.min(idxscore[j], pn[go]);
						int wmax = Math.max(idxscore[k], pn[go]);
						if (wmax - wmin >= variety) {
							min = Math.min(min, solve);
						}
						int tj = pmap[wmin];
						int tk = pmap[wmax];
						if (dp[go][tj][tk] > solve) {
							dp[go][tj][tk] = solve;
						}
					}
				}
			}
		}
		return min;
	}
}

SRM 341 KLastNonZeroDigits

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

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

  • やるだけ。
public class KLastNonZeroDigits {
	public String getKDigits(int N, int K) {
		long x = 1;
		for (long a = N ; a >= 1 ; a--) {
			x *= a;
			while (x % 10 == 0 && x >= 1) {
				x /= 10;
			}
		}
		
		String str = String.valueOf(x);
		if (str.length() <= K) {
			return str;
		}
		return str.substring(str.length() - K, str.length());
	}
}

SRM 342 TagalogDictionary

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

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

  • やるだけ。
    • Comparatorの中に変数を仕込む方法が分からなかったので仕方なくバブルソートでやった
import java.util.Arrays;
import java.util.Comparator;

public class TagalogDictionary {

	int[] ord;
	int ngord;
	
	public int compare(String arg0, String arg1) {
		if (arg0.equals(arg1)) {
			return 0;
		}
		int al = arg0.length();
		int bl = arg1.length();
		int aidx = 0;
		int bidx = 0;
		while (aidx < al && bidx < bl) {
			char a = arg0.charAt(aidx);
			char b = arg1.charAt(bidx);
			int aval = ord[a];
			int bval = ord[b];
			aidx++;
			bidx++;
			if (a == 'n' && aidx < al) {
				if (arg0.charAt(aidx) == 'g') {
					aval = ngord;
					aidx++;
				}
			}
			if (b == 'n' && bidx < bl) {
				if (arg1.charAt(bidx) == 'g') {
					bval = ngord;
					bidx++;
				}
			}
			if (aval < bval) {
				return -1;
			} else if (aval > bval) {
				return 1;
			}
		}
		if (aidx >= al) {
			return -1;
		}
		return 1;
	}
	
	public String[] sortWords(String[] words) {
		String order = "a b k d e g h i l m n ng o p r s t u w y";
		
		
		String[] cp = order.split(" ");
		int cl = cp.length;
		ord = new int[512];
		ngord = 0;
		for (int i = 0 ; i < cl ; i++) {
			if (cp[i].length() == 1) {
				ord[cp[i].charAt(0)] = i;
			} else {
				ngord = i;
			}
		}
		
		int len = words.length;
		for (int y = 0 ; y < len ; y++) {
			for (int x = 0 ; x < len - 1 ; x++) {
				int i = x;
				int j = x + 1;
				String a = words[i];
				String b = words[j];
				int comp = compare(a, b);
				if (comp > 0) {
					String t = words[i];
					words[i] = words[j];
					words[j] = t;
				}
			}
		}
		
		return words;
	}
}

2012-04-21SRM343, SRM344 (Practice)

SRM 343 CDPlayer

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

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

  • 実装するだけ。
public class CDPlayer {

	public int isRandom(String[] songlist, int n) {
		String list = "";
		for (String s : songlist) {
			list += s;
		}
		int len = list.length();
		
		for (int i = 0 ; i < n ; i++) {
			boolean isok = true;
			int[] pcnts = new int[512];
			for (int p = 0 ; p < i ; p++) {
				if (++pcnts[list.charAt(p)] >= 2) {
					isok = false;
					break;
				}
			}
			if (!isok) {
				continue;
			}
			
			int idx = i;
			while (idx < len && isok) {
				int[] cnts = new int[512];
				for (int j = idx ; j < Math.min(len, idx + n) ; j++) {
					if (++cnts[list.charAt(j)] >= 2) {
						isok = false;
						break;
					}
				}
				idx += n;
			}
			if (isok) {
				return i;
			}
		}
		return -1;
	}
}

SRM 344 VolleyballTournament

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

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

  • 0点、1点、2点を取った試合数を全探索する。
    • 組み合わせが複数あれば AMBIGUITY を返す
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class VolleyballTournament {

	static final String AMB = "AMBIGUITY";
	
	public String reconstructResults(int wm, int lm, int ws, int ls) {
		ws -= wm * 3;
		ls -= lm * 3;
		int[] mat = {wm, lm};
		int[] set = {ls, ws};
		List<String> rs = new ArrayList<String>();
		for (int x = 0 ; x <= 1 ; x++) {
			int match = mat[x];
			int sets = set[x];
			int[] zot = new int[3];
			
			int rec = 0;
			for (int zero = 0 ; zero <= match ; zero++) {
				for (int one = 0 ; one <= match ; one++) {
					for (int two = 0 ; two <= match ; two++) {
						if (zero + one + two != match) {
							continue;
						}
						if (zero * 0 + one * 1 + two * 2 == sets) {
							rec++;
							zot = new int[]{zero, one, two};
						}
					}
				}
			}
			if (rec >= 2) {
				return AMB;
			}
			
			if (x == 0) {
				for (int z = 0 ; z <= 2 ; z++) {
					for (int d = 0 ; d < zot[z] ; d++) {
						rs.add("3-" + z);
					}
				}
			} else {
				for (int z = 0 ; z <= 2 ; z++) {
					for (int d = 0 ; d < zot[z] ; d++) {
						rs.add(z + "-3");
					}
				}				
			}
		}
		
		Collections.sort(rs);
		String ret = "";
		for (String s : rs) {
			ret += s + ",";
		}
		return ret.substring(0, ret.length() - 1);
	}
}

2012-04-20SRM345 (Practice)

SRM 345 Pathfinding

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

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

  • 探索で解こうと思った
    • 無理だった
  • 結局場合分けした。
    • xとyは対称性を持つので片方が負の場合だけを考えれば良い
  • 解法の検討に色々迷走したので時間がかかってしまった。
public class Pathfinding {
	public int getDirections(int x, int y) {
		int dx = Math.abs(x);
		int dy = Math.abs(y);
		
		if (x >= 0 && y >= 0) {
			if (dx % 2 == 1 && dy % 2 == 1) {
				return dx + dy + 2;
			}
			return dx + dy;
		} else if (x <= 0 && y <= 0) {
			if (dx % 2 == 0 && dy % 2 == 0) {
				return dx + dy + 4;
			}
			return dx + dy + 2;
		}
		
		if (x > 0) {
			int t = x;
			x = y;
			y = t;
		}
		
		dx = Math.abs(x);
		dy = Math.abs(y);
		if (dx % 2 == 1 && dy % 2 == 0) {
			return dx + dy + 2;
		}
		return dx + dy;
	}
}