BottomCoder SRM 370 div2

SRM 370 div2

points	result	time
250	AC	2.7m
500	AC	4.4m
1000	AC	46.5m

でたー！T9だー！

250

containers(||<=50)のサイズのコンテナににpackages(||<=50)のサイズのパッケージを、前から貪欲に入れて収まりきれなくなったら次のコンテナへ、という風にいれる。全てのパッケージが収まりきることがわかっているとき、収めた後のコンテナの空いている空間のサイズの合計を求めよ。

え、ただたすだけじゃん？とか思ってなんども見直した。

import java.util.Arrays;

public class Containers {
	public int wastedSpace(int[] containers, int[] packages) {
		int s = 0;
		for(int c : containers){
			s += c;
		}
		for(int p : packages){
			s -= p;
		}
		return s;
	}

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

500

箱のなかにある各色のボールの個数がcolors(||<=50)で与えられる。箱からランダムにn(<=sum colors[*])個のボールを取り出すとき、それらが全て同じ色になっている確率を求めよ。

簡単な確率の問題。S=sum colors[*]とすると、
sum_i C(colors[i], n)/C(S,n)
となる。

BigIntegerで計算しているが、別にdoubleでも良い。

import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.Arrays;

public class DrawingMarbles {
	public double sameColor(int[] colors, int n) {
		int sum = 0;
		for(int c : colors){
			sum += c;
		}
		BigInteger den = BigInteger.ONE;
		for(int i = 0;i < n;i++){
			den = den.multiply(BigInteger.valueOf(sum-i));
		}
		BigInteger num = BigInteger.ZERO;
		for(int c : colors){
			if(c >= n){
				BigInteger lnum = BigInteger.ONE;
				for(int i = 0;i < n;i++){
					lnum = lnum.multiply(BigInteger.valueOf(c-i));
				}
				num = num.add(lnum);
			}
		}
		return new BigDecimal(num).divide(new BigDecimal(den), 20, RoundingMode.HALF_UP).doubleValue();
	}

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

1000

T9の入力方式で文字列message(||<=50)を最短ストロークで入力したい。T9の入力方式は以下のとおり。a-zに合計8通りのキーが割り当てられ、このキーをk個入力すると、同じキーストロークで始まる辞書(||<=2500/3?)内の単語のうち一番最初のものの、最初のk文字が表示される。"Next in dictionary"を押すと、辞書内で該当する次の単語の最初のk文字が表示される。また、"New word"を押すと表示中の文字はすべて確定される。スペースを押すと表示中の文字を全て確定した上にスペース文字を追加する。最短ストローク数を答えよ。どうやっても打てない場合は-1を答えよ。ただし終了時に確定されている必要はない。

実装+DPといういやらしいコンビ。最近SRM490のdiv1mediumで類題が出た。やり方は基本的に同じ。

全確定状態から全確定状態に移行する際に増える文字列は、かならず辞書内の文字列のprefix全体の集合のどれかの要素になっている。まずは、このprefixをうつための最短ストローク数を求める。ある辞書内の単語Wのprefix Pについて、これをうつためのストローク数は、(Pと同じキーストロークのprefixを持つ、辞書内でWより前にある単語の個数)+(Pの文字数)で与えられる。同じ字面のprefixのなかでは最小のものを選んでおく。

次にDPをする。dp[i]=(messageのi-1文字目まで入力するまでの最短ストローク数)とする。i-1文字目がスペースのときはdp[i]=dp[i-1]+1となる。
i-1文字目がスペース以外の場合、0<=j

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

public class JohnnysPhone {
	int INF = Integer.MAX_VALUE / 10;
	
	public int minimizePushes(String[] dictionary, String message) {
		StringBuilder sb = new StringBuilder();
		for(String w : dictionary)sb.append(w);
		String[] dic = sb.toString().split(" ");
		int m = dic.length;
		String[] td = new String[m];
		for(int i = 0;i < m;i++){
			td[i] = trans(dic[i]);
		}
		
		Map<String, Integer> mins = new HashMap<String, Integer>();
		for(int i = 0;i < m;i++){
			String w = dic[i];
			for(int j = 1;j <= w.length();j++){
				String sub = w.substring(0, j);
				String subt = td[i].substring(0, j);
				int ct = 0;
				for(int k = 0;k < i;k++){
					if(dic[k].length() >= j && subt.equals(td[k].substring(0, j))){
						ct++;
					}
				}
				if(!mins.containsKey(sub))mins.put(sub, INF);
				mins.put(sub, Math.min(ct+j, mins.get(sub)));
			}
		}
//		tr(mins);
		
		int n = message.length();
		int[] dp = new int[n+1];
		dp[0] = 0;
		for(int i = 1;i <= n;i++){
			int min = INF;
			if(message.charAt(i-1) == ' '){
				dp[i] = dp[i-1]+1;
			}else{
				for(int j = 0;j < i;j++){
					String u = message.substring(j, i);
					if(mins.containsKey(u)){
//						tr(j, i, u, mins.get(u));
						min = Math.min(min, dp[j]+(j==0 || message.charAt(j-1) == ' ' ? 0:1)+mins.get(u));
					}
				}
				dp[i] = min;
			}
		}
//		tr(dp);
		
		return dp[n] >= INF ? -1 : dp[n];
	}
	
	String trans(String x)
	{
		StringBuilder nw = new StringBuilder();
		for(int j = 0;j < x.length();j++){
			if(x.charAt(j) == ' '){
				nw.append(' ');
			}else{
				nw.append(AL[x.charAt(j)-'a']);
			}
		}
		return nw.toString();
	}
	
	char[] AL = "22233344455566677778889999".toCharArray();

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