梱包できるかな？ [ AtCoder Regular Contest 013 A ]

atcoder.jp

問題

N*M*L の大きさの箱に、P*Q*R の大きさの荷物はどれだけ入るか。
荷物はどの向きで入れてもよい。

考察

以前作成した nextPermutation の使いどころがやってきました。

・Javaでnext_permutationメソッドを作ってみる - 文系プログラマーのプログラミング備忘録

nextPermutation メソッドで荷物の向きのパターンを全列挙し、入れられる数の最大値を出力します。

コード

void solve (FastScanner in, PrintWriter out) {

	int[] a = in.nextIntArray(3), b = in.nextIntArray(3);
	ArrayList<Character> list = new ArrayList<>(Arrays.asList('0', '1', '2'));
	
	int max = Integer.MIN_VALUE;
	while (list.size() != 0) {
		max = Math.max(max,(a[0]/b[list.get(0)-'0'])*(a[1]/b[list.get(1)-'0'])*(a[2]/b[list.get(2)-'0']));
		list = nextPermutation(list);
	}

	out.println(max);

}

static ArrayList<Character> nextPermutation (ArrayList<Character> list) {
	int pivotPos = -1;
	char pivot = 0;

	for (int i=list.size()-2; i>=0; i--) {
		if (list.get(i) < list.get(i+1)) {
			pivotPos = i;
			pivot = list.get(i);
			break;
		}
	}

	if (pivotPos==-1 && pivot==0) {
		list.clear();
		return list;
	}

	int L = pivotPos+1, R = list.size()-1;
	int minPos = -1;
	char min = Character.MAX_VALUE;
	for (int i=R; i>=L; i--) {
		if (pivot < list.get(i)) {
			if (list.get(i) < min) {
				min = list.get(i);
				minPos = i;
			}
		}
	}

	Collections.swap(list, pivotPos, minPos);
	Collections.sort(list.subList(L, R+1));

	return list;

}

nextPermutation メソッドはあれから少し改良して、順列パターンを String ではなく ArrayList で管理することにしました。そのため、辞書順最大の順列を超えた場合には、"Final" ではなく 大きさ0のリスト を返すようにしています。