BottomCoder SRM 404 div2

長らく更新してないので、ここにBottomCoderでの記録でも書いていこうと思う。
BottomCoderっていうのは、@aomoriringo @phyllo @Matsu4512 等々同じ研究室の面々が平日毎日自主的にやっているSRM div2解きで、僕はそれに勝手に割り込んで参加している。
YellowCoderには簡単かもしれないが、div2hardはやはり手応えがあるし、どれほど正しいと思ってsubmitしても、凡ミスひとつで0点になることにビクビクしながら解くのも興奮するので。
問題において制約は重要な要素なので、概要にもできるだけ書く。A(||<=100)とかいてあったら、Aの要素数が100以下という意味。

SRM404 div2

point	result	time
250	AC	12m
500	AC	11m
1000	AC	37m

250

文字列配列readParts(||<=50)に読んだ本(複数)の"introduction", "story", "edification"のどれかが読んだ順に入っている。同じ箇所は高々1度しか読まず、一度違う本を読んだら前の本には戻らないとき、上記の3箇所を全て読んだ本の数の最大値を求めよ。

最初順番関係ないのかと思ってただカウントアップして最小値をとったら見事に外れたので問題文を読み直す。
貪欲にとればいいのねとわかって書いたがなぜか最後のsampleが通らない。まさかDPか、ということでDPを書いた結果がこれだよ！
実際は貪欲で良い。というかなぜDP書いた。

public class ReadingBooks {
	public int countBooks(String[] readParts) {
		int n = readParts.length;
		int[] dp = new int[n+1];
		for(int i = 3;i <= n;i++){
			String[] s = new String[]{readParts[i-3], readParts[i-2], readParts[i-1]};
			Arrays.sort(s);
			if(s[0].equals("edification") && s[1].equals("introduction") && s[2].equals("story")){
				dp[i] = Math.max(dp[i-1], dp[i-3] + 1);
			}else{
				dp[i] = dp[i-1];
			}
		}
		return dp[n];
	}
}

500

1桁の数字からなる縦横n*n(<=50*50)の直角二等辺三角形がある。この三角形は隣り合う二つの数をたした1の位が左側の数の直下の値になっている。三角形のいくつかの数字が?になっているものが与えられたとき、すべての?に数字を埋めて三角形を復元せよ。

sample1で理解した。一瞬下から埋めていくのかなーとおもったけど、3個のうち2個が埋まっているものの残りの?を埋められるので、これを繰り返すだけでいいとわかった。冗長っぽくかいてるけどO(N^4)でせふ。

import java.util.Arrays;

public class RevealTriangle {
	public String[] calcTriangle(String[] questionMarkTriangle) {
		int n = questionMarkTriangle.length;
		char[][] tri = new char[n][];
		for(int i = 0;i < n;i++){
			tri[i] = questionMarkTriangle[i].toCharArray();
		}
		
		int[] filled = new int[n*n];
		for(int i = 0;i < n;i++){
			for(int j = 0;j < n - i - 1;j++){
				filled[i*n+j] = 
					(tri[i][j] == '?' ? 0 : 1) +
					(tri[i][j+1] == '?' ? 0 : 1) +
					(tri[i+1][j] == '?' ? 0 : 1);
			}
		}
		
		while(true){
			boolean fo = false;
			for(int i = 0;i < n*n;i++){
				if(filled[i] == 2){
					fo = true;
					filled[i]++;
					int r = i / n;
					int c = i % n;
					if(tri[r][c] == '?'){
						tri[r][c] = (char)('0' + ((tri[r+1][c] - tri[r][c+1] + 10) % 10));
						if(r >= 1)filled[(r-1)*n+c]++;
						if(c >= 1)filled[r*n+c-1]++;
					}else if(tri[r][c+1] == '?'){
						tri[r][c+1] = (char)('0' + ((tri[r+1][c] - tri[r][c] + 10) % 10));
						if(c < n - r - 1 && r >= 1)filled[(r-1)*n+(c+1)]++;
						if(c < n - r - 1)filled[r*n+c+1]++;
					}else if(tri[r+1][c] == '?'){
						tri[r+1][c] = (char)('0' + ((tri[r][c] + tri[r][c+1]) % 10));
						if(r < n - 1 && c >= 1)filled[(r+1)*n+(c-1)]++;
						if(r < n - 1)filled[(r+1)*n+c]++;
					}
				}
			}
			if(!fo)break;
		}
		
		String[] ret = new String[n];
		for(int i = 0;i < n;i++){
			ret[i] = new String(tri[i]);
		}
		return ret;
	}
}

