BottomCoder SRM 394 div2

SRM 394 div2

points	result	time
250	AC	4.5
500	AC	20.5
1000	MLE(ダメもとsubmit)	∞

カラフルだった今回。発想力を問う問題でまくり。

250

各マスに高さ(0〜9)が指定されているマップareaMap(<=50*50)がある。(0,0)からはじめて、次の操作を、もうできなくなるまでに行うときの回数を求めよ。

(i,j)にいるとき(i+1, j), (i, j-1), (i-1, j), (i, j+1)の順に探索する。探索先がマップの中にあって、一度も訪れたことがなくて、(i,j)との高低差がheightDifference以下のときにそこに移動する。

実装ゲー。操作の指示通りに書きます。

import java.util.Arrays;

public class MountainWalk {
	public int cellsVisited(String[] areaMap, int heightDifference) {
		int n = areaMap.length;
		int m = areaMap[0].length();
		char[][] map = new char[n][m];
		for(int i = 0;i < n;i++)map[i] = areaMap[i].toCharArray();
		boolean[][] visited = new boolean[n][m];
		int r = 0, c = 0;
		int[] dr = {1, 0, -1, 0};
		int[] dc = {0, -1, 0, 1};
		int step = 0;
		outer:
		while(true){
			visited[r][c] = true;
			step++;
			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 && !visited[nr][nc] && Math.abs(map[r][c] - map[nr][nc]) <= heightDifference){
					r = nr;
					c = nc;
					continue outer;
				}
			}
			break;
		}
		return step;
		
	}

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

500

小文字だけからなる文字列s(||<=50)が与えられる。ここから最大n文字削って、同じ文字の最多文字数-同じ文字の最少文字数(0は含まない)を最小にしたい。最小値を求めよ。

貪欲かなーDPかなーとか考えたけど、書きかけるとどうもしっくりこない・・というところでひらめいた。
問われているのは最多文字数と最少文字数なので、たとえば最多文字数をAにしたとき、これを実現するためにはAより多いの文字数になっているものを削ってAにすれば良い。同様に、最少文字数をBにしたとき、B未満の文字数になっているものを削って0にすれば良い。
そうして、各A,Bについて実現するための削除文字数がわかるので、全走査して、削除文字数がn以下でかつ差が最小であるものを選べば良い。

import java.util.Arrays;

public class RoughStrings {
	public int minRoughness(String s, int n) {
		int m = s.length();
		int[] ct = new int[26];
		for(int i = 0;i < m;i++){
			ct[s.charAt(i)-'a']++;
		}
		
		int[] tmax = new int[m+1];
		for(int i = 1;i <= m;i++){
			int sum = 0;
			for(int j = 0;j < 26;j++){
				if(ct[j] >= i){
					sum += ct[j] - i;
				}
			}
			tmax[i] = sum;
		}
		
		int[] tmin = new int[m+1];
		for(int i = 1;i <= m;i++){
			int sum = 0;
			for(int j = 0;j < 26;j++){
				if(ct[j] < i){
					sum += ct[j];
				}
			}
			tmin[i] = sum;
		}
		
		int min = 9999;
		for(int i = 1;i <= m;i++){
			for(int j = 1;j <= i;j++){
				if(min > i - j && tmax[i] + tmin[j] <= n){
					min = i - j;
				}
			}
		}
		return min;
	}

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

1000

整数xに対し、d(x)=#{k|1<=k

import java.util.Arrays;

public class ProperDivisors {
	// k<m, k|m, k^n!|m
	public int analyzeInterval(int a, int b, int n) {
		int ct = 0;
		for(int i = 1;i <= a+b;i++){
			ct += (a+b)/i-(a-1)/i;
		}
		ct -= (b+1);
		for(int p = 1;;p++){
			long q = 1;
			for(int i = 0;i < n;i++)q *= p;
			if(q > a+b)break;
			ct -= (a+b)/q-(a-1)/q;
		}
		if(a == 1)ct++;
		
		return ct;
	}
	
	void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

こっちはやけくそ提出版。最大ケースで手元で2.9s近くかかっていた。約数を篩っぽくだすがあえなくMLE.

import java.util.Arrays;
import java.util.BitSet;

public class CopyOfProperDivisors {
	// k<m, k|m, k^n!|m
	public int analyzeInterval(int a, int b, int n) {
		b += a;
		int ct = b - a + 1;
		for(int p = 2;;p++){
			int q = 1;
			for(int i = 0;i < n;i++)q *= p;
			if(q > b)break;
			int sup = b - b%q;
			int inf = a - a%q;
			if(inf < a)inf += q;
			ct += (sup - inf) / q + 1;
		}
		
		int[] u = new int[b+1];
		int[] r = new int[b+1];
		Arrays.fill(r,a,b+1,1);
		for(int i = a;i <= b;i++){
			u[i] = i;
		}
		
		int[] primes = sieveEratosthenes((int)Math.sqrt(b));
		
		for(int p : primes){
			int f = a - a%p;
			if(f < a)f += p;
			for(int i = f;i <= b;i+=p){
				int c = 0;
				for(;u[i] % p == 0;u[i] /= p, c++);
				if(c > 0){
					r[i] *= c+1;
				}
			}
		}
		
		int all = -ct;
		for(int i = a;i <= b;i++){
			if(u[i] > 1){
				all += r[i] * 2 - 1;
			}else{
				all += r[i] - 1;
			}
		}
		if(a == 1)all++;
		
		return all;
	}
	
	public static int[] sieveEratosthenes(int n)
	{
		int[] ret = new int[(int)(n / Math.log(n)) + (int)(n / (Math.log(n)*Math.log(n))*1.5)  ];
		ret[0] = 2;
		int pos = 1;
		
		// 0:3 1:5
		// 2x+3=n
		BitSet bs = new BitSet(n/2+1);
		int sup = (n - 3) / 2;
		for(int i = bs.nextClearBit(0);i <= sup; i = bs.nextClearBit(i+1)){
			int p = 2 * i + 3;
			ret[pos++] = p;
			for(int j = i + p;j <= sup;j += p){
				bs.set(j);
			}
		}
		
		int[] res = new int[pos];
		for(int i = 0;i < pos;i++)res[i] = ret[i];
		return res;
	}
	
	void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}