BottomCoder SRM 397 div2

SRM 397 div2

point	result	time
250	AC	10m以内
500	AC(resubmit)	15m以内
1000	WA1	30m以内

職場のクソPCがarenaを吹っ飛ばしてくれたのでtimeは推測。

250

26個の文字→インデックス(1-base)の暗号表が与えられる。これを使って、messageが数字のみで構成されている場合は2桁ずつ切り取って文字に復号化、文字のみで構成されている場合は1文字ずつ切り取って2桁詰めの数字に暗号化せよ。

実装ゲー。暗号表は26個しかないのでHashMapでよい。2桁ずつの書き出しはString.format("%02d",*)を使えば良い。

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

public class BreakingTheCode {

	public String decodingEncoding(String code, String message) {
		HashMap<String, String> map = new HashMap<String, String>();
		StringBuilder sb = new StringBuilder();
		if(message.charAt(0) >= '0' && message.charAt(0) <= '9'){
			for(int i = 0;i < 26;i++){
				map.put(String.format("%02d", i+1), code.substring(i, i+1));
			}
			for(int i = 0;i < message.length();i += 2){
				sb.append(map.get(message.substring(i, i+2)));
			}
		}else{
			for(int i = 0;i < 26;i++){
				map.put(code.substring(i, i+1), String.format("%02d", i+1));
			}
			for(int i = 0;i < message.length();i++){
				sb.append(map.get(message.substring(i, i+1)));
			}
		}
		return sb.toString();
	}
}

500

1からn(<=8)までの数が1個ずつ入っている配列boardが与えられる。これを次の操作を繰り返して昇順に並べ替えるときの最小手数を求めよ。並べ替えられない場合は-1を出力せよ。

隣り合うk(2<=k<=n)個の項を選んで反転させる。

ちょっとまえに似たような状況でメモ化再帰を使ったほうが簡単だったという某問題が頭にあったのでDFSでやってしまったのが仇。この問題の場合は再帰制限に引っかかる。(System Testではどうだかわからないけど)
というわけでBFSが正解。新しく現れた状態で以前の手数より短いものをぽんぽんキューに追加していく。キューが空になっても最終状態の手数がデフォのままだったら-1。それ以外は最終状態の手数を返す。状態数はたかだか8!=40320なので間に合う。
encPermとdecPermはpermutationとindexを詰めて1:1対応させる関数。少し前につくった。
また、ArrayDequeはJava6にしかなかったのでArrayBlockingQueueを使った。

import java.util.Arrays;
import java.util.BitSet;
import java.util.concurrent.ArrayBlockingQueue;

public class SortingGame {

	int k;
	int[] cache;
	int n;
	BitSet visited;
	
	public int fewestMoves(int[] board, int k) {
		n = board.length;
		for(int i = 0;i < n;i++)board[i]--;
		this.k = k;
		
		int[] d = new int[50000];
		Arrays.fill(d, 99999);
		
		int ini = encPerm(board);
		d[ini] = 0;
		ArrayBlockingQueue<Integer> q = new ArrayBlockingQueue<Integer>(200000);
		q.add(ini);
		
		while(q.size() > 0){
			int cur = q.poll();
			if(cur == 0)break;
			
			int[] b = decPerm(cur, n);
			int nd = d[cur] + 1;
			for(int i = 0;i <= n - k;i++){
				reverse(b, i, i + k);
				int next = encPerm(b);
				if(d[next] > nd){
					d[next] = nd;
					q.add(next);
				}
				reverse(b, i, i + k);
			}
		}
		
		int v = d[0];
		return v >= 99999 ? -1 : v;
	}
	
	public void reverse(int[] a, int x, int y)
	{
		for(int p = x, q = y - 1;p < q;p++, q--){
			int d = a[p]; a[p] = a[q]; a[q] = d;
		}
	}

	public static int encPerm(int[] a)
	{
		int n = a.length;
		int used = 0;
		int ret = 0;
		for(int i = 0;i < n;i++){
			ret = ret * (n - i) + a[i] - Integer.bitCount(used & ((1<<a[i]) - 1));
			used |= 1<<a[i];
		}
		return ret;
	}
	
	public static int[] decPerm(int c, int n)
	{
		int[] a = new int[n];
		for(int i = n - 1;i >= 0;c /= n - i, i--){
			int v = c % (n - i);
			a[i] = v;
			for(int j = i + 1;j <= n - 1;j++){
				if(v <= a[j])a[j]++;
			}
		}
		return a;
	}
}

1000

numberOfBags(<=10)個の容量bagCapacity(<=20)の袋がある。これにそれぞれの重さがmarblesWeight[i]のn(<=13)個のmarbleを入れる。marbleは、bagCapacityを超えては入れられないとき、これらの袋に詰められるmarbleの最大個数を求めよ。

ナップサック。似たような問題をどこかで見たような気がしたけど、忘却の彼方。結局ソートして再帰でやったけどやはりだめだった。いろいろ最大ケース試して間に合ったのにうーむ。

20以下のときはビットを疑え。というわけでBitDP.
dp[ptn(<=1<

import java.util.Arrays;

public class CollectingMarbles {

	public int mostMarbles(int[] marblesWeights, int bagCapacity, int numberOfBags) {
		int n = marblesWeights.length;
		
		int[] dp = new int[1<<n];
		Arrays.fill(dp, 99999);
		dp[0] = 0;
		for(int i = 1;i < 1<<n;i++){
			int sum = 0;
			for(int j = 0;j < n;j++){
				if(((i>>j)&1) == 1){
					sum += marblesWeights[j];
				}
			}
			if(sum <= bagCapacity){
				dp[i] = 1;
			}else{
				int min = 99999;
				for(int j = 0;j <= i;j++){
					min = Math.min(min, dp[i^(i&j)] + dp[i&j]);
				}
				dp[i] = min;
			}
		}
		
		int maxb = 0;
		for(int i = 0;i < 1<<n;i++){
			if(dp[i] <= numberOfBags && Integer.bitCount(i) > maxb){
				maxb = Integer.bitCount(i);
			}
		}
		return maxb;
	}
}

実際に提出したクソコード

import java.util.Arrays;

public class CollectingMarbles {

	int cap;
	int nob;
	int[] left;
	int[] w;
	int n;
	
	public int mostMarbles(int[] marblesWeights, int bagCapacity, int numberOfBags) {
		n = marblesWeights.length;
		w = marblesWeights;
		cap = bagCapacity;
		nob = numberOfBags;
		left = new int[nob];
		Arrays.fill(left, cap);
		
		Arrays.sort(marblesWeights);
		for(int i = 0;i <= n / 2;i++){
			int d = w[i]; w[i] = w[n-1-i]; w[n-1-i] = d;
		}
		return rec(0);
	}
	
	public int rec(int cur)
	{
		if(cur == n)return 0;
		
		int max = rec(cur+1);
		int exed = 0;
		for(int i = 0;i < left.length;i++){
			if(left[i] >= 0){
				if(((exed>>left[i])&1) == 0 && left[i] >= w[cur]){
					left[i] -= w[cur];
					max = Math.max(max, rec(cur+1) + 1);
					left[i] += w[cur];
				}
				exed |= 1<<left[i];
			}
		}
		return max;
	}
}