BottomCoder SRM 374 div2

SRM 374 div2

points	result	time
250	AC	4.2m
500	AC	12.5m
1000	AC	25m

hack祭り。問題文が長い割に中身がなかった・・

250

x,y(<=100)からwidth,height(<=100, height:偶数)だけ広がった長方形の(x,y+height/2), (x+width, y+height/2)それぞれを中心に、長方形の外側に向けてheight/2の半円がある。与えられた点のうち、これらの図形の境界上か内部にあるものの個数を求めよ。

前フリが壮大な割に訊きたいことはこれだけだったという。長方形、円についてそれぞれ判定すればよい。制約も小さいので、すべてintの範囲でもOK.

import java.util.Arrays;

public class HockeyFault {
	public int numPlayers(int width, int height, int x, int y, int[] px, int[] py) {
		int ct = 0;
		for(int i = 0;i < px.length;i++){
			int xx = px[i];
			int yy = py[i];
			if(xx >= x && xx <= x + width && yy >= y && yy <= y + height){
				ct++;
				continue;
			}
			if((xx - x) * (xx - x) + (yy-(y+height/2))*(yy-(y+height/2)) <= (height/2)*(height/2)){
				ct++;
				continue;
			}
			if((xx - (x+width)) * (xx - (x+width)) + (yy-(y+height/2))*(yy-(y+height/2)) <= (height/2)*(height/2)){
				ct++;
				continue;
			}
		}
		return ct;
	}

	void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

500

与えられた文字列配列(||<=50)を次の順番にソートせよ。ただし文字列は子音ではじまり母音で終わる。
文字列を、連続した(子音1個以上+母音1個以上)の配列に分割し、ソートしたもの、を比べる。
上記が等しい場合は、連続した(子音1個以上+母音1個以上)の配列のソートしていないものを比べる。

まず配列への分割は、"母音,子音"の順になっているところを見つけて順次切り出せば良い。あらかじめ文字列の末尾に子音を追加しておけば多少楽になる。
配列を切り出した後は、ソートしたものとしていないものをつくっておけば、あとは比較関数を適当にかくだけ。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class SyllableSorting {
	public String[] sortWords(String[] words) {
		int n = words.length;
		final List<List<String>> l = new ArrayList<List<String>>();
		final List<List<String>> sl = new ArrayList<List<String>>();
		for(int i = 0;i < n;i++){
			words[i] += " ";
			List<String> lo = new ArrayList<String>();
			int prev = 0;
			for(int j = 0;j < words[i].length()-1;j++){
				char c = words[i].charAt(j);
				char cn = words[i].charAt(j+1);
				if(!consonant(c) && consonant(cn)){
					lo.add(words[i].substring(prev, j+1));
					prev = j+1;
				}
			}
			words[i] = words[i].substring(0, words[i].length() - 1);
			l.add(lo);
			List<String> loo = new ArrayList<String>(lo);
			Collections.sort(loo);
			sl.add(loo);
		}
		
		Integer[] ord = new Integer[n];
		for(int i = 0;i < n;i++){
			ord[i] = i;
		}
		Arrays.sort(ord, new Comparator<Integer>(){
			public int compare(Integer x, Integer y)
			{
				for(int i = 0;i < sl.get(x).size() && i < sl.get(y).size();i++){
					if(!sl.get(x).get(i).equals(sl.get(y).get(i))){
						return sl.get(x).get(i).compareTo(sl.get(y).get(i));
					}
				}
				if(l.get(x).size() - l.get(y).size() != 0){
					return l.get(x).size() - l.get(y).size();
				}
				for(int i = 0;i < l.get(x).size() && i < l.get(y).size();i++){
					if(!l.get(x).get(i).equals(l.get(y).get(i))){
						return l.get(x).get(i).compareTo(l.get(y).get(i));
					}
				}
				return 0;
			}
		});
		
		String[] ret = new String[n];
		for(int i = 0;i < n;i++){
			ret[i] = words[ord[i]];
		}
		
		return ret;
	}
	
	boolean consonant(char c)
	{
		return !(c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o');
	}

	void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

1000

文字列の2次元配列photo(<=50*50)が与えられる。これのi行j列目に文字kがあるというのは、各辺がx,y軸に平行な四角形(2j,2i)-(2j+2,2i+2)の範囲に文字kがある、という認識で。このとき辺が隣接している四角形の連結成分で、面積がthreshold以上になるものを選んで、その連結成分を覆う、各辺がx,y軸に平行な最小の長方形の中心の座標をx,y座標昇順に列挙して返せ。

という問題の意味を理解するまでにかなりの時間を要した。わかればなんてことはない。ただのBFSで連結成分を拾って色々調べるだけだった。覆う長方形の中心も、x,y座標それぞれについて(最小座標+最大座標)/2で求められる。
最後に返す"x y"は"列 行"なことに注意。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class PlayerExtraction {
	public String[] extractPlayers(String[] photo, int k, int threshold) {
		int n = photo.length;
		int m = photo[0].length();
		char[][] p = new char[n][m];
		for(int i = 0;i < n;i++){
			p[i] = photo[i].toCharArray();
		}
		
		List<Integer> ll = new ArrayList<Integer>();
		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;j++){
				if(p[i][j] == k+'0'){
					Queue<Integer> q = new LinkedList<Integer>();
					q.add(i*m+j);
					int S = 0;
					int minr = i, maxr = i+1;
					int minc = j, maxc = j+1;
					p[i][j] = ' ';
					int[] dr = {1,0,-1,0};
					int[] dc = {0,1,0,-1};
					while(!q.isEmpty()){
						int cur = q.poll();
						int r = cur/m;
						int c = cur%m;
						minr = Math.min(minr, r);
						minc = Math.min(minc, c);
						maxr = Math.max(maxr, r+1);
						maxc = Math.max(maxc, c+1);
						S++;
						for(int l = 0;l < 4;l++){
							int nr = r+dr[l];
							int nc = c + dc[l];
							if(nr >= 0 && nr < n && nc >= 0 && nc < m && p[nr][nc] == k+'0'){
								p[nr][nc] = ' ';
								q.add(nr*m+nc);
							}
						}
					}
					if(4*S >= threshold){
						ll.add((minc+maxc)*2*n+(minr+maxr));
					}
				}
			}
		}
		Collections.sort(ll);
		String[] ret = new String[ll.size()];
		for(int i = 0;i < ll.size();i++){
			int cur = ll.get(i);
			int rr = cur % (2*n);
			int cc = cur / (2*n);
			ret[i] = cc + " " + rr;
		}
		
		return ret;
	}

	void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}