BottomCoder SRM 389 div2

TopCoder

SRM 389 div2

points result time
250 AC 2.5m
500 AC 5.5m
1000 AC 23.5m

あれ・・あっさり・・
全問実装ゲー

250

容量maxWeight(<=10^5)の箱に重さweights[i](0<=||<=50)の本をi昇順に詰めていく。必要な箱の個数を求めよ。

この間順序自由の問題がhardで出たナップサック。だが、ここでは順序が決められているので超簡単。本の数が0と言う場合もあることに注意。

import java.util.Arrays;

public class BoxesOfBooks {

	public int boxes(int[] weights, int maxWeight) {
		if(weights.length == 0)return 0;
		int cur = 0;
		int box = 1;
		for(int i = 0;i < weights.length;i++){
			if(cur + weights[i] > maxWeight){
				cur = 0;
				box++;
			}
			cur += weights[i];
		}
		
		return box;
	}

	void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

500

1/bは次の無限級数で近似できる。
1/b=1/(t-c)=c^0/t^1+c^1/t^2+…
tはb以上の最小の2の累乗とする。この右辺のterms項までの和をとってa/bの近似を求めよ。

式が与えられているのでまさにその通りにやるだけ。下手にt^kを計算しようとかしなければ何も問題はない。

import java.util.Arrays;

public class ApproximateDivision {

	public double quotient(int a, int b, int terms) {
		int t = Integer.highestOneBit(b);
		if(t < b)t *= 2;
		double ret = 0;
		int c = t-b;
		double mul = (double)a / t;
		for(int i = 0;i < terms;i++){
			ret += mul;
			mul *= (double)c / (double)t;
		}
		return ret;
	}

	void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

1000

N(<=6)本の弦があるギターでM(<=N)個の音を同時に弾く。どの弦も必ずどれかの音を弾かなければならず、M個の音のどれも欠けてはならない。弦を抑えるときの難しさを、一番高い位置から一番低い位置をひいたもの+1とする。開放弦でいいときは計算に加味しない。すべて開放弦でいいときは0とする。ギターの開放弦のコードと弾くべき音のコードが与えられたとき、難しさの最小値を求めよ。ただしkオクターブ違う音はすべて同じ音とみなす。

Nが小さすぎるので全探索でOK. M^Nだけまわして、全パターンを列挙し、抑えるべき位置の最小値とそれに12足したものを再帰でみていく。
これでO(6^6*(6+2^6)). 実質O(6^6*6+6!*2^6)で余裕で終わる。

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class GuitarChords {
	int[] ss;
	int[] cc;
	int m, n;
	
	public int stretch(String[] strings, String[] chord) {
		Map<String, Integer> map = new HashMap<String, Integer>();
		String[] T = {"A", "A#", "B", "C", "C#", "D", "D#", "E", "F", "F#", "G", "G#"};
		for(int i = 0;i < T.length;i++){
			map.put(T[i], i);
		}
		
		n = strings.length;
		m = chord.length;
		cc = new int[m];
		ss = new int[n];
		for(int i = 0;i < m;i++)cc[i] = map.get(chord[i]);
		for(int i = 0;i < n;i++)ss[i] = map.get(strings[i]);
		int[] ord = new int[n];
		for(int i = 0;i < n;i++)ord[i] = 0;
		do{
			int used = 0;
			for(int u : ord)used |= 1<<u;
			if(used != (1<<m)-1)continue;
			rec(ord, 0, 99, 0);
		}while(inc(ord, m));
		
		return gmin;
	}
	
	int gmin = 999;
	
	void rec(int[] ord, int pos, int min, int max)
	{
		if(pos == n){
			if(max - min < 0){
				gmin = 0;
			}else{
				gmin = Math.min(gmin, max - min + 1);
			}
		}else{
			for(int i = (cc[ord[pos]] - ss[pos] + 12)%12;i <= 24;i+=12){
				if(i == 0){
					rec(ord, pos+1, min, Math.max(max, i));
				}else{
					rec(ord, pos+1, Math.min(min, i), Math.max(max, i));
				}
			}
		}
	}

	public static boolean inc(int[] a, int base)
	{
		int n = a.length;
		int i;
		for(i = n - 1;i >= 0 && a[i] == base - 1;i--);
		if(i == -1)return false;
		
		a[i]++;
		Arrays.fill(a, i + 1, n, 0);
		return true;
	}
	
	void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}