Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-25SRM362, SRM363 (Practice)

SRM362 (Practice)

SRM362 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM362 (Practice) - hama_DU@TopCoderへの道

問題結果ポイントその他
250MaximizeSquaresAccepted219.66数学
500PartialSeriesOpened0.00DP+経路復元
1000CoolRectanglesOpened0.00英語読めない

SRM 362 MaximizeSquares

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

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

  • 格子状に、なるべく正方形っぽく並べるのが一番いい気がする。
    • 反例があるかも・・・
  • 念のため、長方形を作る場合を全部試す
public class MaximizeSquares {
	public int squareCount(int N) {
		int max = 0;
		for (int i = 2 ; i * i <= N ; i++) {
			int count = 0;
			int j = N / i;
			int amari = N - i * j;
			for (int a = 1 ; a < i ; a++) {
				count += (i - a) * (j - a);
			}
			for (int a = 1 ; a < amari ; a++) {
				count += (amari - a);
			}
			max = Math.max(max, count);
			
		}		
		return max;
	}
}

SRM 362 PartialSeries

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

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

  • 経路復元付きDP
    • 状態数は [使った数字の組み合わせ][直前の数字][前回上がったか下がったかそのままか]
      • 2^15 * 11 * 3
  • 経路復元ができなくて死亡。
    • 他の人のコードを見て実装を勉強する
  • 解いた。
    • 辞書順最小で経路復元する必要がある場合はメモ化再帰で書くと見通しが良い
    • 状態も単純に [使った数字の組み合わせ][前回の数字][前々回の数字] として良い
      • その方が極値判定が楽で、バグが少なく実装できる
import java.util.Arrays;

public class PartialSeries {
	int[][][] memo;
	int[][][] next;
	int[] idxmap;
	int[] seq, avl;
	int ecnt;
	int len;
	int alen;
	
	public int ext(int a, int b, int c) {
		return (((a < b) && (b > c)) || ((a > b) && (b < c))) ? 1 : 0;
	}
	
	public int dfs(int idx, int ptn, int prev1, int prev2) {
		if (idx == len) {
			return 0;
		}
		
		if (seq[idx] == -1) {
			if (memo[ptn][prev1][prev2] != Integer.MAX_VALUE) {
				return memo[ptn][prev1][prev2];
			}
			int ret = Integer.MAX_VALUE;
			int best = -1;
			int besta = -1;
			for (int a = 0 ; a < alen ; a++) {
				if ((ptn & (1<<a)) == 0) {
					int nptn = ptn | (1<<a);
					int tr = dfs(idx+1, nptn, avl[a], prev1);
					int trext = ext(avl[a], prev1, prev2);
					if (idx <= 1) {
						trext = 0;
					}
					tr += trext;
					if (ret > tr) {
						ret = tr;
						best = avl[a];
						besta = a;
					} else if (ret == tr && best > avl[a]) {
						best = avl[a];
						besta = a;
					}
				}
			}
			next[ptn][prev1][prev2] = besta; 
			memo[ptn][prev1][prev2] = ret;
			return ret;
		}
		int ret = dfs(idx+1, ptn, seq[idx], prev1);
		int tr = ext(seq[idx], prev1, prev2);
		if (idx <= 1) {
			tr = 0;
		}
		return ret + tr;
	}
	
	public int[] getFirst(int[] series, int[] available) {
		seq = series;
		avl = available;
		len = series.length;
		alen = available.length;
		ecnt = 0;
		idxmap = new int[51]; 
		for (int i = 0 ; i < len ; i++) {
			if (series[i] == -1) {
				idxmap[ecnt] = i;
				ecnt++;
			}
		}
		
		memo = new int[1<<alen][11][11];
		next = new int[1<<alen][11][11];
		for (int i = 0 ; i < (1<<alen) ; i++) {
			for (int j = 0 ; j < 11 ; j++) {
				Arrays.fill(memo[i][j], Integer.MAX_VALUE);
				Arrays.fill(next[i][j], Integer.MAX_VALUE);
			}
		}
		
		dfs(0, 0, 0, 0);
		
		
		
		int now = 0;
		int nptn = 0;
		int val = seq[0];
		int prev1 = 0;
		int prev2 = 0;
		while (now < len) {
			while (now < len && seq[now] != -1) {
				val = seq[now];
				prev2 = prev1;
				prev1 = val;
				now++;
			}
			if (now >= len) {
				break;
			}
			
			int tptn = nptn;
			if (next[nptn][prev1][prev2] == Integer.MAX_VALUE) {
			} else {
				tptn |= (1<<next[nptn][prev1][prev2]);
				seq[now] = avl[next[nptn][prev1][prev2]];
			}
			val = seq[now];
			nptn = tptn;
			prev2 = prev1;
			prev1 = val;
			now++;
		}
		System.out.println(Arrays.toString(seq));
		return seq;
	}
}

SRM363 (Practice)

SRM363 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM363 (Practice) - hama_DU@TopCoderへの道

問題結果ポイントその他
250HandsShakingAccepted233.21メモ化再帰
500MirrorNumberCompiled0.00再帰、全探索
1000PackageDeliveryUnopened0.00見てない

SRM 363 HandsShaking

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

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

  • メモ化再帰するだけ。簡単。
public class HandsShaking {
	long[] memo = new long[100];
	
