kanetaiの二次記憶装置

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

Stellar Performance of the Debunkey Family(AOJ No.0180), Persistence(AOJ No.0181), Beaker(AOJ No.0182), Black-and-White(AOJ No.0183), Tsuruga Castle(AOJ No.0184), Goldbach's Conjecture II(AOJ No.0185), Aizu Chicken(AOJ No.0186), Stoning Fort(AOJ No.0187),

Online Judge

リポジトリ

Stellar Performance of the Debunkey Family(AOJ No.0180)

要するにMSTの総コストを求める。

コード

前作ったライブラリ使っただけ、Prim法。

import java.util.*;
public class aoj0180 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(true){
			int n = stdin.nextInt(), m = stdin.nextInt();
			if((n|m) == 0) break;
			Map<Integer, Integer> name = new HashMap<Integer, Integer>(n<<1);
			int id = 0;
			List<List<Edge>> list = new ArrayList<List<Edge>>(n);
			for(int i = 0; i < n; ++i) list.add(new ArrayList<Edge>());
			for(int i = 0; i < m; ++i){
				int a = stdin.nextInt(), b = stdin.nextInt(), cost = stdin.nextInt();
				if(!name.containsKey(a)) name.put(a, id++);
				if(!name.containsKey(b)) name.put(b, id++);
				int aid = name.get(a), bid = name.get(b);
				list.get(aid).add(new Edge(aid, bid, cost));
				list.get(bid).add(new Edge(bid, aid, cost));
			}
			System.out.println(Prim(list).getTotalCost());
		}
	}
	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 class MSTResult{
		private int totalCost;
		private List<Edge> edgeList;
		public MSTResult(int totalCost, List<Edge> edgeList){ this.totalCost = totalCost; this.edgeList = edgeList; }
		public final int getTotalCost(){ return totalCost; }
		public final List<Edge> getEdgeList(){ return edgeList; }
	}
	public static MSTResult Prim(List<List<Edge>> adjList, int s) {
		int n = adjList.size(), totalCost = 0;
		List<Edge> T = new LinkedList<Edge>();
		boolean[] visited = new boolean[n];

		PriorityQueue<Edge> q = new PriorityQueue<Edge>();
		q.add( new Edge(-1, s, 0) );
		while(!q.isEmpty()){
			Edge e = q.poll();
			if(visited[e.d]) continue;
			T.add(e);
			totalCost += e.w;
			visited[e.d] = true;
			for(Edge f: adjList.get(e.d)) if(!visited[f.d]) q.add(f);
		}
		return new MSTResult(totalCost, T);
	}
	public static MSTResult Prim(List<List<Edge>> list){ return Prim(list, 0); }
}

Persistence(AOJ No.0181)

本棚の段数mと本1〜本nの幅 w_iがそれぞれ与えられる。１からnを順番に並べて置くとき、必要最低限の幅を求める。
制約
1 \leq w_i \leq 1000000
1 \leq m \leq 20
1 \leq n \leq 100
本棚の幅は x_{max} = 1,500,000 を超えない

アルゴリズム

