BottomCoder SRM 402 div2

SRM402 div2

point	result	time
250	AC	4m
500	WA1	6m
1000	AC	27m

500がみんな落ちてて泣いた。引っ掛け問題に本当に弱い。

250

要素数N(<=50)の文字列(||<=50)配列が与えられる。各文字列について、その接頭辞でかつ他の文字列の接頭辞とならない最小長の文字列を並べた配列を出力せよ。ただしこれらの文字列は必ず存在するとする。

問題文の通りにやるだけ。Java的にはsubstring(0,i)をとって他の文字列でstartsWithしていないかどうか調べれば良い。

public class WordAbbreviation {

	public String[] getAbbreviations(String[] words) {
		int n = words.length;
		String[] ret = new String[n];
		for(int i = 0;i < n;i++){
			outer:
			for(int j = 1;j <= words[i].length();j++){
				String sub = words[i].substring(0, j);
				for(int k = 0;k < n;k++){
					if(i != k && words[k].startsWith(sub)){
						continue outer;
					}
				}
				ret[i] = sub;
				break;
			}
		}
		return ret;
	}

}

500

要素数N(<=50)の自然数の配列が与えられる。これらがある連続した(7,8,9,10,11のような)自然数の配列から1個除いて順番を変えたものである場合、除いた可能性のある数字を昇順に並べた配列を出力せよ。

と書くとはっきりわかるが、本来の問題文からはあたかも、既成の配列から除いたことありきのように書かれ・・となるとsample出力の空配列はどうなんだよってツッコミを自分に飛ばせなかったのがくやしい。

数字が除かれた可能性のある配列は、ソートしたとき間隔がオール1(A)または1箇所だけ2(B)となっている。Aの場合は両端の外側に、Bの場合は間隔2のところにある数字が答えとなる。下限が1なことに注意。

コードは後付けで間隔チェックを入れたため少々汚い。

import java.util.Arrays;

public class ConsecutiveNumbers {

	public int[] missingNumber(int[] numbers) {
		int n = numbers.length;
		Arrays.sort(numbers);
		int d2 = 0;
		for(int i = 0;i < n - 1;i++){
			int d = numbers[i+1] - numbers[i];
			if(d == 0 || d >= 3)return new int[0];
			if(d == 2){
				if(d2 >= 1)return new int[0];
				d2++;
			}
		}
		
		if(numbers[n-1] - numbers[0] >= n + 1){
			return new int[0];
		}else if(numbers[n-1] - numbers[0] == n){
			for(int i = 0;i < n - 1;i++){
				if(numbers[i+1] - numbers[i] == 2){
					return new int[]{numbers[i] + 1};
				}
			}
		}else{
			if(numbers[0] == 1){
				return new int[]{numbers[n-1] + 1};
			}else{
				return new int[]{numbers[0] - 1, numbers[n-1] + 1};
			}
		}
		
		return null;
	}

}

1000

n(<=8)個の順列(1〜nの並び替え)がある。これをソートしたい。次の操作を繰り返してソートするとき、操作回数の期待値を求めよ。

• 順列の中で[i]>[j]となっているペア(i,j)の集合から等確率で選び、その要素を交換する。

状態数は高々8!しかないのでメモ化再帰で十分。期待値の計算は、最終状態では0、それ以外の場合は、次の状態の期待値の平均+1とすればよい。

ペアの数によってトポロジカルソートできるからDPでできるな、と思ってDP書いたアホでーす。前もこんな感じでメモ化再帰で簡単に書けるところをDPで書いてしまうDP病。時間もdiv1easyの平均を上回ってしまってこれはよくない。
あと課題としては、順列と自然数の1:1対応。今回は10進で書いてしまったけれど、1〜n!と1:1対応させることもできる・・よね？というわけでこれをライブラリに加えるTODO.

import java.util.HashMap;
import java.util.Map;

public class RandomSort {

	Map<Integer, Double> codeE = new HashMap<Integer, Double>();
	
	public double rec(int[] perm)
	{
		int n = perm.length;
		int code = 0;
		for(int i = 0;i < n;i++){
			code = code * 10 + perm[i];
		}
		if(codeE.containsKey(code)){
			return codeE.get(code);
		}
		
		double e = 0.0;
		int m = 0;
		for(int i = 0;i < n;i++){
			for(int j = i + 1;j < n;j++){
				if(perm[i] > perm[j]){
					int d = perm[i]; perm[i] = perm[j]; perm[j] = d;
					e += rec(perm);
					m++;
					d = perm[i]; perm[i] = perm[j]; perm[j] = d;
				}
			}
		}
		
		if(m == 0){
			codeE.put(code, 0.0);
			return 0;
		}
		e = e / m + 1;
		codeE.put(code, e);
		return e;
	}
	
	public double getExpected(int[] permutation) {
		return rec(permutation);
	}
}

誰得のDP版もおいておく

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class CopyOfRandomSort {

	Map<Integer, Integer> codeDif = new HashMap<Integer, Integer>();
	
	public void rec(int[] perm)
	{
		int n = perm.length;
		int dif = 0;
		int code = 0;
		for(int i = 0;i < n;i++){
			code = code * 10 + perm[i];
		}
		if(codeDif.containsKey(code)){
			return;
		}
		for(int i = 0;i < n;i++){
			for(int j = i + 1;j < n;j++){
				if(perm[i] > perm[j]){
					dif++;
					int d = perm[i]; perm[i] = perm[j]; perm[j] = d;
					rec(perm);
					d = perm[i]; perm[i] = perm[j]; perm[j] = d;
				}
			}
		}
		
		codeDif.put(code, dif);
	}
	
	public double getExpected(int[] permutation) {
		int n = permutation.length;
		rec(permutation);
		List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(codeDif.entrySet());
		
		int m = list.size();
		Integer[] ord = new Integer[m];
		for(int i = 0;i < m;i++){
			ord[i] = i;
		}
		Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>(){
			public int compare(Map.Entry<Integer, Integer> x, Map.Entry<Integer, Integer> y){
				return x.getValue() - y.getValue();
			}
		});
		Map<Integer, Integer> codeInd = new HashMap<Integer, Integer>();
		for(int i = 0;i < m;i++){
			codeInd.put(list.get(i).getKey(), i);
		}
		
		double[] dp = new double[m];
		int[] a = new int[n];
		for(int i = 1;i < m;i++){
			int code = list.get(i).getKey();
			for(int k = 0;k < n;k++, code /= 10){
				a[n - 1 - k] = code % 10;
			}
			double sum = 0;
			for(int l = 0;l < n;l++){
				for(int j = l + 1;j < n;j++){
					if(a[l] > a[j]){
						int d = a[l]; a[l] = a[j]; a[j] = d;
						int c = 0;
						for(int q = 0;q < n;q++){
							c = c * 10 + a[q];
						}
						sum += dp[codeInd.get(c)];
						d = a[l]; a[l] = a[j]; a[j] = d;
					}
				}
			}
			
			dp[i] = sum / list.get(i).getValue() + 1;
		}
		
		return dp[m-1];
	}
	
	public static boolean nextPermutation(int[] src)
	{
		int i;
		for(i = src.length - 2;i >= 0 && src[i] > src[i+1];i--);
		if(i == -1)return false;
		int j;
		for(j = i + 1;j < src.length && src[i] < src[j];j++);
		int d = src[i]; src[i] = src[j - 1]; src[j - 1] = d;
		for(int p = i + 1, q = src.length - 1;p < q;p++,q--){
			d = src[p]; src[p] = src[q]; src[q] = d;
		}
		return true;
	}
}