Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-11SRM377,SRM378,SRM379 (Practice)

SRM 379 FillBox

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

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

  • 使えるCube数が無限大と仮定した時、各大きさのCubeが何個必要か求めておく
  • 大きいCubeから貪欲に使っていってOK
    • n段階小さいCubeで大きいCubeを代用するには pow(8, n)個必要
    • オーバーフローに注意する
import java.util.Arrays;

public class FillBox {
	public int minCubes(int length, int width, int height, int[] cubes) {
		int len = cubes.length;
		long[] lcubes = new long[len];
		for (int i = 0 ; i < len ; i++) {
			lcubes[i] = cubes[i];
		}
		
		long minlwh = Math.min(length, Math.min(width, height));
		long[] needpack = new long[100];
		long lwh = minlwh;
		int cnt = 0;
		while (lwh >= 1) {
			lwh /= 2;
			cnt++;
		}
		
		for (int mc = cnt - 1 ; mc >= 0 ; mc--) {
			long size = (long)Math.pow(2, mc);
			long ln = length / size;
			long wl = width / size;
			long hl = height / size;
			needpack[mc] = ln * wl * hl;
			long pw = 1;
			for (int bigger = mc + 1 ; bigger < 100 ; bigger++) {
				pw *= 8;
				if (needpack[bigger] >= 1) {
					needpack[mc] -= pw * needpack[bigger];
				}
			}
		}
		
		long used = 0;
		for (int i = cnt - 1 ; i >= 0 ; i--) {
			if (needpack[i] >= 1) {
				long needv = needpack[i] * (long)Math.pow(8, i);
				for (int u = Math.min(i, len-1) ; u >= 0 ; u--) {
					if (lcubes[u] >= 1) {
						long pu = (long)Math.pow(8, u);
						long canuse = Math.min(needv / pu, lcubes[u]);
						lcubes[u] -= canuse;
						used += canuse;
						needv -= canuse * pu;
					}
					if (needv <= 0) {
						break;
					}
				}
				if (needv >= 1) {
					return -1; 
				}
			}
		}	
		return (int)used;
	}
}

utmathutmath2012/03/26 13:34SRM378 Medium 落としておきました。

hama_DUhama_DU2012/03/26 17:27うっ、嘘解法でしたからね・・・
どんなケースで落としたのか教えていただけるとうれしいです。

utmathutmath2012/03/27 15:563552*x^25 + 730*x^20 + 886*x^15 + 68*x^10 + 160*x^5 + 62*x + 4 です。x = 4 を代入すると、4 * (10^9+9) * (10^9 +7) になり、どちらで mod をとっても 0 になってしまいます。

hama_DUhama_DU2012/03/29 16:19なるほど、ありがとうございます。
というかこんなケースよく見つけましたね・・・