ちょい難かったが2分探索の応用で解けた。解空間が [1, x_{max}] に限定されているのがみそ。
解xを2分探索(lowerBound)で求める。
2分探索をする際の比較関数f(x')は、ある幅x'のとき、本棚に順番に置けるかどうかを返す関数 O(n)。
コレを使って、f(x')=trueとなる最低のx'を求める。全体の計算量は O(n\log x_{max})\rightarrow 100\log 1,500,000 \approx 10,000,000

コード

import java.util.*;
public class aoj0181 {
	static final Scanner stdin = new Scanner(System.in);
	static final int MAX = 1500000;
	static int m, n;
	static int[] a;
	public static void main(String[] args) {
		while(true){
			m = stdin.nextInt(); n = stdin.nextInt();
			if((m|n) == 0) break;
			a = new int[n];
			for(int i = 0; i < n; ++i) a[i] = stdin.nextInt();
			System.out.println(lowerBound());
		}
	}
	public static boolean func(int v){
		int c = 0, d = 1;
		for(int i = 0; i < n; ++i){
			if((c+=a[i]) > v){
				if((c = a[i]) > v) return false;
				if(++d > m) return false;
			}
		}
		return true;
	}
	public static int lowerBound(){
		int lb = 0, ub = MAX;
		//解の存在範囲が１より大きい間、反復
		while(ub - lb > 1){
			int mid = (lb + ub) / 2;
			if( func(mid) ) 	//midが条件を満たせば、解の存在範囲は(lb,mid]
				ub = mid;
			else		//midが条件を満たさなければ、解の存在範囲は(mid,ub]
				lb = mid;
		}
		return ub; 		//(lb, ub], ub = lb + 1 → [ub, ub+1)
	}
}

Beaker(AOJ No.0182)

  • ビーカーに入っている水は,残さずにすべて他のビーカーに移さなければならない。ただし、一個のビーカーに水を全部移せないときは、複数のビーカーに分けて移してもよい。
  • ビーカーに水を入れるとき、いっぱいになるまで水を注がなければならない。また、水をこぼしてはならない。
  • 複数のビーカーから同じビーカーに一度に水を注いではならない。
  • 同じビーカーには一度しか水を注いではならない。

ビーカーの個数 nと各ビーカーの容量 a'_iが与えられる。
初期状態は、一番容量の大きいビーカーに水が一杯に注がれて、ほかのビーカーには水が無い状態。
すべてのビーカーに水を注ぐことができる(最終状態は、全てのビーカーに水が入った状態になっているという意味ではなく、全てのビーカーに一度だけ水が注がれたことがあるという意味)かどうかを判定する。
制約
1\leq n\leq 50
1\leq a'_i \leq 50

アルゴリズム

結構難しいうえに問題を勘違いしてて、時間掛かった。
初期状態からトップダウンに考えると自由度が高すぎて、大変そう。
3253 -- Fence Repairとかもそうだが、こういうやつはボトムアップな貪欲法で上手く行く場合が多い気がする。
とりあえず昇順ソート a'_i \rightarrow a_i。
DFSで最終状態(最後にどのビーカーに水が入っているか)を決める。
ビーカー0から順に見ていき、水が入っていないビーカーiを見つけたら、ビーカー0からビーカーi-1の水を使って( a_iより大きいのは使えないので当然0〜i-1のビーカーを使うことになる)、ビーカーiに水を注ぐ。この操作もDFSで行うが、大きいビーカーを優先して使った方が速く終わりそう。
これをビーカーn-1まで繰り返して、問題なく全てのビーカーを使用できるかどうかを答える。
計算量？シラネ。

コード

最終状態では一番小さいビーカーに水が注がれているのは自明なので、最終状態決定はビーカー1から始めている。

import java.util.*;
public class aoj0182 {
	static final Scanner stdin = new Scanner(System.in);
	static int n;
	static int[] a;
	static boolean[] finalState, water;
	public static void main(String[] args) {
		while((n = stdin.nextInt()) != 0){
			a = new int[n]; finalState = new boolean[n]; 
			for(int i = 0; i < n; ++i) a[i] = stdin.nextInt();
			Arrays.sort(a); Arrays.fill(finalState, false);
			finalState[0] = true; //YESだと仮定すると、最終状態で一番小さいやつに水が注がれている状態になる
			System.out.println(DFS(1, a[n-1]-a[0]) ? "YES": "NO");
		}
	}
	/** 最終状態を決めてから検証 */
	static boolean DFS(int k, int v){ //a[k]以降からvになるように選ぶ
		if(v == 0){ //最終状態が決定したので検証開始
			water = finalState.clone();
			for(int i = 0; i < n; ++i){
				if(!water[i]){ //a[i]は未使用、a[0]〜a[i-1]は使用済み
					if(!dfs(i-1, a[i])) return false; //a[i]にa[0]〜a[i-1]の水を使って、a[i]に入れられるかを調べる
					water[i] = true;
				}
			}
			return true;
		}
		if(v < a[k]) return false; //選んだ組み合わせではa[n-1]分の水を分割して注げなかった。
		//最終状態をDFSで決定 a[k]以降を使う
		finalState[k] = true; //a[k]を使う
		if(DFS(k+1, v-a[k])) return true; //成功してたらreturn
		finalState[k] = false;
		return DFS(k+1, v); //a[k]は使わない
	}
	static boolean dfs(int k, int v){ //a[k]〜a[0]で水が入っているものから選ぶ(大きい方優先で使う)
		if(v == 0) return true;
		if(k < 0) return false;
		if(!water[k]) return dfs(k-1, v);
		if(a[k] <= v){
			water[k] = false;
			if(dfs(k-1, v-a[k])) return true;
			water[k] = true;
		}
		return dfs(k-1, v);
	}
}

Black-and-White(AOJ No.0183)

O×の勝敗判定

コード

これをWAとか馬鹿なの？死ぬの？

import java.util.*;
public class aoj0183 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 3;
	static final char[][] board = new char[N][];
	public static void main(String[] args) {
		String s;
		while(!(s = stdin.nextLine()).equals("0")){
			board[0] = s.toCharArray(); board[1] = stdin.nextLine().toCharArray(); board[2] = stdin.nextLine().toCharArray();
			String ans = "NA";
			boolean d = true, D = true;
			for(int i = 0; i < N; ++i){
				boolean r = true, c = true;
				if(board[0][0] == '+' || board[0][0] != board[i][i]) d = false;
				if(board[0][N-1] == '+' || board[0][N-1] != board[i][N-1-i]) D = false;
				for(int j = 1; j < N; ++j){
					if(board[i][0] == '+' || board[i][0] != board[i][j]) r = false;
					if(board[0][i] == '+' || board[0][i] != board[j][i]) c = false;
				}
				if(r){ ans = ""+board[i][0]; break; }
				if(c){ ans = ""+board[0][i]; break; }
			}
			System.out.println( d ? board[0][0] : D ? board[0][N-1] : ans);
		}
	}
}

Tsuruga Castle(AOJ No.0184)

来客数を年代別に集計しる

コード

import java.util.*;
public class aoj0184 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int[] freq = new int[7];
		int n;
		while((n = stdin.nextInt()) != 0){
			Arrays.fill(freq, 0);
			while((n--)>0){
				int k = stdin.nextInt(), x;
				x = k<10 ? 0 : k<20 ? 1 : k<30 ? 2 : k<40 ? 3 : k<50 ? 4 : k<60 ? 5 : 6;
				freq[x]++;
			}
			for(int i: freq) System.out.println(i);
		}
	}
}

