kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

Bubble Sort(AOJ No.0167), Kannondou(AOJ No.0168), Blackjack(AOJ No.0169), Lunch(AOJ No.0170)

Online Judge

リポジトリ

Bubble Sort(AOJ No.0167)

a_0, a_1, \cdots , a_{n-1}が与えられたて、右から確定していくナイーブなバブルソートをしたときの反転数を答える。
制約
0 < a_i \leq 1000000
1\leq n \leq 100

アルゴリズム

nが小さいので普通にバブルソートしてもいいが、2299 -- Ultra-QuickSortの問題だと間に合わない。ソート(Sorting)で書いたマージソートを使えば O(n\log n)で反転数が求まる。
プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?にBITを使う方法が紹介されていたが、そのままだと a_iの値域だけ空間計算量とそれに応じた計算量がかかるので、少し改造してみた。

反転数 Tは、
f(i):=|\{ j|j < i, a_j > a_i \} |　と定義すると、
T=\sum_{i=0}^{n-1} f(i)である。
まず、BITを0初期化しておき、 aをソートした配列 bを作っておく。
BITは、 a_iのソート後の位置にインクリメントしていく(下の実装だと、等しい値をもつものがあればソート後の位置とは厳密には異なるが、計算結果には関係ない)。
0\leq i < nについて次の更新を行う。

  • 更新位置 pos = a_iのソート後での位置( a_iの順位)

bに対してbinarySearchを行って posを求めたが、binarySearchを使わなくても、 a_iがソート後どの位置にあるか分かるようになってればおk。
はじめはlowerBound使わないと駄目だと思い込んでいたが、よくよく考えれば同じbinarySearchを使い続ければ、同じ値を持つ要素をkeyにしたとき返ってくるインデクスは毎回同じなので全く問題なかった。

  • ans += i - tree.sum(pos)

ここで tree.sum(pos) = |\{ j|j < i, a_j <= a_i \}| なので、 i - tree.sum(pos) = f(i) = |\{ j| j < i, a_j > a_i \}|

  • tree.add(pos, 1)　更新

O(\log n)の操作を n回繰り返すので O(n\log n)

コード

import java.util.*;
public class aoj0167 {
	static final Scanner stdin = new Scanner(System.in);
	static Solver solver = Solver.MergeCount;
	public static void main(String[] args) {
		int n;
		while((n = stdin.nextInt()) != 0){
			int[] a = new int[n];
			for (int i = 0; i < n; i++) a[i] = stdin.nextInt();
			System.out.println(solver.solve(a));
		}
	}
	static enum Solver {
		BIT { @Override int solve(int[] a){
			int n = a.length;
			int[] b = new int[n]; System.arraycopy(a, 0, b, 0, n); Arrays.sort(b); //aをソートしたやつ
			FenwickTree tree = new FenwickTree(n); // all 0 で 初期化
			int ans = 0;
			for(int i = 0; i < n; ++i){
				int pos = Arrays.binarySearch(b, a[i]); //ソート後の位置(a[i]の順位)
				ans += i - tree.sum(pos); //tree.sum(pos)= |{j|j < i, a[j] <= a[i]}|
				tree.add(pos, 1);
			}
			return ans;
		}}, MergeCount { @Override int solve(int[] a){ return mergeCount(a); }
		}, BubbleSort { @Override int solve(int[] a){ return bubbleSort(a); }};
		int solve(int[] a){ return 0; }
	}
	public static int solve(int[] a){
		int n = a.length;
		int[] b = new int[n]; System.arraycopy(a, 0, b, 0, n); Arrays.sort(b); //aをソートしたやつ
		FenwickTree tree = new FenwickTree(n); // all 0 で 初期化
		int ans = 0;
		for(int i = 0; i < n; ++i){
			int pos = Arrays.binarySearch(b, a[i]); //ソート後の位置(a[i]の順位)
			ans += i - tree.sum(pos); //tree.sum(pos)= |{j|j < i, a[j] <= a[i]}|
			tree.add(pos, 1);
		}
		return ans;
	}
	public static class FenwickTree{
		private int[] x;
		public FenwickTree(int n){ init(n);}
		public final void init(int n){ x = new int[n]; Arrays.fill(x, 0); }
		public final int sum(int i){
			int ret = 0;
			//If 1 start (not 0 start), use j -= (j&-j)
			for(int j = i; j >= 0; j = ((j & (j+1)) - 1)) ret += x[j];
			return ret;
		}
		public final void add(int i, int a){
			//If 1 start (not 0 start), use j += (j&-j)
			for(int j = i; j < x.length; j |= j+1) x[j] += a;
		}
	}
	public static final int[] swap(int[] x, int i, int j){
		int tmp = x[i]; x[i] = x[j]; x[j] = tmp; return x;
	}
	public static final int bubbleSort(int a[], int fromIndex, int toIndex){
		int n = toIndex - fromIndex, count = 0;
		for (int i = fromIndex+1; i < n; ++i) 
			for (int j = fromIndex; j < n-i; j++) 
				if(a[j] > a[j+1]){ swap(a, j, j+1); count++; }
		return count;
	}
	public static final int bubbleSort(int a[]){ return bubbleSort(a, 0, a.length); }
	public static int mergeCount(int[] a, int fromIndex, int toIndex){
		int count = 0;
		int n = toIndex - fromIndex;
		if(n > 1){
			int mid = fromIndex + n/2;
			count += mergeCount(a, fromIndex, mid); count += mergeCount(a, mid, toIndex);
			int[] temp = new int[n]; System.arraycopy(a, fromIndex, temp, 0, n);
			//merge index i-> x, j-> left subsequence of x, k-> right subsequence of x
			for(int i = fromIndex, j = 0, k = n/2; i < toIndex; ++i){
				if(j == n/2)			a[i] = temp[k++];
				else if(k == n)			a[i] = temp[j++];
				else if(temp[j] <= temp[k])	a[i] = temp[j++];
				else				{a[i] = temp[k++]; count += n/2 - j; }
			}
		}
		return count;
	}
	public static final int mergeCount(int[] a){ return mergeCount(a, 0, a.length); }
}

