kanetaiの二次記憶装置

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

Byakko Delivery Company(AOJ No.0194), What is the Most Popular Shop in Tokaichi?(AOJ No.0195), Baseball Championship(AOJ No.0196), Greatest Common Divisor: Euclidean Algorithm(AOJ No.0197), Trouble in Artist Shinagawa's Artifact(AOJ No.0198), Chairs Where

Online Judge

リポジトリ

Byakko Delivery Company(AOJ No.0194)

  • 東西方向の道路 M本、南北方向の道路 N本 からなる格子状のマップが与えられる。格子点は交差点を表す。
  • 東西-南北の方向に信号機がある交差点 (x_l, y_l)もあり、一定の周期 k_lで青、赤が切り替わる。 (0 < l < \leq ns)
  • 市内の交差点間を結ぶ道路には工事中で通過できない個所 [(xs_i, ys_i), (xd_i, yd_i)]がいくつかある (0 < i \leq nc)。
  • 交差点から交差点へ移動するのに一定D時間かかるが、渋滞している道路 [(xs_j, ys_j), (xd_j, yd_j)]ではさらに長い時間 d_jかかる (0 < j\leq nj)。
  • 初期状態は、東向き、すべての信号機が南北の方向に青に切り替わる。
  • 交差点に到達した時刻に、信号が赤の場合には進入できない(※青になるまで待つということはしない)。
  • 交差点で進行方向を変えることがUターンはできない。

信号情報 (x_l,y_l,k_l), 工事情報 (xs_i, ys_i, xd_i, yd_i), 渋滞情報 (xs_j, ys_j, xd_j, yd_j, d_j), 出発地点 (S_x, S_y), 目的地点 (G_x, G_y)が与えられたとき、出発地点から目的地点に到達するまでの再短時間を求める。
※時間100いないにゴールに到達できる入力になっている。
制約
2\leq M, N \leq 20

アルゴリズム

(座標) MN\times (時間) 100 \times(進行方向) 4 = 160,000の拡張ダイクストラ.
隣接ノードは時間と進行方向によって決まる。
計算量的には、少し多めになりそうだと思ったので、 f^*(n) = time + D\times ManhattanDistanceの A^*にした。

コード

いろいろ面倒なのでjava.awt.Point使用。
信号はtime/kが偶数なら南北方向が青。
compareTo == 0とequalsは同値でないとTreeSetやTreeMapの動作は、保証されないが、
HashSetでは、大小比較はしないからcompareTo == 0とequalsが同値でなくても良いのか...
つーわけで、PriorityQueue用のcompareToと、HashSet用のequalsで判断基準が異なるようにしてる。