Goldbach's Conjecture II(AOJ No.0185)

Goldbach's Conjecture II「6以上のどんな偶数 nも、2つの素数 p,q(p\leq q)の和p+qとして表わすことができる」
n(偶数)が与えられたとき、 p,qの組み合わせの数を答える。
制約
6\leq n \leq 1000,000

コード

1000,000以下の素数は78498個。
はじめは、ルックアップテーブルつくろうと思ってたが、n×78498→80,000,000,000ぐらいの計算量オーダーになる(本当はもっと少ないが)ので、その場で計算する。

import java.util.*;
public class aoj0185 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 1000000;
	static final boolean[] table = sieve(N);
	public static void main(String[] args) {
		List<Integer> list = new LinkedList<Integer>();
		for(int i = 0; i <= N; ++i) if(table[i]) list.add(i);
		int n;
		while((n = stdin.nextInt()) != 0){
			int ans = 0;
			for(int p: list){
				int q = n-p;
				if(p > q) continue;
				if(table[q]) ans++;
			}
			System.out.println(ans);
		}
	}
	public static boolean[] sieve(int n){
		boolean[] ret = new boolean[n+1];
		Arrays.fill(ret, true);
		ret[0] = ret[1] = false;
		for(int i = 2; i*i <= n; ++i)
			if(ret[i]) for(int j = i*i; j <= n; j+=i) ret[j] = false;
		return ret;
	}
}

Aizu Chicken(AOJ No.0186)

買うべき鶏肉の量の下限 q1(100グラム単位)、予算 b、会津地鶏100グラムの値段 c1、ふつうの鶏肉100グラムの値段 c2、会津地鶏を一人が買える量の上限 q2(100グラム単位)を入力とし、次のルールで鶏肉を買ったときの、会津地鶏、ふつうの鶏肉の量（１００グラム単位）を答える。

  • 鶏肉が足りなくなると困るので、決められた量以上の鶏肉を買う。
  • 予算の許す範囲で会津地鶏をできるだけ多く買う(会津地鶏は必ず買うこと)。
  • 会津地鶏を買った残りでふつうの鶏肉をできるだけ多く買う(予算が足りなければ買わない)。

制約
1\leq q_1, b, c_1, c_2, q_2 \leq 1,000,000

アルゴリズム

会津地鶏の買う量が決まると普通の鶏肉の買う量が決まる。
会津地鶏の買う量を[1, q2]の範囲から2分探索(upperBound)で求める。 O(\log q_2)

コード

境界条件を間違えて時間掛かった。

