BottomCoder SRM 387 div2

SRM 387 div2

points	result	time
250	AC	3.4m
600	WA2	29.5m
1000	AC	29.5m

今日も参加しませんでした(チェコちゃんの声で
寝ぼけてたとはいえ時間かかりすぎ。

250

数列(3<=||<=50, *<=10^6)が与えられる。これは等差数列か等比数列かのどちらか一方であることが分かっている場合、最後の項の次の項を求めよ。

等差数列か等比数列か判定していけば良い。一方の判定がfalseになったら、他方の項を予測するようにする。判定は両側の項の和・積が真ん中の項の2倍・2乗になってるかどうか調べれば良い。int超えに注意。

import java.util.Arrays;

public class GuessingNextElement {
	public int guess(int[] A) {
		for(int i = 0;i < A.length-1;i++){
			if(A[i] + A[i+2] != 2 * A[i+1]){
				return (int)((long)A[A.length-1] * A[1] / A[0]);
			}
			if((long)A[i] * A[i+2] != (long)A[i+1] * A[i+1]){
				return A[A.length-1] + A[1] - A[0];
			}
		}
		return 0;
	}

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

600

N(<=50)個の箱にM(<=50)種類のmarbleが入っている。最大ひとつの箱をJokerBoxとして、JokerBox以外の箱は最大1種類までしかmarbleが入れず、さらに同じ種類のmarbleはJokerBox以外の2つ以上の箱に入らないようにmarbleを箱間で移動させる。箱から他の箱に複数のmarbleを他の箱に移動させるコストを1とするとき、最小コストを求めよ。

JokerBoxを1個適当に決めて、残りの箱からJokerBoxにmarbleを渡しまくればよい(カウント+1ずつ)。このとき、元の箱に1種類しかmarbleが入っていなくて、それまでに同じ種類のmarbleしかはいていない箱が存在しないときは、渡さなくて良い。(カウント+0)元の箱に何も入っていない時も、渡さなくて良い(カウント+0)。こうしてカウントしたものの最小値が答え。

最初太字の部分をhardみたいに読んでいたので、え、なにこれ無理ゲーじゃねとか思ってたがそんなことはなかった。WAは、1L<

import java.util.Arrays;

public class MarblesRegroupingEasy {
	public int minMoves(String[] boxes) {
		int n = boxes.length;
		int m = boxes[0].length();
		long[] b = new long[n];
		for(int i = 0;i < n;i++){
			long u = 0;
			for(int j = 0;j < m;j++){
				u |= (boxes[i].charAt(j)>'0' ? 1L : 0L)<<j;
			}
			b[i] = u;
		}
		
		int min = 999;
		for(int i = 0;i < n;i++){
			long mask = (1L<<m)-1;
			int ct = 0;
			for(int j = 0;j < n;j++){
				if(i != j){
					int bc = Long.bitCount(b[j]);
					if(bc == 0){
					
					}else if(bc == 1){
						if((b[j]&mask)==0){
							ct++;
						}else{
							mask^=b[j];
						}
					}else{
						ct++;
					}
				}
			}
			min = Math.min(min, ct);
		}
		return min;
	}

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

1000

N(<=50)個の箱にM(<=14)種類のmarbleが入っている。どの箱も最大1種類までしかmarbleが入れず、さらに同じ種類のmarbleはJokerBox以外の2つ以上の箱に入らないようにmarbleを箱間で移動させる。箱から他の箱に1個のmarbleを移動させるコストを1とするとき、最小コストを求めよ。

20以下はbit!ということでBitDP.今度は「また同じ問題かーめんどくせー」と思いつつJokerBoxがあるもんだとばっかり思ってたが無くていいようだ。

dp[i][j]=(i番目の箱までみたときの、種類パターンjまで埋まっているような最小コスト)とする。(51*2^14)
種類パターンというのは、0番目の箱を2番目の種類のみの箱にしようとおもったら1<<2が立つようなbitパターン。

最終的にはどの箱も1種類のパターンのmarbleが入るか、何も入らないかのどちらかなので、漸化式は、
dp[i][j]=min_{k:jの1つのbitまたは0} (dp[i-1][j^k]+sums[i-1]-boxes[i-1][magic[k]])
boxes[i][j]は、i番目の箱にあるj番目の種類のmarbleの個数。
magic[k]は、2^t→tに変換する関数。
sums[i]は、i番目の箱にあるmarbleの総数。
どれもdpの前に準備できる。

最後はどんな種類パターンになってても関係ないので、min dp[n][*]を求めればよい。

import java.util.Arrays;

public class MarblesRegroupingHard {
	public int minMoves(String[] boxes) {
		int n = boxes.length;
		int[][] b = new int[n][];
		int[] sums = new int[n];
		int m = 0;
		for(int i = 0;i < n;i++){
			String[] sp = boxes[i].split(" ");
			int[] row = new int[sp.length];
			int sum = 0;
			for(int j = 0;j < sp.length;j++){
				row[j] = Integer.parseInt(sp[j]);
				sum += row[j];
			}
			b[i] = row;
			sums[i] = sum;
			m = sp.length;
		}
		
		int[] map = {0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13, 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14};
		
		int[][] dp = new int[n+1][1<<m];
		for(int i = 0;i < 1<<m;i++){
			dp[0][i] = 99999999;
		}
		dp[0][0] = 0;
		
		for(int i = 1;i <= n;i++){
				for(int j = 0;j < 1<<m;j++){
					int min = dp[i-1][j] + sums[i-1];
					for(int l = j;l > 0;l &= l - 1){
						int t = l&-l;
						int u = map[t*0x076be629>>>27];
						min = Math.min(min, dp[i-1][j^t] + sums[i-1] - b[i-1][u]);
					}
					dp[i][j] = min;
				}
		}
		
		int gmin = 99999999;
		for(int i = 0;i < 1<<m;i++){
			gmin = Math.min(gmin, dp[n][i]);
		}
		return gmin;
	}

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