AOJ1261 Mobile Computing - nanikakaのAOJ航海日誌

概要

モビールというものは以下のように再帰的に定義される。
　1つの石をヒモで吊り下げたもの
　長さ1の棒の両端にモビールを吊り下げたもので、棒の重心の位置にヒモをつけて吊り下げられる
今石がS個あり、それぞれの重さはwiである。これらの石を全て使ってモビールを作るとき、そのモビールの横幅を幅R未満の範囲で最大化せよ。モビール同士が重なってしまうような構築の仕方をしても構わない。石の横幅は無視してよい。
1 <= S <= 6
1 <= wi <= 1000
0.0 < r < 10.0

解法

棒を節点、石を葉とする2分木をモビールと考えることができます。つまり、葉がS個の2分木を全て列挙し、その葉に置く石を全通り試せば答えが出ます。
葉がS個の2分木をどう列挙したか説明します。
文字列で2分木を表現し、それを構文解析してモビールを得るという方法を取りました。2分木は
Exp = (Exp,Exp) | Num
Num = '0'〜'9'
というBNFで表現できます。葉が1〜6個の2分木をこの文字列で列挙、生成します。葉が6個のときでも木は40通りくらいしかありません。そして、石の置き方は6!通りまでなので40*6! ≒ 3000 で、計算時間は大したことはないです。
生成する文字列ではNumに相当する部分を'?'にしておいて、順列を生成したのち石の番号に置き換えています。
あとは、再帰的にモビールのノードを訪問して、石が置かれているx座標の最小値と最大値を調べていきます。

※2分木の根ノードの左側に使う石の集合と、右側に使う石の集合を決めて、左にはみ出す分＋右にはみ出す分＋1がモビールの横幅になるとは限らないです。棒の重なりが許されているので、左に吊り下げたモビールの左端より右に吊り下げたモビールの左端が左にくることがあるからです。自分はまんまとこれで引っ掛かっていました。

ソース

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

//Mobile Computing
public class AOJ1261 {

	double r, best;
	int n;
	int[] ws, w;
	Set<String>[] trees;
	
	class M{
		double x;
		boolean leaf;
		int w;
		M left, right;
		public M(double x, boolean leaf, int w) {
			this.x = x;
			this.leaf = leaf;
			this.w = w;
			left = right = null;
		}
		int get(){
			if(leaf)return w;
			return left.get()+right.get();
		}
		void val(){
			if(leaf){
				min = Math.min(min, x); max = Math.max(max, x); return;
			}
			int w1 = left.get(), w2 = right.get();
			double a = w2*1.0/(w1+w2);
			left.x = x-a;
			right.x = x+1-a;
			left.val();
			right.val();
		}
	}
	
	double min, max;
	boolean[] used;
	int[] order;
	void dfs(int k){
		if(k==n){
			for(String t:trees[n]){
				s = (t+"$").toCharArray();
				id = 0;
				int a = 0;
				//orderに石を置く順番が入っているので'?'を石の番号に置き換える
				for(int i=0;i<s.length;i++){
					if(s[i]=='?'){
						s[i] = (char)(order[a++]+'0');
					}
				}
				//構文解析してモビールを得る
				M root = exp();
				min = max = 0;
				if(!root.leaf){
					root.x = 0;
					root.val();
				}
				double res = max-min;
				if(res<r)best = Math.max(best, res);
				root.val();
			}
			return;
		}
		for(int i=0;i<n;i++){
			if(used[i])continue;
			used[i]=true;
			order[k] = i;
			dfs(k+1);
			used[i]=false;
		}
	}
	
	char[] s;
	int id;
	char get(){
		return s[id++];
	}
	M exp(){
		char ch = get();
		if(ch=='('){
			M res = new M(0, false, 0);
			res.left = exp();
			get();
			res.right = exp();
			get();
			return res;
		}
		M res = new M(0, true, ws[ch-'0']);
		return res;
	}
	
	@SuppressWarnings("unchecked")
	void run(){
		//文字列で木を表現
		trees = new Set[7];
		for(int i=1;i<=6;i++)trees[i] = new HashSet<String>();
		trees[1].add("?");
		for(int i=2;i<=6;i++){
			for(int j=1;j<i;j++){
				for(String left:trees[j])for(String right:trees[i-j])trees[i].add("("+left+","+right+")");
			}
		}
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		while(T--!=0){
			r = sc.nextDouble(); n = sc.nextInt();
			ws = new int[n];
			for(int i=0;i<n;i++)ws[i]=sc.nextInt();
			w = new int[1<<n];
			for(int i=0;i<1<<n;i++){
				int s = 0;
				for(int j=0;j<n;j++)if(((i>>j)&1)>0)s+=ws[n-1-j];
				w[i] = s;
			}
			best = -1;
			used = new boolean[n];
			order = new int[n];
			dfs(0);
			System.out.printf("%.8f\n", best);
		}
	}

	public static void main(String[] args) {
		new AOJ1261().run();
	}
}