	public long dfs(int n) {
		if (n <= 4) {
			return memo[n];
		}
		if (memo[n] >= 1) {
			return memo[n];
		}
		
		long ans = 0;
		int left = n - 2;
		for (int z = 0 ; z <= left ; z += 2) {
			ans += dfs(left-z) * dfs(z);
		}
		memo[n] = ans;
		return ans;
	}
	
	public long countPerfect(int n) {
		memo[0] = 1;
		memo[2] = 1;
		memo[4] = 2;
		return dfs(n);
	}
}

SRM 363 MirrorNumber

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

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

  • 方針を検討
    • DPする?
      • 先頭に2をつけたら後ろに5をつけなきゃいけない。
      • 「オーバーしたかどうか」フラグを管理するのが難しそう
    • 求めるべき数はそんなに大きくないはず。全探索でよさそう
      • 5^9 * 2 = 4Mぐらいだろ、だいじょぶだいじょぶ!
  • 実装
    • 10^18を突っ込むとTLEする
      • あれ!?
      • 文字列操作コストがそれなりに重いのかなぁ
    • やっぱりDPしなきゃダメか?
  • Editorial読むと全探索って書いてある
    • 選んだ数字を配列に入れてけばいいらしい。数字のまま処理するべし
    • 長さを決め打ちするって発想も出てこなかったなぁ
public class MirrorNumber {
	long A, B;
	int cnt;
	int[] pre = {0, 1, 8, 2, 5};
	int[] suf = {0, 1, 8, 5, 2};
	int[] digits = new int[50];
	
	public void dfs(int l, int f, int t) {
		if (f < t) {
			for (int i = (f == 0) ? 1 : 0 ; i < 5 ; i++) {
				digits[f] = pre[i];
				digits[t] = suf[i];
				dfs(l, f+1, t-1);
			}
		} else if (f == t) {
			for (int i = 0 ; i < 3 ; i++) {
				digits[f] = pre[i];
				dfs(l, f+1, t-1);
			}
		} else {
			long val = 0;
			for (int i = l ; i >= 0 ; i--) {
				val *= 10;
				val += digits[i];
			}
			if (A <= val && val <= B) {
				cnt++;
			}
		}
	}
	
	public int count(String a, String b) {
		A = Long.valueOf(a);
		B = Long.valueOf(b);
		for (int i = 0 ; i < 18 ; i++) {
			dfs(i, 0, i);
		}
		return cnt;
	}
}

SRM 363 PackageDelivery

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

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

  • 見てない

後で

  • やってみた
  • サンプル通るけどWAする
    • 想定解法と違うっぽいので、あとでやる
import java.util.Arrays;

public class PackageDelivery {

	int len;
	long[][] memo;
	long[][] calcmemo;
	long[] pos;
	long wc, fc, pc, tc;
	
	public long calc(int from, int to) {
		if (calcmemo[from][to] != Long.MAX_VALUE) {
			return calcmemo[from][to];
		}
		int packnum = to - from + 1;
		long[][] dp = new long[packnum+1][packnum+1];
		for (int p = 0 ; p <= packnum ; p++) {
			Arrays.fill(dp[p], Long.MAX_VALUE);
		}
		
		dp[0][0] = 0;
		long mincost = Long.MAX_VALUE;
		for (int p = 0 ; p <= packnum ; p++) {
			for (int done = 0 ; done <= packnum ; done++) {
				if (dp[p][done] == Long.MAX_VALUE) {
					continue;
				}
				long now = (p == 0) ? 0 : pos[from+p-1];
				long cost = dp[p][done];
				for (int i = done ; i < p ; i++) {
					cost += wc * Math.abs(now - pos[from+i]);
				}
				
				long ecost = cost;
				for (int i = p ; i < packnum ; i++) {
					ecost += wc * Math.abs(now - pos[from+i]);
				}
				if (to < len - 1) {
					ecost += fc * now;
				}
				mincost = Math.min(mincost, ecost);
				for (int go = p+1 ; go <= packnum ; go++) {
					long tcost = cost;
					tcost += pc + fc * Math.abs(now - pos[from+go-1]);
					dp[go][p] = Math.min(dp[go][p], tcost);
				}
			}
		}
		calcmemo[from][to] = mincost;
		return mincost;
	}
	
	
	public long dfs(int from, int to) {
		if (memo[from][to] != Long.MAX_VALUE) {
			return memo[from][to];
		}
		long ret = Long.MAX_VALUE;
		if (to - from + 1 <= tc) {
			ret = calc(from, to);
		}
		for (int i = from ; i <= to - 1 ; i++) {
			ret = Math.min(dfs(from, i) + dfs(i+1, to), ret);
		}
		memo[from][to] = ret;
		return ret;
	}
	
	public long minimalCost(int[] packages, int walkCost, int fuelCost, int parkingCost, int truckCapacity) {
		Arrays.sort(packages);
		len = packages.length;
		pos = new long[len];
		for (int i = 0 ; i < len ; i++) {
			pos[i] = packages[i];
		}
		memo = new long[len+1][len+1];
		calcmemo = new long[len+1][len+1];
		for (int i = 0 ; i <= len ; i++) {
			Arrays.fill(memo[i], Long.MAX_VALUE);
			Arrays.fill(calcmemo[i], Long.MAX_VALUE);
		}
		wc = walkCost;
		fc = fuelCost;
		pc = parkingCost;
		tc = truckCapacity;
		
		long walkall = 0;
		for (int i = 0 ; i < len ; i++) {
			walkall += pos[i] * walkCost;
		}
		
		return Math.min(walkall, dfs(0, len-1));
	}

}