Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-21SRM367 (Practice)

0完。

問題結果ポイントその他
250ObtainingDigitKWA0.00陰湿なコーナーケース
500DeviceProgrammingTLE0.00DP
1000WSNParentsAssignmentUnopened0.00見てない

SRM 367 ObtainingDigitK

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

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

  • 方針を検討
    • 一番下の桁だけ見ればいいんじゃないの
    • 書いてサンプル合った
  • いや、待てよ
    • 例えば "15", 2 のとき、最適は 5 を足して十の位を 2 にすべき
    • 危ない危ない。繰り上がりを考慮したコードに書き換える。
  • WA
    • "99999", 1 で死んでた
    • そうか、桁がひとつ増える場合を考慮してなかった
    • 先頭に '0' を付加したら通った
  • 他の人のコード見る
    • みんなBigIntegerでやってる・・・
      • そもそも求める数は高々9だよね。
      • 1〜9までの数字を足して k が含まれてるかどうか見ればいい
    • ライブラリゲーかよ、くそっ
public class ObtainingDigitK {
	public int minNumberToAdd(String originalNumber, int k) {
		originalNumber = '0' + originalNumber; 
		int len = originalNumber.length();
		int min = 99;
		for (int i = len-1 ; i >= 1 ; i--) {
			if (originalNumber.charAt(i) - '0' == k) {
				return 0;
			}
		}
		int c = (k - (originalNumber.charAt(len-1) - '0'));
		min = Math.min(min, (c < 0) ? c + 10 : c);
		
		for (int i = 0 ; i < len ; i++) {
			int d = originalNumber.charAt(i) - '0';
			if ((d == 9 && k == 0) || (k - d == 1)) {
				int nadd = 0;
				for (int j = i+1 ; j < len ; j++) {
					int e = originalNumber.charAt(j) - '0';
					if (e == 9) {
						if (len - 1 - j == 0) {
							min = Math.min(min, 1);
						}
						continue;
					} else {
						if (len - 1 - j >= 1) {
							break;
						} else {
							nadd = 10 - e;
							min = Math.min(nadd, min);
						}
					}
				}
			}
		}
		return min;
	}
}

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];
	}
}