kanetaiの二次記憶装置

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

Russian Dolls(AOJ No.0157), Collatz's Problem(AOJ No.0158), The Best Body(AOJ No.0159), Delivery Fee(AOJ No.0160)

Online Judge

リポジトリ

Russian Dolls(AOJ No.0157)

マトリョーシカのデータ系列系列 x_k = (r_k,h_k)が与えられる。
もし, h_i < h_j \wedge r_i < r_jならマトリョーシカ iをマトリョーシカ jの中に入れることができる。
最大何個のマトリョーシカからなるマトリョーシカができるかを答える。
制約
2 \leq k \leq 200
0 < h_i, h_j < 1,000

アルゴリズム1

hかrに優先度をつけてソートして h_i < h_j \wedge r_i < r_jとなるような最長増加部分列の長さを求めればいい。
x_i < x_j \equiv h_i < h_j \wedge r_i < r_j と定義しても、その否定が x_i \geq x_jとはならないので、2分探索せずに、素直に O(n^2)のDPで解いた方がいいと思う。

アルゴリズム2

G(V=\{k\} , E = \{(i,j) | h_i < h_j \wedge r_i < r_j\wedge i,j \in V\} )のようなグラフを考えると、
G(V,E)は非循環グラフ(directed acyclic graph;DAG)となるので、その最大経路長+1を求めれば良いとも考えられる。
最大経路長は、辺の重みを-1として最短経路を求めて、絶対値をとれば良い。負辺を含むので、Bellman-Ford, Floyd-Warshall, Jhonson's algrithmあたりを使う。計算量はアルゴリズム1のほうが小さいはず。

コード

