SRM340

250

与えられた数字Nをつなげていったときに最低何個つなげたらkの倍数になりますかという問題．できなかったら-1を返す．
数字をつなげるというのはNの長さをlとしたときに10^lかけて，Nを足すのと同じなのでmod kで考えていって0になるまで繰り返す．ただし，同じ数字が出てきたら巡回したので-1を返す．

500

単純なDPで解こうとするとO(2^N M^2 N)でNが15まででMが50までなので計算時間が間に合わなくなる．最適化するといけるみたいだけど．そこで許すコストを固定した時にはO(2^N N)で計算できるのを利用してコストに関して2分探索するといけるみたい．

追記 :
500をとりあえず書いてみた，O(2^N N)で書けるはずだけどメモ化をさぼったO(2^N NM)のコードでも間に合う

public class PaintingBoards {
	int bl[] , ps[];
	public double minimalTime(int[] boardLength, int[] painterSpeed) {
		bl = boardLength;
		ps = painterSpeed;
		double low = 0.0;
		double high = 500000.0;
		while(high - low >= 1.0E-9){
			double middle = low + (high - low) / 2.0;
			if(can(middle)) high = middle;
			else low = middle;
		}
		return low;
	}
	boolean can(double time){
		int dp[] = new int[1<<ps.length];
		for(int i = 0 ; i < ps.length ; i++){
			for(int j = 0 , s = 0; j < bl.length ; j++){
				s += bl[j];
				if(s  > time * ps[i])break;
				else dp[1<<i] = j + 1;
			}
		}		
		for(int k = 1 ; k < dp.length ; k++)
			for(int i = 0 ; i < ps.length ; i++)
				if((k & (1 <<i))!= 0){
					int prev = dp[k - (1<<i)];
					int res = prev;
					for(int j = prev , s = 0; j < bl.length ; j++){
						s += bl[j];
						if(s > time * ps[i])break;
						else res = j + 1;
					}
					dp[k] = Math.max(dp[k], res);
				}
		
		for(int i : dp)if(i==bl.length)return true;
		return false;
	}
}