Kannondou(AOJ No.0168)

n段の階段を、１段 or ２段 or３段登るという操作を繰り返して登る。
1日１０種類の登り方をしたとき、全種類の登り方を達成するのに何年掛かるか。
１年３６５日計算(366日で全種類の登り方ができるとき2年と答える。)
制約
1\leq n \leq N = 30

アルゴリズム

DP_0 = 1, DP_1 = 1, DP_2 = 2
DP_{i} = DP_{i-1}+DP{i-2}+DP_{i-3}
で組み合わせ数を求める。

コード

import java.util.*;
public class aoj0168 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 31, D = 10, Y = 365;
	static final int[] DP = new int[N];
	public static void main(String[] args) {
		DP[0] = 1; DP[1] = 1; DP[2] = 2;
		for(int i = 3; i < N; ++i) DP[i] = DP[i-1]+DP[i-2]+DP[i-3];
		for(int i = 0; i < N; ++i) DP[i] = ((DP[i] + D-1)/D + Y-1)/Y;
		int n;
		while((n = stdin.nextInt()) != 0) System.out.println(DP[n]);
	}
}

Blackjack(AOJ No.0169)

BJ。手札(n枚)が与えられて、最大点を求める。

  • 1は1点あるいは11点
  • 2から9までは、書かれている数の通りの点数
  • 10から13までは、10点

コード

１を１にするか１１にするかの組み合わせを考えればいいが、順番は関係ないので、 O(n)でとける。
nの最大値は問題に明記されていないから、本当なら適当に打ち切るべきだけど、通ったからいいか。

import java.util.*;
public class aoj0169 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 21;
	public static void main(String[] args) {
		while(true){
			String[] s = stdin.nextLine().split(" ");
			if(s[0].equals("0")) break;
			int one = 0, base = 0;
			for(int i = 0; i < s.length; ++i){
				int temp = Integer.parseInt(s[i]);
				if(temp == 1) one += Math.min(temp, 10);
				else base += Math.min(temp, 10);
			}
			int ans = 0;
			for(int i = 0; i <= one; ++i){
				int sum = base + i*10 + one;
				ans = Math.max(ans, (sum > N ? 0 : sum)); 
			}
			System.out.println(ans);
		}
	}
}

Lunch(AOJ No.0170)

食べ物の名前、重さ、耐久値( f , w, s)の情報が n個与えられる。
これらを重心が最小となるように並び替える。
ただし、 s_{f_i}は f_iの上に置けるものの最大重量で、下から( f_1, f_2, \cdots, f_n)と並び替えた場合
s_{f_i} \geq \sum_{k=i+1}^n w_{f_k}を満たしている必要がある。
重心 Gは、 G = \frac{\sum_{k=1}^n kw_{f_k}}{\sum_{k=1}^n w_{f_k}}
制約
1\leq n\leq 10