import java.util.*;
public class aoj0186 {
	static final Scanner stdin = new Scanner(System.in);
	static final int[] q = new int[2], c = new int[2], a = new int[2];
	static int b;
	public static void main(String[] args) {
		while((q[0] = stdin.nextInt()) != 0){
			b = stdin.nextInt(); c[0] = stdin.nextInt(); c[1] = stdin.nextInt(); q[1] = stdin.nextInt();
			int i = upperBound(1, q[1]+1)-1;
			System.out.println(check(i) ? i+" "+(b-c[0]*i)/c[1] : "NA");
		}
	}
	static final boolean check(int i){
		int j = (b-c[0]*i)/c[1];
		return b-c[0]*i-c[1]*j >= 0 && i+j >= q[0] && j >= 0 && i > 0 && i <= q[1];
	}
	public static int upperBound(int begin, int end){
		int lb = begin-1, ub = end;
		//解の存在範囲が１より大きい間、反復
		while(ub - lb > 1){
			int mid =(lb + ub) / 2;
			if( check(mid) )	//midが条件を満たせば、解の存在範囲は[mid,ub)
				lb = mid;
			else		//mが条件を満たさなければ、解の存在範囲は[lb,mid)
				ub = mid;
		}
		return ub; 		//ub = lb + 1, [lb, ub)
	}
}

Stoning Fortune(AOJ No.0187)

３つの線分が与えられ、それぞれの交点を頂点とする３角形の面積で運勢を判定する。

1,900,000以上 大吉 (dai-kichi)
1,000,000以上1,900,000未満 中吉 (chu-kichi)
100,000以上1,000,000未満 吉 (kichi)
0より大きく 100,000未満 小吉 (syo-kichi)
三角形なし 凶 (kyo)

コード

らいぶらりゲー。

import java.awt.geom.Point2D;
import java.util.*;
public class aoj0187 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		Line[] l = new Line[3];
		Point[] p = new Point[3];
		while(true){
			int a = stdin.nextInt(), b = stdin.nextInt(), c = stdin.nextInt(), d = stdin.nextInt();
			if((a|b|c|d) == 0) break;
			l[0] = new Line(a,b,c,d);
			l[1] = new Line(stdin.nextDouble(), stdin.nextDouble(), stdin.nextDouble(), stdin.nextDouble());
			l[2] = new Line(stdin.nextDouble(), stdin.nextDouble(), stdin.nextDouble(), stdin.nextDouble());
			p[0] = l[0].intersectionSSPoint(l[1]);
			p[1] = l[1].intersectionSSPoint(l[2]);
			p[2] = l[2].intersectionSSPoint(l[0]);
			boolean flag = true;
			for(Point q: p) if(q == null) flag = false;
			if(!flag){
				System.out.println("kyo");
			}else{
				double S = square(p);
				System.out.println(
						1900000<=S ? "dai-kichi" :
						1000000<=S ? "chu-kichi":
						100000<=S  ? "kichi" : 
						0 < S      ? "syo-kichi" : "kyo");
			}
		}
	}
	public static final double EPS = 1e-10;
	public static boolean equal(double a, double b){ return Math.abs(a-b) < EPS; }	// a == b
	public static boolean less(double a, double b){ return a - b < -EPS; }			// a < b
	public static boolean greater(double a, double b){ return less(b,a); }			// a > b
	public static double square(Point[] polygon){
		int n = polygon.length;
		double res = 0.0;
		for(int i = 0; i < n; ++i){
			Point cur = polygon[i], next = polygon[(i+1)%n];
			res += (cur.x + next.x)*(cur.y - next.y);
		}
		return Math.abs(res/2.0);
	}
	@SuppressWarnings("serial") public static class Point extends Point2D.Double {
		public Point(double x, double y){ super(x,y); }
		public Point(Point p){ super(p.x, p.y); }
		public final double normsq(){ return x*x + y*y; }
		public final Point add(Point p){ return new Point( x + p.x, y + p.y ); }
		public final Point sub(Point p){ return new Point( x - p.x, y - p.y ); }
		public final Point mul(double k){ return new Point( k*x, k*y ); }
		public final double cross(Point p){ return x * p.y - y * p.x; }
		public final double dot(Point p){ return x * p.x + y * p.y; }
		public final int ccw(Point b, Point c) {
			Point ab = b.sub(this);
			Point ac = c.sub(this);
			if (greater(ab.cross(ac), 0))		return +1;	// counter clockwise
			if (less(ab.cross(ac), 0))			return -1;	// clockwise
			if (less(ab.dot(ac), 0))			return +2;	// (c--a--b or b--a--c) on line
			if (less(ab.normsq(), ac.normsq()))	return -2;	// (a--b--c or c--b--a) on line (b≠c, includes a=b)
			return 0;									// (a--c--b or b--c--a) on line (includes c=b, a=c, a=b=c)
		}
	} //class Point
	public static class Line{
		private final Point start;
		private final Point end;
		public Line(double sx, double sy, double ex, double ey){ start = new Point(sx,sy); end = new Point(ex,ey); }
		public Point dirV() { return end.sub(start); } //directional vector
		public final int ccw(Point p){ return start.ccw(end, p); }
		public final boolean intersectsSS(Line t) {
			return ccw(t.start) * ccw(t.end) <= 0 && t.ccw(start) * t.ccw(end) <= 0;
		}
		public final Point intersectionSSPoint(Line t) {
			return intersectsSS(t) ? intersectionLLPoint(t) : null;
		}
		public final boolean intersectsLL(Line m) {
			Point lv = this.dirV(), mv = m.dirV();
			return Math.abs(lv.cross(mv)) > EPS || // non-parallel
					Math.abs(lv.cross(mv.mul(-1))) < EPS;     // same line
		}
		public final Point intersectionLLPoint(Line m){
			Point mp = m.end.sub(m.start), lp = end.sub(start);
			double A = m.end.sub(start).cross(mp);
			double B = lp.cross(mp);
			if(equal(A, 0) && equal(B, 0)) return m.start; //same line
			if(equal(B, 0)) return null; //parallel
			return start.add(lp.mul(A/B));
		}
	} //class Line
}