import java.util.*;
import java.awt.Point;
 class aoj0194 {
	static final Scanner stdin = new Scanner(System.in);
	static final Point dir[] = { new Point(0,-1), new Point(1,0), new Point(0,1), new Point(-1,0) };
	static Point start, goal;
	static int M, N, D;
	static final Map<Point, HashMap<Point, Integer>> badEdge = new HashMap<Point, HashMap<Point, Integer>>();
	static final Map<Point, Integer> light = new HashMap<Point, Integer>();
	static final int hstar(Point p){ return D*(Math.abs(goal.x - p.x) + Math.abs(goal.y - p.y)); }
	static final Point parsePoint(String s){
		String[] p = s.split("-");
		return new Point(Integer.parseInt(p[1])-1, p[0].charAt(0)-'a');
	}
	static final void addEdge(Point src, Point dst, int d){
		if(!badEdge.containsKey(src)) badEdge.put(src, new HashMap<Point, Integer>());
		if(!badEdge.containsKey(dst)) badEdge.put(dst, new HashMap<Point, Integer>());
		badEdge.get(src).put(dst, d); badEdge.get(dst).put(src, d);
	}
	public static void main(String[] args) {
		while(true){
			M = stdin.nextInt(); N = stdin.nextInt();
			if((M|N) == 0) break;
			D = stdin.nextInt();
			int ns = stdin.nextInt();
			light.clear(); badEdge.clear();
			for(int i = 0; i < ns; ++i) light.put(parsePoint(stdin.next()), stdin.nextInt());
			int nc = stdin.nextInt();
			for(int i = 0; i < nc; ++i) addEdge(parsePoint(stdin.next()), parsePoint(stdin.next()), -1);
			int nj = stdin.nextInt();
			for(int i = 0; i < nj; ++i) addEdge(parsePoint(stdin.next()), parsePoint(stdin.next()), stdin.nextInt());
			start = parsePoint(stdin.next()); goal = parsePoint(stdin.next());
			System.out.println(AStar());
		}
	}
	static int AStar(){
		PriorityQueue<State> q = new PriorityQueue<State>(M*N*400);
		HashSet<State> closed = new HashSet<State>();
		q.add(new State(start.x, start.y, 0, 1)); //time = 0, dir=1(東向き)
		while(!q.isEmpty()){
			State e = q.poll();
			if(e.p.equals(goal)) return e.time;
			if(closed.contains(e)) continue;
			closed.add(e);
			HashMap<Point, Integer> nextNode = badEdge.get(e.p);
			for(int i = 0; i < 4; ++i){
				if((e.dir + 2) % 4 == i) continue; //turn
				int nx = e.p.x + dir[i].x, ny = e.p.y + dir[i].y;
				if(0 <= nx && nx < N && 0 <= ny && ny < M){
					Point np = new Point(nx, ny);
					Integer d = null;
					if(nextNode != null) d = nextNode.get(np);
					if(d != null && d == -1) continue; //工事中
					int ntime = e.time + D + (d == null ? 0 : d); //d:渋滞遅延
					if(light.containsKey(np) && ((ntime/light.get(np)) & 1) != (i&1)) continue; //信号赤
					State ne = new State(np.x, np.y, ntime, i);
					if(ne.fstar > 100) continue;
					q.add(ne);
				}
			}
		}
		return -1;
	}
	static class State implements Comparable<State>{
		Point p;
		int time, dir, fstar;
		State(int x, int y, int time, int dir){
			this.p = new Point(x,y); this.time = time; this.dir = dir;
			fstar = time + hstar(p);
		}
		@Override public int compareTo(State o) { return fstar - o.fstar; } //for priority queue
		@Override public boolean equals(Object _o){ //for hash set
			State o = (State)_o;
			return p.equals(o.p) && time == o.time && dir == o.dir;
		}
		@Override public int hashCode(){ //for hash set
			return p.x + 100*p.y + 10000*dir + 100000*time;
		}
	}
}

What is the Most Popular Shop in Tokaichi?(AOJ No.0195)

a_i, b_iが与えられて、 I = \arg\max_i \{a_i + b_i\}としたとき、 ((char)(I + 'A'), a_{I}+b_{I})を答える

import java.util.*;
public class aoj0195 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 5;
	public static void main(String[] args) {
		Map<Integer, Character> S = new TreeMap<Integer, Character>();
		int s;
		while((s = stdin.nextInt()+stdin.nextInt()) != 0){
			S.clear();
			S.put(-s, 'A');
			for(int i = 1; i < N; ++i) S.put(-stdin.nextInt()-stdin.nextInt(), (char)('A'+i));
			int k = S.keySet().iterator().next();
			System.out.println(S.get(k) + " " + -k);
		}
	}
}

Baseball Championship(AOJ No.0196)

成績のいい順に答える

import java.util.*;
public class aoj0196 {
	static final Scanner stdin = new Scanner(System.in);
	static final int WIN = 0, LOSE = 1, DRAW = 2;
	static class T implements Comparable<T>{
		String name;
		int id;
		int freq[] = {0,0,0};
		T(String[] data, int id){
			name = data[0];
			this.id = id;
			for(int i = 1; i < data.length; ++i) freq[Integer.parseInt(data[i])]++;
		}
		@Override public int compareTo(T o) {
			return	freq[WIN] != o.freq[WIN] ? o.freq[WIN] - freq[WIN] : 
					freq[LOSE] != o.freq[LOSE] ? freq[LOSE] - o.freq[LOSE] : id - o.id;
		}
	}
	public static void main(String[] args) {
		int n;
		while((n = stdin.nextInt()) != 0){
			T[] data = new T[n]; stdin.nextLine();
			for(int i = 0; i < n; ++i) data[i] = new T(stdin.nextLine().split(" "), i);
			Arrays.sort(data);
			for(T t: data) System.out.println(t.name);
		}
	}
}

