BottomCoder SRM 379 div2

TopCoder

SRM 379 div2

points result time
250 AC 2.5m
500 AC 11.2m
900 AC 19.5m

すべて実装ゲー。全体的に問題文が難しめ。

250

N(<=50)個のファイルをダウンロードしている。速度と、その速度から割り出された残り時間が与えられるとき、すべてのファイルをダウンロードし終わる残り時間を求めよ。なお、あるファイルのダウンロードが終了したらその帯域は他のファイルのダウンロードで使われる。

前に創作しかけた問題に近い。帯域全体を考えれば良いだけ。全部の速度を足したものが回線速度なので、これで残りサイズ(速度*残り時間の和)を割れば良い。

public class DownloadingFiles {

	public double actualTime(String[] tasks) {
		int n = tasks.length;
		long sum = 0;
		long w = 0;
		for(int i = 0;i < n;i++){
			String[] sp = tasks[i].split(" ");
			sum += Integer.parseInt(sp[0])*Integer.parseInt(sp[1]);
			w += Integer.parseInt(sp[0]);
		}
		return (double)sum / (double)w;
	}

}

500

N(<=50)人の客に商品を売りつける。i番目の客はprice[i]以下の値段なら買い、商品の発送にcost[i]だけコストがかかる。儲けを最大にするような最適な値段を答えよ。ただし客が買える値段でもその客に売りつけるかどうかは自由である。

値段を決め打ち(border)して、border以上のprice[i]をもつ客で、borderよりcost[i]が小さければ売りつけることにする。そして儲けの合計が最大になるborderを採用すれば良い。
儲けを最大にするので、borderは各price[i]のどれかになる。よって全探索でも余裕。(O(N^2))

public class SellingProducts {

	public int optimalPrice(int[] price, int[] cost) {
		int n = price.length;
		int maxp = 0;
		int maxi = 0;
		for(int i = 0;i < n;i++){
			int v = price[i];
			int pr = 0;
			for(int j = 0;j < n;j++){
				if(price[j] >= v && v >= cost[j]){
					pr += v - cost[j];
				}
			}
			if(maxp < pr || (maxp == pr && maxi > price[i])){
				maxp = pr;
				maxi = price[i];
			}
		}
		return maxi;
	}

}

900

1〜N(<=6)の置換をσとする。σの各i→jについてboard[i][j](-9〜9)の積を計算する。さらに、σの強連結成分の個数が偶数だったら-1を掛ける。こうして求めた値をf(σ)とするとき、すべてのσのなかでのf(σ)の最小値と最大値を求めよ。(意訳)

置換の総数は6!以下なので、全探索でも間に合う。σの強連結成分は必ずサイクルになるので、辺をたどっていくだけで、そんな難しいアルゴリズムも必要ない。

public class TVGameWinnings {

	public int[] getMinMax(String[] board) {
		int n = board.length;
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = i;
		
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		do{
			int used = 0;
			int nc = 0;
			for(int i = 0;i < n;i++){
				if((used&(1<<i))==0){
					used |= 1<<i;
					int cur = a[i];
					while((used&(1<<cur))==0){
						used |= 1<<cur;
						cur = a[cur];
					}
					nc++;
				}
			}
			int mul = nc % 2 == 0 ? -1 : 1;
			for(int j = 0;j < n;j++){
				mul *= trans(board[j].charAt(a[j]));
			}
			min = Math.min(min, mul);
			max = Math.max(max, mul);
		}while(nextPermutation(a));
		return new int[]{min, max};
	}
	
	int trans(char c)
	{
		if(c >= '0' && c <= '9'){
			return c - '0';
		}else{
			return -(c - 'A' + 1);
		}
	}

	public static boolean nextPermutation(int[] src)
	{
		int i;
		for(i = src.length - 2;i >= 0 && src[i] > src[i+1];i--);
		if(i == -1)return false;
		int j;
		for(j = i + 1;j < src.length && src[i] < src[j];j++);
		int d = src[i]; src[i] = src[j - 1]; src[j - 1] = d;
		for(int p = i + 1, q = src.length - 1;p < q;p++,q--){
			d = src[p]; src[p] = src[q]; src[q] = d;
		}
		return true;
	}
	
}