import java.util.*;
public class aoj0157 {
	static final Scanner stdin = new Scanner(System.in);
	static final int INF = Integer.MAX_VALUE/2;
	static class T implements Comparable<T>{
		int h, r;
		T(int h, int r){ this.h = h; this.r = r; }
		T(T t){ h = t.h; r = t.r; }
		@Override public int compareTo(T o) { return (h != o.h ? h - o.h : r - o.r); }
		public final boolean less(T o){ return r < o.r && h < o.h; }
	}
	static Solver solver = Solver.LIS;
	public static void main(String[] args) {
		int n;
		while((n = stdin.nextInt()) != 0){
			List<Integer> h = new ArrayList<Integer>(), r = new ArrayList<Integer>();
			while(n-- > 0){ h.add(stdin.nextInt()); r.add(stdin.nextInt()); }
			n = stdin.nextInt();
			while(n-- > 0){ h.add(stdin.nextInt()); r.add(stdin.nextInt()); }
			System.out.println(solver.solve(h,r));
		}
	}
	static enum Solver {
		LIS { @Override public int solve(List<Integer> h, List<Integer> r){
			int n = h.size();
			T[] x = new T[n];
			for(int i = 0; i < n; ++i) x[i] = new T(h.get(i), r.get(i));
			Arrays.sort(x);
			return _LIS(x).size();
		}}, FloydWarshall { @Override public int solve(List<Integer> h, List<Integer> r){
			initGraph(h,r);
			APSPResult res = FloydWarshall(G);
			for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) ans = Math.min(ans, res.getDist(i, j));
			return 1-ans;
		}}, Johnson { @Override public int solve(List<Integer> h, List<Integer> r){
			initGraph(h,r);
			APSPResult res = Johnson(list);
			for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) ans = Math.min(ans, res.getDist(i, j));
			return 1-ans;
		}}, BellmanFord { @Override public int solve(List<Integer> h, List<Integer> r){
			initGraph(h,r);
			for(int i = 0; i < n; ++i){
				SSSPResult res = BellmanFord(list, i);
				for(int j = 0; j < n; ++j) ans = Math.min(ans, res.getDist(j));
			}
			return 1-ans;
		}};
		static private int n, G[][], ans;
		static private List<List<Edge>> list;
		public int solve(List<Integer> h, List<Integer> r){ return 0; }
		static private void initGraph(List<Integer> h, List<Integer> r){
			n = h.size();
			G = new int[n][n]; //adjacency matrix
			for(int i = 0; i < n; ++i)
				for(int j = 0; j < n; ++j)
					G[i][j] = (h.get(i) < h.get(j) && r.get(i) < r.get(j) ? -1 : INF);
			ans = INF;
			list = convertToAdjacencyList(G);
		}
	}
	public static List<T> _LIS(T[] x, int begin, int end){
		int n = end - begin;
		int[] DP = new int[n]; Arrays.fill(DP, 1);
		int[] prev = new int[n]; Arrays.fill(prev, -1);
		int lidx = 0;
		for(int i = 1; i < n; ++i){
			for(int j = 0; j < i; ++j)
				if(x[begin+j].less(x[begin+i]) && DP[i] < DP[j] + 1){ DP[i] = DP[j] + 1; prev[i] = j; }
			if(DP[lidx] < DP[i]) lidx = i;
		}
		LinkedList<T> lis = new LinkedList<T>();
		for(int i = lidx; i >= 0; i = prev[i]) lis.addFirst(new T(x[begin+i]));
		return lis;
	}
	public static List<T> _LIS(T[] x){ return _LIS(x, 0, x.length); }
	public static List<List<Edge>> convertToAdjacencyList(int[][] G){
		int n = G.length;
		List<List<Edge>> list = new ArrayList<List<Edge>>(n);
		for(int i = 0; i < n; ++i){
			list.add(new ArrayList<Edge>());
			for(int j = 0; j < n; ++j) if(G[i][j] < INF) list.get(i).add(new Edge(i, j, G[i][j]));
		}
		return list;
	}
	@SuppressWarnings("unused") public static class APSPResult{
		private int[][] dist; // dist[d]:= shortest path to d
		private int[][] prev; // back pointers
		private boolean hasNegativeCycle;
		public APSPResult(int[][] dist, int[][] prev, boolean hasNegativeCycle){ set(dist, prev, hasNegativeCycle); }
		final private void set(int[][] dist, int[][] prev, boolean hasNegativeCycle){ this.dist = dist; this.prev = prev; this.hasNegativeCycle = hasNegativeCycle; }
		final public int getDist(int i, int j){ return dist[i][j]; }
	}
	public static class Edge implements Comparable<Edge>{
		protected int s; //source node		
		protected int d; //destination node
		protected int w; //edge weight
		Edge(int s, int d, int w){ set(s, d, w); }
		Edge(Edge o){ set(o.s, o.d, o.w); }
		public final void set(int s, int d, int w){ this.s = s; this.d = d; this.w = w; }
		@Override public int compareTo(Edge o) { return w < o.w ? -1 : w == o.w ? 0 : 1; }
	}
	public static APSPResult FloydWarshall(int[][] G){
		int n = G.length;
		int[][] prev = new int[n][n], dist = new int[n][n];
		for(int i = 0; i < n; ++i){
			System.arraycopy(G[i], 0, dist[i], 0, n);
			dist[i][i] = 0;
			for(int j = 0; j < n; ++j) prev[i][j] = (G[i][j] != INF ? i : -1);
		}
		for(int k = 0; k < n; ++k){
			for(int i = 0; i < n; ++i){
				if(dist[i][k] >= INF) continue;
				for(int j = 0; j < n; ++j){
					int newDist = dist[i][k] + dist[k][j];
					if(dist[i][j] > newDist){
						dist[i][j] = newDist;
						prev[i][j] = prev[k][j];
					}
				}
			}
		}
		boolean hasNegativeCycle = false;
		for(int i = 0; i < n; ++i) if(dist[i][i] < 0){ hasNegativeCycle = true; break; }
		return new APSPResult(dist, prev, hasNegativeCycle);
	}
	public static APSPResult Johnson(List<List<Edge>> list){
		int n = list.size();
		int[] h = new int[n]; Arrays.fill(h, 0);
		//Via Bellman-Ford, detect negative cycle and bias(w'(i,j) = w(i,j) + h(i) - h(j))
		boolean hasNegativeCycle = false, updated = true;
		for(int k = 1; k <= n && updated; ++k){
			hasNegativeCycle = (k==n);
			updated = false;
			for(int i = 0; i < n; ++i){
				for(Edge e: list.get(i)){
					int newDist = h[e.s] + e.w;
					if(h[e.d] > newDist){
						h[e.d] = newDist;
						updated = true;
						if(hasNegativeCycle) return new APSPResult(null, null, true);
					}
				}
			}
		}
		//Dijkstra
		int[][] dist = new int[n][n], prev = new int[n][n];
		for(int i = 0; i < n; ++i){ Arrays.fill(dist[i], INF); Arrays.fill(prev[i], -1); }
		for(int s = 0; s < n; ++s){
			PriorityQueue<Edge> q = new PriorityQueue<Edge>(n*n);
			dist[s][s] = 0;
			q.add(new Edge(-1, s, 0));
			while(!q.isEmpty()){
				Edge p = q.poll();
				int v = p.d;
				if(prev[s][v] != -1) continue;
				prev[s][v] = p.s;
				for(final Edge u: list.get(v)){
					int newDist = dist[s][v] + u.w + (h[u.s] - h[u.d]); //h[u.s] - h[u.d]: bias
					if(dist[s][u.d] > newDist){
						dist[s][u.d] = newDist;
						q.add(new Edge(u.s, u.d, dist[s][u.d]));
					}
				}
			}
			for(int d = 0; d < n; ++d) dist[s][d] -= (h[s] - h[d]); //convert into non-biased distances.
		}
		return new APSPResult(dist, prev, true);
	}
	@SuppressWarnings("unused") public static class SSSPResult{
		private int[] dist; // dist[d]:= shortest path to d
		private int[] prev; // back pointers
		private boolean hasNegativeCycle;
		public SSSPResult(int[] dist, int[] prev, boolean hasNegativeCycle){ set(dist, prev, hasNegativeCycle); }
		final private void set(int[] dist, int[] prev, boolean hasNegativeCycle){ this.dist = dist; this.prev = prev; this.hasNegativeCycle = hasNegativeCycle; }
		final public int getDist(int i){ return dist[i]; }
	}
	public static SSSPResult BellmanFord(List<List<Edge>> list, int s) {
		int n = list.size();
		int[] dist = new int[n]; Arrays.fill(dist, INF);
		int[] prev = new int[n]; Arrays.fill(prev, -1);
		boolean hasNegativeCycle = false, updated = true;
		dist[s] = 0;

		for(int k = 1; k <= n && updated; ++k){
			hasNegativeCycle = (k==n);
			updated = false;
			for(int i = 0; i < n; ++i){
				for(final Edge e: list.get(i)){
					int newDist = dist[e.s] + e.w;
					if(dist[e.d] > newDist){
						dist[e.d] = (hasNegativeCycle ? -INF : newDist);
						prev[e.d] = e.s;
						updated = true;
					}
				}
			}
		}
		return new SSSPResult(dist, prev, hasNegativeCycle);
	}
}

