BottomCoder SRM 373 div2

SRM 373 div2

points	result	time
250	AC	3.5m
500	AC	11.5m
1000	AC	13.2m

後解き。
500がいい問題だった。

250

X,Y,P(<=1000)が与えられる。自然数a,bについて、aX+bYがPで割り切れるときのa+bの最小値を求めよ。ただし答えは2P以下になる。

一瞬面食らうが、最後の文のおかげで、a<=P, b<=Pで全走査すればいいとわかる。

public class TheEquation {

	public int leastSum(int X, int Y, int P) {
		int min = 2*P;
		for(int i = 1;i <= P;i++){
			for(int j = 1;j <= P;j++){
				if((i*X+j*Y)%P == 0 ){
					min = Math.min(min, i+j);
				}
			}
		}
		return min;
	}

}

500

先頭と末尾にスペースがない、スペースで区切られたtext(||<=50)が与えられる。これを7より大きいサイズのフォントで表示してwidth*height(<=10000*10000)に収めたい。ただしスペースの箇所しか改行に変えることはできず、フォントサイズがsのとき、1文字の横幅はs+2, 高さは2sとなる。収められる最大のフォントサイズを求めよ。そのようなサイズが存在しないときは-1を返せ。

フォントサイズを固定したときは、なるべく1行にたくさん収まるように詰めていく方針で埋めていけば良い。前もってスペースの位置をリストアップして(末尾も付け加えておく)おいて、現在のスペースまでで収まって、次のスペースで収まらない、あるいは次が存在しないところを探せばよい。
コードはsの二分探索でかいているが、答えはせいぜい5000までで、スペースの数も高々50/2個だろうから、線形探索でもよい。

import java.util.ArrayList;
import java.util.List;

public class StringFragmentation {

	int w, h;
	List<Integer> ss;
	
	public int largestFontSize(String text, int width, int height) {
		text += " ";
		ss = new ArrayList<Integer>();
		for(int i = 0;i < text.length();i++){
			if(text.charAt(i) == ' '){
				ss.add(i);
			}
		}
		
		w = width; h = height;
		int inf = 7;
		int sup = 10001;
		while(sup - inf > 1){
			int mid = (inf+sup)/2;
			if(ok(mid)){
				inf = mid;
			}else{
				sup = mid;
			}
		}
		return inf == 7 ? -1 : inf;
	}
	
	boolean ok(int n)
	{
		int m = ss.size();
		int prev = 0;
		int hh = 0;
		for(int i = 0;i < m;i++){
			if((n+2)*(ss.get(i)-prev) <= w){
				if(i+1 >= m || (n+2)*(ss.get(i+1)-prev) > w){
					prev = ss.get(i)+1;
					hh += 2*n;
					if(hh > h){
						return false;
					}
				}
			}else{
				return false;
			}
		}
		return true;
	}

}

1000

互いに共有点を持たない長方形がN(<=50)個ある。また、M(<=50)本の線分が与えられる。このとき、"線分の端点の少なくとも1個が内部にあるような長方形の面積の合計"と、"線分の端点が1個も内部にないが、少なくとも1本の線分と交わっている長方形の面積の合計"を求めよ。

求める2種類両方の性質を持つ長方形は存在しない。よって、"線分の端点の少なくとも1個が内部にあるような長方形"を求めてから、
"少なくとも1本の線分と交わっている長方形"から上記の長方形たちをのぞけば良い。
後者の長方形を求める段では、両端とも長方形内部にあるようなものは後々除かれるので、必ず線分と長方形の辺のどれかは交わっていると考える。線分同士の交点は、Javaではine2D.intersectsLineを使えば楽勝である。

import java.awt.geom.Line2D;
import java.util.BitSet;

public class RectangleCrossings {

	// 13.2
	public int[] countAreas(String[] rectangles, String[] segments) {
		int n = rectangles.length;
		int m = segments.length;
		int[][] rect = new int[n][4];
		int[][] seg = new int[m][4];
		for(int i = 0;i < n;i++){
			String[] sp = rectangles[i].split(" ");
			for(int j = 0;j < 4;j++){
				rect[i][j] = Integer.parseInt(sp[j]);
			}
		}
		for(int i = 0;i < m;i++){
			String[] sp = segments[i].split(" ");
			for(int j = 0;j < 4;j++){
				seg[i][j] = Integer.parseInt(sp[j]);
			}
		}
		
		BitSet end = new BitSet();
		for(int j = 0;j < m;j++){
			for(int i = 0;i < n;i++){
				if(rect[i][0] < seg[j][0] && seg[j][0] < rect[i][2] && rect[i][1] < seg[j][1] && seg[j][1] < rect[i][3]){
					end.set(i);
					break;
				}
			}
			for(int i = 0;i < n;i++){
				if(rect[i][0] < seg[j][2] && seg[j][2] < rect[i][2] && rect[i][1] < seg[j][3] && seg[j][3] < rect[i][3]){
					end.set(i);
					break;
				}
			}
		}
		
		BitSet inter = new BitSet();
		for(int j = 0;j < m;j++){
			for(int i = 0;i < n;i++){
				if(Line2D.linesIntersect(seg[j][0], seg[j][1], seg[j][2], seg[j][3], rect[i][0], rect[i][1], rect[i][0], rect[i][3]))inter.set(i);
				if(Line2D.linesIntersect(seg[j][0], seg[j][1], seg[j][2], seg[j][3], rect[i][0], rect[i][3], rect[i][2], rect[i][3]))inter.set(i);
				if(Line2D.linesIntersect(seg[j][0], seg[j][1], seg[j][2], seg[j][3], rect[i][2], rect[i][1], rect[i][2], rect[i][3]))inter.set(i);
				if(Line2D.linesIntersect(seg[j][0], seg[j][1], seg[j][2], seg[j][3], rect[i][0], rect[i][1], rect[i][2], rect[i][1]))inter.set(i);
			}
		}
		
		inter.andNot(end);
		int se = 0, si = 0;
		for(int i = end.nextSetBit(0);i != -1;i = end.nextSetBit(i+1)){
			se += (rect[i][3] - rect[i][1]) * (rect[i][2] - rect[i][0]);
		}
		for(int i = inter.nextSetBit(0);i != -1;i = inter.nextSetBit(i+1)){
			si += (rect[i][3] - rect[i][1]) * (rect[i][2] - rect[i][0]);
		}
		
		return new int[]{se, si};
	}

}