1000

x軸に平行な互いに共有点を持たない線分がn(<=50)本ある。y=0からスタートして、(y=0または線分)からy座標が等しいかより大きい線分への距離がK以下の場合線分から線分へ飛び移れる。線分iにはsweets[i]のスイーツがあり、線分に乗ったらスイーツを獲得できる。最終的に獲得できるスイーツの最大値を求めよ。

同じ階さえなければーと唸っていた。同じ階がなければy座標昇順でソートしてDPでOK. 同じ階をどう扱うか〜とハヤシライスを盛りながら考える。
x座標昇順にソートしておけば、ある線分から飛び移れる線分たちは連続していて、隣隣に飛び移れるかどうかしらべていけばよさげ。飛び移りは可逆なので、飛び移れる範囲すべてのスイーツをゲット出来る。ゲットした主人公は飛び移れる範囲すべてのスイーツ最大値を更新しうる。

コードは、leap[i][j]でiからjに飛び移れるか、sleap[i]でy=0からiに飛び移れるかを最初に調べちゃう。ordでインデックスをy,xの昇順に並べ替えて、それ以降はordを経由してアクセスする。同じ階をまとめて扱う感じでDPっていく。最後に全部の最大値をとっておわり。到達不可能な階からは飛び移れないようにしないといけないことにちゅうい。
O(N^3). うまくやればO(N^2)だと思うけど制約的に必要なさげ。

import java.util.Arrays;
import java.util.Comparator;

public class GetToTheTop {
	public int collectSweets(int K, int[] sweets, final int[] x, final int[] y, int[] stairLength) {
		int n = sweets.length;
		boolean[][] leap = new boolean[n][n];
		for(int i = 0;i < n;i++){
			for(int j = 0;j < n;j++){
				if(i != j && y[j] >= y[i]){
					int d2 = 0;
					if(x[i] + stairLength[i] < x[j]){
						d2 = (x[j] - (x[i] + stairLength[i])) * (x[j] - (x[i] + stairLength[i])) + (y[j] - y[i]) * (y[j] - y[i]);
					}else if(x[j] + stairLength[j] < x[i]){
						d2 = (x[i] - (x[j] + stairLength[j])) * (x[i] - (x[j] + stairLength[j])) + (y[j] - y[i]) * (y[j] - y[i]);
					}else{
						d2 = (y[j] - y[i]) * (y[j] - y[i]);
					}
					leap[i][j] = d2 <= K * K;
				}
			}
		}
		boolean[] sleap = new boolean[n];
		for(int i = 0;i < n;i++){
			sleap[i] = y[i] <= K;
		}
		
		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 a, Integer b)
			{
				if(y[a] - y[b] != 0)return y[a] - y[b];
				return x[a] - x[b];
			}
		});
		
		int[] dp = new int[n];
		Arrays.fill(dp, -1);
		
		int start = 0;
		for(int i = 1;i <= n;i++){
			if(i == n || y[ord[i-1]] < y[ord[i]]){
				for(int j = start;j < i;j++){
					int max = -1;
					if(sleap[ord[j]]){
						max = 0;
					}
					for(int k = 0;k < start;k++){
						if(leap[ord[k]][ord[j]] && dp[k] != -1){
							max = Math.max(max, dp[k]);
						}
					}
					if(max != -1){
						dp[j] = max + sweets[ord[j]];
					}else{
						dp[j] = -1;
					}
				}
				int[] qdp = new int[n];
				Arrays.fill(qdp, -1);
				for(int j = start;j < i;j++){
					if(dp[j] != -1){
						int k, l;
						int sw = 0;
						for(k = j;k < i - 1 && leap[ord[k]][ord[k+1]];k++)sw += sweets[ord[k+1]];
						for(l = j;l >= start + 1 && leap[ord[l]][ord[l-1]];l--)sw += sweets[ord[l-1]];
						for(int u = l;u <= k;u++){
							qdp[u] = Math.max(qdp[u], sw + dp[j]);
						}
					}
				}
				for(int j = start;j < i;j++){
					dp[j] = Math.max(dp[j], qdp[j]);
				}
				start = i;
			}
		}
		
		int mx = 0;
		for(int i = 0;i < n;i++){
			mx = Math.max(mx, dp[i]);
		}
		
		return mx;
	}
}