Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-15SRM374 (Practice)

mediumが後で読むと簡単な問題であることがわかりすごく悔しい 417/551位

問題結果ポイントその他
250SyllableSortingAccepted175.97強実装
500PlayerExtractionOpened0.00問題文が読めなかったのでhardに逃げた
1000CommercialPlannerWA0.00hardに逃げた結果がこれだよ!

SRM 374 SyllableSorting

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

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

  • 問題文の通りに実装する。
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class SyllableSorting {

	public class S implements Comparable<S> {
		List<String> slist;
		List<String> ulist;
		String base;
		S (List<String> l, String b) {
			ulist = new ArrayList<String>();
			slist = new ArrayList<String>();
			for (String a : l) {
				ulist.add(a);
				slist.add(a);
			}
			Collections.sort(slist, new Comparator<String>(){
				public int compare(String a, String b) {
					int al = a.length();
					int bl = b.length();
					for (int i = 0 ; i < Math.min(al, bl) ; i++) {
						if (a.charAt(i) < b.charAt(i)) {
							return -1;
						} else if (a.charAt(i) > b.charAt(i)) {
							return 1;
						}
					}
					return al - bl;
				}
			});
			base = b;
		}
		public int compareTo(S anothers) {
			int cmpsorted = compareList(slist, anothers.slist);
			if (cmpsorted == 0) {
				return compareList(ulist, anothers.ulist);
			}
			return cmpsorted;
		}
		
		public int compareList(List<String> arg0, List<String> arg1) {
			int min = Math.min(arg0.size(), arg1.size());
			for (int i = 0 ; i < min ; i++) {
				String a = arg0.get(i);
				String b = arg1.get(i);
				int c = comp(a, b);
				if (c != 0) {
					return c;
				}
			}
			return arg0.size() - arg1.size();
		}
	}
	
	
	public boolean[] v;
	
	public int comp(String a, String b) {
		int al = a.length();
		int bl = b.length();
		for (int i = 0 ; i < Math.min(al, bl) ; i++) {
			if (a.charAt(i) < b.charAt(i)) {
				return -1;
			} else if (a.charAt(i) > b.charAt(i)) {
				return 1;
			}
		}
		return al - bl;
	}
	
	public List<String> syllablize(String w) {
		List<String> sy = new ArrayList<String>();
		int l = w.length();
		int from = 0;
		boolean isv = false; 
		for (int i = 0 ; i < l ; i++) {
			if (!v[w.charAt(i)]) {
				if (isv) {
					sy.add(w.substring(from, i));
					from = i;
					isv = false;
				}
			} else {
				isv = true;
			}
		}
		sy.add(w.substring(from));
		return sy;
	}
	
	
	public String[] sortWords(String[] words) {
		v = new boolean[512];
		v['a'] = v['e'] = v['i'] = v['o'] = v['u'] = true;
		List<S> sylist = new ArrayList<S>();
		for (String w : words) {
			sylist.add(new S(syllablize(w), w));
		}
		Collections.sort(sylist);
		String[] ns = new String[words.length];
		for (int i = 0 ; i < words.length ; i++) {
			ns[i] = sylist.get(i).base;
		}
		return ns;
	}

}


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;
	}
}

SRM 374 CommercialPlanner

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

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

  • 単純に他のコマーシャルの直後を調べてけばいいんじゃないかと思ったが、0秒目を考慮するのを忘れてた
  • あとで解く