Collatz's Problem(AOJ No.0158)

コラッツの問題 - Wikipedia

  • f(x)=\left\{ \begin{array}{lr} x/2 & x\equiv 0 \\ 3x+1 & x\equiv 1 \end{array} \right. \pmod{2}
  • a_i = \left\{ \begin{array}{lr} n & (i=0) \\ f(a_{i-1}) & (i > 0) \end{array} \right.
  • \forall n \in \mathbb{N} > 0, \exists i \in \mathbb{N}:a_0 = n\Rightarrow a_i = 1

初期値 a_0が与えられたとき a_k = 1となる最も小さい kを求める。
ただし、 0 \leq k \leq 1,000,000となる入力が保証されている。

コード

作業ゲー

import java.util.*;
public class aoj0158 {
	static final Scanner stdin = new Scanner(System.in);
	public static int operate(int n){ return (n&1) == 0 ? n/2 : 3*n+1; }
	public static void main(String[] args) {
		int n;
		while((n = stdin.nextInt()) != 0){
			int ans;
			for(ans = 0; n != 1; ++ans) n = operate(n);
			System.out.println(ans);
		}
	}
}

The Best Body(AOJ No.0159)

n個のデータ系列(id, 体重w(kg), 身長h(cm))が与えられて、
BMI = 体重(kg) / (身長(m))2　が基準値22に一番近いデータのidを答える。
一番近いデータが複数ある場合はidが小さい方を答える。
制約
0 < n \leq 1000000
1 \leq w,h \leq 200

コード

なんでプログラミングの課題とかって、BMIを求めるのが多いの?

import java.util.*;
public class aoj0159 {
	static final Scanner stdin = new Scanner(System.in);
	static final double STANDARD = 22;
	static class T implements Comparable<T>{
		int id;
		double diffBMI;
		T(int id, int h, int w){ this.id = id; diffBMI = Math.abs(STANDARD - w/Math.pow(h/100.0, 2)); }
		@Override public int compareTo(T o) { return (diffBMI == o.diffBMI) ? id - o.id : (diffBMI > o.diffBMI ? 1 : -1); }
	}
	public static void main(String[] args) {
		int n;
		while((n = stdin.nextInt()) != 0){
			T[] a = new T[n];
			for (int i = 0; i < a.length; i++) a[i] = new T(stdin.nextInt(), stdin.nextInt(), stdin.nextInt());
			Arrays.sort(a);
			System.out.println(a[0].id);
		}
	}
}

Delivery Fee(AOJ No.0160)

荷物のデータ系列( x_i, y_i, h_i, w_i)が与えられる。
荷物iの大きさ= x_i +y_i +h_i

A サイズ B サイズ C サイズ D サイズ E サイズ F サイズ
大きさ 60cm以内 80cm以内 100cm以内 120cm以内 140cm以内 160cm以内
重さ 2kg以内 5kg以内 10kg以内 15kg以内 20kg以内 25kg以内
料金 600円 800円 1000円 1200円 1400円 1600円

Fサイズより大きいものは対象外とし料金の総計に含めない。
荷物データがn個与えられたとき料金総計を求める。
制約
1\leq i \leq n
1\leq x,y,h,w \leq 1,000,000

import java.util.*;
public class aoj0160 {
	static final Scanner stdin = new Scanner(System.in);
	static final int INF = Integer.MAX_VALUE;
	static final int size[] = {60, 80, 100, 120, 140, 160, INF};
	static final int weight[] = {2, 5, 10, 15, 20, 25, INF};
	static final int fee[] = {600, 800, 1000, 1200, 1400, 1600, 0};
	static final int N = size.length;
	static final int calc(int x, int y, int h, int w){
		int s = x + y + h;
		for(int i = 0; i < N; ++i) if(s <= size[i] && w <= weight[i]) return fee[i];
		return 0;
	}
	public static void main(String[] args) {
		int n;
		while((n = stdin.nextInt()) != 0){
			long ans = 0;
			for (int i = 0; i < n; i++)
				ans += calc(stdin.nextInt(), stdin.nextInt(), stdin.nextInt(), stdin.nextInt());
			System.out.println(ans);
		}
	}
}