Greatest Common Divisor: Euclidean Algorithm(AOJ No.0197)

指示通りにユークリッドの互除法でGCDを求めて、GCDとステップ数を求める。
答えがあってりゃどうやって求めてもおk。

import java.util.*;
public class aoj0197 {
	static final Scanner stdin = new Scanner(System.in);
	static int ans;
	public static int GCD(int a, int b){ ans++; return b == 0 ? a : GCD(b, a%b); }
	public static void main(String[] args) {
		while(true){
			int x = stdin.nextInt(), y = stdin.nextInt();
			if((x|y) == 0) break;
			if(x < y){ int temp = x; x = y; y = temp; }
			ans = -1;
			System.out.println(GCD(x,y) + " " + ans);
		}
	}
}

Trouble in Artist Shinagawa's Artifact(AOJ No.0198)

各面にRed、Yellow、Blue、Magenta、Green、Cyan のいずれかの色がついた立方体がn個与えられる。
だぶっている配色がだぶっている立方体の数を答える。

コード

回転パターン生成の部分はDice Puzzleを解いたときのコードをそのまま流用している。

import java.util.*;
public class aoj0198 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 4;
	public static void main(String[] args) {
		int n;
		Set<Cube<String>> set = new HashSet<Cube<String>>();
		while((n = stdin.nextInt()) != 0){
			stdin.nextLine();
			set.clear();
			int ans = 0;
			for(int i = 0; i < n; ++i){
				boolean flag = true;
				for(Cube<String> d : (new Cube<String>(stdin.nextLine().split(" "))).generateAllPattern()){
					if(set.contains(d)){
						if(flag) ans++;
						flag = false;
					}else{
						set.add(d);
					}
				}
			}
			System.out.println(ans);
		}
	}
	@SuppressWarnings("unchecked") public static class Cube <T>{
		static enum Surface{TOP, FRONT, RIGHT, LEFT, BACK, BOTTOM};
		static final int N = 6, M = 4;
		private T[] id;
		public final T get(Surface s){ return id[s.ordinal()]; }
		public Cube(T[] c){ id = (T[]) new Object[N]; System.arraycopy(c, 0, id, 0, N); }
		public Cube(Cube<T> c){ id = (T[]) new Object[N]; System.arraycopy(c.id, 0, id, 0, N); }
		public final void rotateXZ() { rotate(Surface.TOP, Surface.FRONT, Surface.BOTTOM, Surface.BACK); }
		public final void rotateYZ() { rotate(Surface.TOP, Surface.RIGHT, Surface.BOTTOM, Surface.LEFT); }
		public final void rotateXY() { rotate(Surface.FRONT, Surface.LEFT, Surface.BACK, Surface.RIGHT); }
		private final void rotate(Surface a, Surface b, Surface c, Surface d) { //abcd->bcda
			T tmp = id[a.ordinal()];
			id[a.ordinal()] = id[b.ordinal()];
			id[b.ordinal()] = id[c.ordinal()];
			id[c.ordinal()] = id[d.ordinal()];
			id[d.ordinal()] = tmp;
		}
		public Set<Cube<T>> generateAllPattern(){
			Set<Cube<T>> ret = new HashSet<Cube<T>>(N*M);
			for (int k = 0; k < N; ++k){
				for (int i = 0; i < M; rotateXY(), ++i) ret.add(new Cube<T>(this));
				if((k&1)==0) rotateXZ(); else rotateYZ();
			}
			return ret;
		}
		@Override public String toString() {
			StringBuilder sb = new StringBuilder();
			for(Surface s : Surface.values()) sb.append(id[s.ordinal()]);
			return sb.toString();
		}
		@Override public boolean equals(Object o) {
			if(!(o instanceof Cube<?>))return false;
			Cube<T> d = (Cube<T>)o;
			for(Surface f : Surface.values()) if(!id[f.ordinal()].equals(d.id[f.ordinal()])) return false;
			return true;
		}
		@Override public int hashCode() {
			int hash = 17;
			for(Surface f : Surface.values()) hash += 31*hash+id[f.ordinal()].hashCode();
			return hash;
		}
	}
}

