Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-21SRM367 (Practice)

SRM 367 DeviceProgramming

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

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

  • 強烈なDP
    • 座標圧縮して適当にやればいい気がした
    • メモリの位置先頭(末尾)から (maxPacketSize - overhead) 進めた(戻した)位置を記録
      • トータルで 50 * 1000 * 2 = 100,000
    • dp[位置] = 現在位置まででパケットを区切るときの最小バイト数
      • 遷移数は高々1000(どの末尾まで考えるか)でいいはず
      • トータルの計算量は 100,000 * 1,000 = 100,000,000 ちょっと危ないか・・・?
  • 大丈夫大丈夫!
    • 暗示をかけながら提出
  • TLEする
    • やっぱり適当じゃダメか もっと考えなきゃ
  • 通した。そもそも方針が間違ってた
    • i番目からj番目まで(inclusive)を載せるコストを cost[i][j+1]として前計算
    • i番目まで載せるコストをdpで計算する

通したコード

import java.util.Arrays;
import java.util.Comparator;

public class DeviceProgramming {
	class Memory {
		long offset;
		long size;
		Memory(int o, int s) {
			offset = o;
			size = s;
		}
	}
	
	public long minBytes(int[] offset, int[] size, int maxPacketSize, int overhead) {
		int cansend = maxPacketSize - overhead;
		int len = offset.length;
		Memory[] mem = new Memory[len];
		for (int i = 0 ; i < len ; i++) {
			mem[i] = new Memory(offset[i], size[i]);
		}
		Arrays.sort(mem, new Comparator<Memory>(){
			public int compare(Memory a, Memory b) {
				return Long.signum(a.offset - b.offset);
			}
		});
		
		long[][] cost = new long[len+1][len+1];
		for (int i = 0 ; i < len ; i++) {
			for (int j = i ; j < len ; j++) {
				long from = mem[i].offset;
				long to = mem[j].offset + mem[j].size;
				long load = to - from;
				long rec = (load +  cansend - 1) / cansend;
				cost[i][j+1] = load + rec * overhead;
			}
		}
		
		long[] dp = new long[len+1];
		Arrays.fill(dp, Long.MAX_VALUE);
		dp[0] = 0;
		for (int i = 0 ; i < len ; i++) {
			for (int j = i+1 ; j <= len ; j++) {
				dp[j] = Math.min(dp[j], dp[i] + cost[i][j]);
			}
		}
		return dp[len];
	}
}

TLEするコード

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DeviceProgramming {
	class Memory {
		int offset;
		int size;
		Memory(int o, int s) {
			offset = o;
			size = s;
		}
	}
	
	class Position {
		int offset;
		int idx;
		Position(int o, int i) {
			offset = o;
			idx = i;
		}
	}
	
	
	public long minBytes(int[] offset, int[] size, int maxPacketSize, int overhead) {
		int cansend = maxPacketSize - overhead;
		int len = offset.length;
		Memory[] mem = new Memory[len];
		for (int i = 0 ; i < len ; i++) {
			mem[i] = new Memory(offset[i], size[i]);
		}
		Arrays.sort(mem, new Comparator<Memory>(){
			public int compare(Memory a, Memory b) {
				return a.offset - b.offset;
			}
		});
		
		List<Long> pos = new ArrayList<Long>();
		Set<Long> posset = new HashSet<Long>();
		Set<Long> ends = new HashSet<Long>();
		Set<Long> starts = new HashSet<Long>();
		Set<Long> sarea = new HashSet<Long>();
		Set<Long> earea = new HashSet<Long>();
		for (int i = 0 ; i < len ; i++) {
			ends.add((long)offset[i] + size[i]);
			starts.add((long)offset[i]);
		}
		
		for (int i = 0 ; i < len ; i++) {
			long from = mem[i].offset;
			long to = mem[i].offset + mem[i].size;
			for (long k = 0 ; k < cansend ; k++) {
				if (!posset.contains(from+k)) {
					if (from+k <= to) {
						posset.add(from+k);
						pos.add(from+k);
						sarea.add(from+k);
					}
				}
				if (!posset.contains(to-k)) {
					if (to-k >= from) {
						posset.add(to-k);
						pos.add(to-k);
						earea.add(to-k);
					}
				}
 			}
		}
		Collections.sort(pos);
		
		int plen = pos.size();
		long[] dp = new long[plen+1];
		Arrays.fill(dp, Long.MAX_VALUE);
		dp[0] = 0;
		for (int d = 0 ; d < plen ; d++) {
			if (dp[d] != Long.MAX_VALUE) {
				long npos = pos.get(d);
				if (ends.contains(npos) && !starts.contains(npos)) {
					dp[d+1] = Math.min(dp[d+1], dp[d]);
					continue;
				}
				
				int cnt = 0;
				for (int td = d+1 ; td < plen ; td++) {
					long topos = pos.get(td);
					long dist = topos - npos;
					long needpack = (dist + cansend - 1) / cansend;
					long sz = needpack * overhead + dist;
					dp[td] = Math.min(dp[td], dp[d] + sz);
					if (cnt >= 1000) {
						break;
					}
					cnt++;
				}
			}
		}
		return dp[plen];
	}
}