Search(AOJ 0188)

2分探索の比較(反復)回数を数えれ

コード

import java.util.*;
public class aoj0188 {
	static final Scanner stdin = new Scanner(System.in);
	static int ans;
	public static void main(String[] args) {
		int n;
		while((n=stdin.nextInt()) != 0){
			Integer[] x = new Integer[n];
			for(int i = 0; i < n; ++i) x[i] = stdin.nextInt();
			Arrays.sort(x);
			ans = 0;
			_binarySearch(x, stdin.nextInt());
			System.out.println(ans);
		}
	}
	public static <T> int _binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c){
		int lb = fromIndex, ub = toIndex-1;
		while( lb <= ub ){
			ans++;
			int mid = (lb + ub) / 2, cmp = c.compare(a[mid], key);
			if( cmp == 0 ) return mid;	// exit success
			if( cmp < 0 )	lb = mid + 1;
			else 		ub = mid-1; 	// x[mid] > key
		}
		return -1; 				//exit failure
	}
	public static <T extends Comparable<? super T>> int _binarySearch(T[] a, T key){
		return _binarySearch(a, 0, a.length, key, new Comparator<T>(){
			@Override public int compare(T o1, T o2) { return o1.compareTo(o2); }
		});
	}
}

Convenient Location(AOJ No.0189)

グラフG(V,E)が与えられて、あるソースノードsから他の全ノードまでの距離の総和をSとする。
\arg\min_{(s,S)} Sを求める。

コード

やるだけ。入力に|V|が明示的に含まれていないのでちょいめんどい。

import java.util.*;
public class aoj0189 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int n;
		while((n=stdin.nextInt()) != 0){
			Map<Integer, Integer> name2id = new HashMap<Integer, Integer>(n<<1), id2name = new HashMap<Integer, Integer>(n<<1);
			List<Edge> edge = new ArrayList<Edge>(n<<1);
			for(int i = 0, id = 0; i < n; ++i){
				int a = stdin.nextInt(), b = stdin.nextInt(), c = stdin.nextInt();
				if(!name2id.containsKey(a)) name2id.put(a, id++);
				if(!name2id.containsKey(b)) name2id.put(b, id++);
				int aid = name2id.get(a), bid = name2id.get(b);
				id2name.put(aid, a); id2name.put(bid, b);
				edge.add(new Edge(aid, bid, c));
			}
			n = name2id.size();
			int[][] G = new int[n][n];
			for(int i = 0; i < n; ++i) Arrays.fill(G[i], INF);
			for(Edge e: edge) G[e.s][e.d] = G[e.d][e.s] = e.w;
			APSPResult res = FloydWarshall(G);
			int mi = -1, mw = INF;
			for(int i = 0; i < n; ++i){
				int S = 0;
				for(int j = 0; j < n; ++j) S += res.getDist(i, j);
				if(mw > S){ mi = i; mw = S; }
			}
			System.out.println(id2name.get(mi) + " " + mw);
		}
	}
	static final int INF = Integer.MAX_VALUE/2;
	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; }
	}
	@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 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);
	}
}