BottomCoder SRM 383 div2

SRM 383 div2

points	result	time
250	AC	3m
500	AC	8.4m
1000	AC	15m

ちょい易し目でした。

250

マップ(||<=50*50)上の'-'が横に連続したかたまりと'|'が縦に連続したかたまりの合計個数を求めよ。

この間のSRM496div1easyとすごく似てる。というかほとんど同じ。
すべてのセルについて走査。'-'だったら、左隣が'-'でなければカウント++, '|'だったら、上隣が'|'でなければカウント++, とすれば良い。

public class FloorLayout {

	public int countBoards(String[] layout) {
		int n = layout.length;
		int m = layout[0].length();
		int ct = 0;
		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;j++){
				if(layout[i].charAt(j) == '-'){
					if(j == 0 || layout[i].charAt(j-1) != '-'){
						ct++;
					}
				}else{
					if(i == 0 || layout[i-1].charAt(j) != '|'){
						ct++;
					}
				}
			}
		}
		return ct;
	}

}

500

N(<=50)個の長さlengths[*](<=10000)木の棒が与えられる。これをある長さになるようにそろえて切って売る(1つの木の棒から何個でも切り出せる)。長さLにそろえたとき、売値はL*(Lの長さの断片の個数)*woodValueとなる。また、1回切るためにcostPerCutだけかかる。このとき、売値-コストの最大値を求めよ。

最後のサンプルがなければ死んでいるところだった。

Lを全走査。(Lの長さの断片の個数)=\sum [lengths[*]/L]で与えられる。また、切り出す回数は、[lengths[*]/L]から、棒の長さがLの倍数なら1節約できるので、(切り出す合計回数)=\sum [(lengths[*]-1)/L]となる。これで売値-コストを計算して最大化すればよい。

public class Planks {

	public int makeSimilar(int[] lengths, int costPerCut, int woodValue) {
		int max = 0;
		for(int i = 1;i <= 10000;i++){
			int cost = 0;
			for(int len : lengths){
				cost += Math.max(0, -(len-1)/i * costPerCut + len/i*i*woodValue);
			}
			max = Math.max(max, cost);
		}
		return max;
	}

}

1000

N*M(<=25*25)の地図が与えられる。それぞれのセルは高さが0〜51となっている。(0,0)から出発して、隣のセルに移動して適当にまわって時間timeToDark以内に(0,0)に戻ってくる事を考える。隣のセルとの高低差の絶対値がthresholdより大きい場合は移動できない。高低差が+1以上の時は(高低差)^2の時間がかかり、それ以外のときは1だけ時間がかかる。このとき行けるセルの最大の高さを求めよ。

1セル1回縛りとかもないので、実はそんなに難しくない問題。

あるセルCについて、(0,0)とCとの最短往路と最短復路の合計がtimeToDark以内であればCに行けることになる。このようなCのうちの最高点を求めれば良い。
これを達するためには、(0,0)と全点との最短往路と最短復路を求めれば良い。最短往路は、dijkstraで行けるところまで網羅すればOK. 最短復路も、復路を逆行するようにdijkstraを構成すればよい。高低差が-1以下のとき2乗の時間がかかるように、それ以外は1の時間とする。これでO((NM)^2)でできる。
dijkstraのコードさえ用意しておけば、ほとんどコピペでできちゃったりする。

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

public class HillWalker {

	public int highestPoint(String[] landscape, int threshold, int timeToDark) {
		int n = landscape.length;
		int m = landscape[0].length();
		int[][] h = new int[n][m];
		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;j++){
				char c = landscape[i].charAt(j);
				if(c <= 'Z'){
					h[i][j] = c - 'A';
				}else{
					h[i][j] = c - 'a' + 26;
				}
			}
		}
		
		int[] dr = {1, 0, -1, 0};
		int[] dc = {0, 1, 0, -1};
		
		final int[] td = new int[n*m];
		Arrays.fill(td, Integer.MAX_VALUE / 3);
		{
			TreeSet<Integer> q = new TreeSet<Integer>(new Comparator<Integer>(){
				public int compare(Integer a, Integer b) {
					if(td[a] - td[b] != 0)return td[a] - td[b];
					return a - b;
				}
			});
			q.add(0);
			td[0] = 0;
			
			while(q.size() > 0){
				int cur = q.first();
				q.remove(cur);
				int r = cur / m;
				int c = cur % m;
				
				for(int i = 0;i < 4;i++){
					int nr = r + dr[i];
					int nc = c + dc[i];
					if(nr >= 0 && nr < n && nc >= 0 && nc < m){
						int dh = h[nr][nc] - h[r][c];
						if(dh <= threshold){
							int nd = td[cur] + (dh >= 1 ? dh * dh : 1);
							int x = nr * m + nc;
							if(nd < td[x]){
								q.remove(x);
								td[x] = nd;
								q.add(x);
							}
						}
					}
				}
			}
		}
		
		final int[] rd = new int[n*m];
		Arrays.fill(rd, Integer.MAX_VALUE / 3);
		{
			TreeSet<Integer> q = new TreeSet<Integer>(new Comparator<Integer>(){
				public int compare(Integer a, Integer b) {
					if(rd[a] - rd[b] != 0)return rd[a] - rd[b];
					return a - b;
				}
			});
			q.add(0);
			rd[0] = 0;
			
			while(q.size() > 0){
				int cur = q.first();
				q.remove(cur);
				int r = cur / m;
				int c = cur % m;
				
				for(int i = 0;i < 4;i++){
					int nr = r + dr[i];
					int nc = c + dc[i];
					if(nr >= 0 && nr < n && nc >= 0 && nc < m){
						int dh = h[nr][nc] - h[r][c];
						if(dh <= threshold){
							int nd = rd[cur] + (dh <= -1 ? dh * dh : 1);
							int x = nr * m + nc;
							if(nd < rd[x]){
								q.remove(x);
								rd[x] = nd;
								q.add(x);
							}
						}
					}
				}
			}
		}
		
		int maxh = 0;
		for(int i = 0;i < n*m;i++){
			if(td[i] + rd[i] <= timeToDark && maxh < h[i/m][i%m]){
				maxh = h[i/m][i%m];
			}
		}
		return maxh;
	}

}