Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-02-15SRM399 (Practice)

練習。


問題結果ポイントその他
250AvoidingProductWA0.00いくらなんでもこれは通さなきゃダメだろ!
500BinarySumAccepted211.27方針が二転三転するうちにDP(探索)を思いつく
1000DancingPartyUnopened0.00見てない

SRM 399 AvoidingProduct

|  SRM 399 AvoidingProduct - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 399 AvoidingProduct - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8758


コーディングフェーズ

  • とりあえず {x, y, z} = {1〜n+1} での全探索を実装(←ここでもう間違ってる)
    • zのループに入る前に x * y が (n + 差の絶対値) を超えてたら探索しない(continue)という謎枝刈りをする
    • 配列aがたくさん埋まってたら間に合わないかもという考えつつも気にせず提出

  • 500を提出し250に戻ってくる
    • ちょっと気になったので配列aを1〜50で全埋めした場合をテスト
      • ローカルで1.7s。これはTLEする!
    • よく考えると枝刈りのとこcontinueじゃなくてbreakでいいよね なにやってんだ
    • 再提出

システムテスト後

  • あっさり落ちる。なんで!?
    • {1〜n+1}ではなく、最大の{1〜1001}で回すべき。それでも間に合うんだから
      • 念のため{1〜1501}で再実装。通した

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class AvoidingProduct {

	public int[] getTriple(int[] a, int n) {
		int minx = 9999;
		int miny = 9999;
		int minz = 9999;
		int mindist = Integer.MAX_VALUE / 4;
		
		
		boolean[] ok = new boolean[1501];
		Arrays.fill(ok, true);
		for (int x : a) {
			ok[x] = false;
		}

		
		List<Integer> il = new ArrayList<Integer>();
		for (int i = 1 ; i <= 1500 ; i++) {
			if (ok[i]) {
				il.add(i);
			}
		}
		
		for (int x : il) {
			for (int y : il) {
				for (int z : il) {
					int xyz = x * y * z;
					int val = Math.abs(xyz - n);
					if (xyz > n + mindist * 2) {
						break;
					}
					
					if (val < mindist) {
						mindist = val;
						minx = x;
						miny = y;
						minz = z;
					} else if (val == mindist) {
						if (minx > x) {
							minx = x;
							miny = y;
							minz = z;
						} else if (minx == x) {
							if (miny > y) {
								miny = y;
								minz = z;
							} else if (miny == y) {
								if (minz > z) {
									minz = z;
								}
							}
						}
					}
				}
			}
		}
		return new int[]{minx, miny, minz};
	}
}

SRM 399 BinarySum

|  SRM 399 BinarySum - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 399 BinarySum - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8711

コーディングフェーズ

  • はじめは数学的に解こうとした
    • 1のビットをどう動かせば最小になるかを考えるなどした
    • 難しい・・・
  • 30分後、ふと探索という考えが頭をよぎった
    • これ[桁][Aで使った1の数][Bで使った1の数][足した結果の1の数][繰上げフラグ] のDPでいけるじゃん
    • 実装

import java.util.Arrays;

public class BinarySum {

	public int rearrange(int a, int b, int c) {
		int an = Integer.bitCount(a);
		int bn = Integer.bitCount(b);
		int cn = Integer.bitCount(c);
		int maxdigit = 0;
		int[] cp = new int[]{a, b, c};
		for (int i = 0 ; i < 3 ; i++) {
			int digit = 0;
			while (cp[i] > 0) {
				cp[i] /= 2;
				digit++;
			}
			maxdigit = Math.max(maxdigit, digit);
		}
		if (an + bn < cn) {
			return -1;
		}
		
		int maxvalue = (1<<maxdigit)-1;
		long md = ((1L<<an)-1) + ((1L<<bn)-1);
		int mindigit = Long.bitCount(md);
		if (mindigit == cn) {
			if (md <= maxvalue) {
				return (int)md;
			} else {
				return -1;
			}
		}
		
		int ma = 32;
		long[][][][][] dp = new long[ma][ma][ma][ma][2];
		for (int i = 0 ; i < ma ; i++) {
			for (int j = 0 ; j < ma ; j++) {
				for (int k = 0 ; k < ma ; k++) {
					for (int l = 0 ; l < ma ; l++) {
						Arrays.fill(dp[i][j][k][l], Integer.MAX_VALUE);
					}
				}
			}
		}
		dp[0][0][0][0][0] = 0;
		for (int now = 0 ; now < maxdigit ; now++) {
			for (int oa = 0 ; oa <= an ; oa++) {
				for (int ob = 0 ; ob <= bn ; ob++) {
					for (int res = 0 ; res <= cn ; res++) {
						for (int carry = 0 ; carry <= 1 ; carry++) {
							if (dp[now][oa][ob][res][carry] != Integer.MAX_VALUE) {
								long base = dp[now][oa][ob][res][carry];
								// 0 + 0
								dp[now+1][oa][ob][res+carry][0] = Math.min(dp[now+1][oa][ob][res+carry][0], base + (carry<<now));
								
								
								// 1 + 0
								if (carry == 0) {
									dp[now+1][oa+1][ob][res+1][0] = Math.min(dp[now+1][oa+1][ob][res+1][0], base + (1<<now));
								} else {
									dp[now+1][oa+1][ob][res][1] = Math.min(dp[now+1][oa+1][ob][res][1], base);
								}

								// 0 + 1
								if (carry == 0) {
									dp[now+1][oa][ob+1][res+1][0] = Math.min(dp[now+1][oa][ob+1][res+1][0], base + (1<<now));
								} else {
									dp[now+1][oa][ob+1][res][1] = Math.min(dp[now+1][oa][ob+1][res][1], base);
								}
								
								
								// 1 + 1
								if (carry == 0) {
									dp[now+1][oa+1][ob+1][res][1] = Math.min(dp[now+1][oa+1][ob+1][res][0], base);
								} else {
									dp[now+1][oa+1][ob+1][res+1][1] = Math.min(dp[now+1][oa+1][ob+1][res+1][1], base + (1<<now));
								}
							}
						}
					}
				}
			}
		}
		return (dp[maxdigit][an][bn][cn][0] != Integer.MAX_VALUE) ? (int)dp[maxdigit][an][bn][cn][0] : -1;
	}

}