アルゴリズム

DFS. 上の方から累積質量を計算しながらやると早めに枝刈りできる。ただ、せいぜいn=10なら全探索しても O(n!)\rightarrow 10! = 3,628,800なので、まあ、余裕でしょう。

コード

簡単なんだが、上から０にしたか、それとも１にしたのか、あるいは下から数えていたのか混乱して時間掛かった。
nextPermutationのテストも兼ねて全探索もしてます。

import java.util.*;
public class aoj0170 {
	static final double INF = 1e10;
	static final Scanner stdin = new Scanner(System.in);
	static int[] w, s;
	static Solver solver = Solver.DFS;
	public static final double centerOfGravity(Integer[] idx){
		int n = idx.length, numerator = n*w[idx[n-1]];
		int denominator = w[idx[n-1]];
		for(int i = n-2; i >= 0; --i){
			if(s[idx[i]] < denominator) return INF;
			denominator += w[idx[i]];
			numerator += (i+1)*w[idx[i]];	
		}
		return ((double)numerator)/denominator;
	}
	public static void main(String[] args) {
		int n;
		while((n = stdin.nextInt()) != 0){
			String[] name = new String[n];
			w = new int[n]; s = new int[n];
			Integer[] idx = new Integer[n];
			for(int i = 0; i < n; ++i){
				name[i] = stdin.next(); w[i] = stdin.nextInt(); s[i] = stdin.nextInt();
				idx[i] = i;
			}
			for(int i: solver.solve(idx)) System.out.println(name[i]);
		}
	}
	static enum Solver {
		NextPermutation { @Override Integer[] solve(Integer[] idx){
			int n = idx.length;
			Integer[] ans = new Integer[n];
			double g = INF;
			do{
				double tempg = centerOfGravity(idx);
				if(g > tempg){ System.arraycopy(idx, 0, ans, 0, n); g = tempg; }
			}while(nextPermutation(idx));
			return ans;
		}}, DFS { @Override Integer[] solve(Integer[] idx){
			int n = idx.length;
			answer = new Integer[n]; tempa = new Integer[n]; used = new boolean[n]; g = INF; Arrays.fill(used, false);
			DFS(0, 0, 0);
			return answer;
		}};
		Integer[] solve(Integer[] idx){ return new Integer[]{}; }
	}
	static Integer[] answer, tempa; static boolean[] used; static double g;
	public static void DFS(int d, int numerator, int denominator){
		int n = answer.length;
		if(d == n){
			double tempg = (double)numerator/denominator;
			if(g > tempg){ g = tempg; System.arraycopy(tempa, 0, answer, 0, n); }
			return;
		}
		for(int i = 0; i < n; ++i){
			if(used[i] || s[i] < denominator) continue;
			used[i] = true; tempa[n-d-1] = i;
			DFS(d+1, numerator+(n-d-1)*w[i], denominator+w[i]);
			used[i] = false;
		}
	}
	public static <T> boolean nextPermutation(T[] a, int fromIndex, int toIndex, final Comparator<? super T> c){
		for (int i = toIndex - 1; i > fromIndex; --i) {
			if (c.compare(a[i-1], a[i]) < 0) { //[i,toIndex) is arranged in descending order.
				int swapIndex = toIndex;
				while (c.compare(a[i-1], a[--swapIndex]) >= 0);
				//int swapIndex = lowerBound(a, i, toIndex, a[i - 1], new Comparator<T>(){ @Override public int compare(T o1, T o2) { return -(c.compare(o1, o2)); }}) - 1;
				swap(a, i-1, swapIndex);
				reverse(a, i, toIndex);
				return true;
			}
		}
		reverse(a, fromIndex, toIndex); //turn back
		return false;
	}
	public static <T extends Comparable <? super T>> boolean nextPermutation(T[] a){
		return nextPermutation(a, 0, a.length, new Comparator<T>(){
			@Override public int compare(T o1, T o2) { return o1.compareTo(o2); }
		});
	}
	public static Object[] swap(Object[] a, int i, int j){	
		Object tmp = a[i]; a[i] = a[j]; a[j] = tmp; return a;
	}
	public static void reverse(Object[] a, int fromIndex, int toIndex) {
		for(int n = toIndex - fromIndex, mid = n>>1, i = 0, j = n-1; i < mid; ++i, --j)
			swap(a, fromIndex+i, fromIndex+j); 
	}
}