Chairs Where Demanding People Sit(AOJ No.0199)

A, B, C, Dの国の人が椅子に座っていく。

  • A: 左端から見ていき空いている椅子に座る
  • B: A 国人の隣以外で、右端から空いている椅子に座る。ただし、 A国人の隣しか空いていない場合、我慢して左端から空いている椅子に座る。
  • C:左側から順に座っている人を見ていき、一番左側に座っている人 の右隣に座ろうとするが、そこが埋まっているならその人の左隣に座ろうとする。そこも埋まっ ているなら次の人の隣に同条件で座ろうとする。どの椅子にも人が座っていなければ真ん中(椅 子の数が奇数の場合 (n+1)/2 、偶数の場合 n/2+1 )の椅子に座る。
  • D: 一番近い人との距離が、一番大きくなる椅子に座ろうとする。 同条件の椅子が複数ある場合や、どうしても誰かの隣に座らなければならない場合、その中で一 番左側にある椅子に座る。誰も座っていない場合は左端の椅子に座る。

乗客の情報を入力とし、 椅子にどのように座っているかを出力する
制約
椅子の数は 1 以上 100 以下とし、乗客の数は椅子の数を超 P えることはない。

コード

「超 P えることはない」ってなんや。
D国人が一番めんどい。C国人で真ん中に座るときの奇偶の場合分けは必要ない。

import java.util.*;
public class aoj0199 {
	static final Scanner stdin = new Scanner(System.in);
	static final void A(char[] Seat){ for(int i = 0; i < Seat.length; ++i) if(Seat[i] == '#'){ Seat[i] = 'A'; return; } }
	static final void B(char[] Seat){
		int n = Seat.length;
		for(int i = n-1; i >= 0; --i){
			if(Seat[i] == '#'){
				if(i+1 < n && Seat[i+1] == 'A' || i-1 >= 0 && Seat[i-1] == 'A') continue;
				Seat[i] = 'B'; return;
			}
		}
		for(int i = 0; i < n; ++i) if(Seat[i] == '#'){ Seat[i] = 'B'; return; }
	}
	static final void C(char[] Seat){
		int n = Seat.length;
		for(int i = 0; i < n; ++i)
			if(Seat[i] != '#'){
				if(i+1 < n && Seat[i+1] == '#'){ Seat[i+1] = 'C'; return; }
				if(i-1 >= 0 && Seat[i-1] == '#'){ Seat[i-1] = 'C'; return; }
			}
		Seat[n/2] = 'C'; //場合分けの必要なし
	}
	static final void D(char[] Seat){
		int n = Seat.length, count = 0, max = -1, mi = -1;
		int[] dist = new int[n];
		for(int i = n - 1; i >= 0; --i) dist[i] = (Seat[i] == '#' ? ++count : (count = 0)); //右の人までの距離を計算
		count = 0;
		for(int i = 0; i < n; ++i){
			count = (Seat[i] == '#' ? count+1 : 0); //左の人までの距離を計算
			dist[i] = (i == 0 || i == n-1) ? 
					Math.max(dist[i], count) : Math.min(dist[i], count); //端っこならmax, そうじゃないときはmin
			if(max < dist[i]){ max = dist[i]; mi = i; }
		}
		Seat[mi] = 'D';
	}
	public static void main(String[] args) {
		while(true){
			int n = stdin.nextInt(), m = stdin.nextInt();
			if((n|m) == 0) break;
			char[] Seat = new char[n]; Arrays.fill(Seat, '#');
			for(int i = 0; i < m; ++i){
				switch(stdin.next().toCharArray()[0]){
					case 'A': A(Seat); break;
					case 'B': B(Seat); break;
					case 'C': C(Seat); break;
					case 'D': D(Seat); break;
				}
			}
			System.out.println(Seat);
		}
	}
}