Aka-beko and 40 Thieves(AOJ No. 0266), Triangle of Blocks(AOJ No. 0267), Kongo Type(AOJ No. 0268), East Wind(AOJ No. 0269), Modular Query(AOJ No. 0270)

リポジトリ

Aka-beko and 40 Thieves(AOJ No.0266)

1 or 2の系列が与えられたとき、AからBに行けるかどうかを答える。

コード

import java.util.*;
public class aoj0266 {
	static final Scanner stdin = new Scanner(System.in);
	enum City { 
		A, B, X, Y, Z, W, D;
		static City path[][] = { {X, Y}, {Y, X}, {D, Z}, {X, D}, {W, B}, {B, Y}, {D, D} };
	}
	public static void main(String[] args) {
		while (true) {
			char[] str = stdin.next().toCharArray();
			if (str[0] == '#') break;
			int pos = City.A.ordinal();
			for (char c : str) pos = City.path[pos][c - '0'].ordinal();
			System.out.println(pos == City.B.ordinal() ? "Yes" : "No");
		}
	}
}

Triangle of Blocks(AOJ No. 0267)

ブロックの並びが与えられたとき

• 一番下のブロックを取り除く
• 取り除いたブロックを右端に縦に並べる。
• 隙間がある場合は右につめる

という操作を何回繰り返せば段差１の階段状になるかを答える。完成系にならない場合または操作回数が10,000を超える場合はNAと答える。
階段の高さをkとしたときブロックの総数がk×(k＋1)/2でないと完成系はつくれない。

コード

import java.util.*;
public class aoj0267 {
	static final Scanner stdin = new Scanner(System.in);
	static final int LIMIT = 10000, N = 100;
	@SuppressWarnings("serial") static final List<Integer> TRI = new ArrayList<Integer>(N){
		{ add(-1); for (int i = 0; i < N; ++i) add((i+1)*(i+2)/2); }
	};
	public static void main(String[] args) {
		while (true) {
			int n = stdin.nextInt(), s = 0;
			if (n == 0) break;
			List<Integer> l = new ArrayList<Integer>(n);
			for (int i = 0; i < n; ++i) {
				l.add(stdin.nextInt());
				s += l.get(i);
			}
			int i = -1;
			if (TRI.contains(s)) {
				for (i = 0; i <= LIMIT &&  !check(l); ++i) {
					int sz = l.size();
					for (int j = 0; j < sz; ++j) l.set(j, l.get(j)-1);
					int idx = -1;
					while((idx = l.indexOf(0)) != -1) l.remove(idx);
					l.add(sz);
				}
			}
			System.out.println(i > LIMIT ? -1 : i);
		}
	}
	static boolean check(List<Integer> l) {
		for (int i = 0; i < l.size(); ++i) if (l.get(i) != i+1) return false;
		return true;
	}
}

Kongo Type(AOJ No. 0268)

金剛型：

金剛型２進数を１０進数で一切の誤差無く出力する。

コード

BigDecimal使わなくてもいいかも

import java.math.BigDecimal;
import java.util.*;
public class aoj0268 {
	static final Scanner stdin = new Scanner(System.in);
	static final BigDecimal divisor = new BigDecimal((1<<7));
	public static void main(String[] args) {
		int n = stdin.nextInt();
		while (n-- > 0) {
			long x = Long.parseLong(stdin.next(), 16);
			StringBuilder sb = new StringBuilder((x&0x80000000) == 0 ? "" : "-");
			BigDecimal d = new BigDecimal((x&0x7fffffff));
			sb.append(d.divide(divisor).toString());
			if (sb.indexOf(".") == -1) sb.append(".0");
			System.out.println(sb.toString());
		}
	}
}

East Wind(AOJ No. 0269)

座標(0,0)に私の梅の木があり、
まず、H個の家、U個の（私のではない）梅の木、M個の松の木、S個の桜の木の座標と、梅・桃・桜の香りが広がる角度du、dm、dsが与えられる。
風の強さaと風の吹く方向wが与えられたとき、図のように香りが広がる。

R日分の風の情報(風の強さ+風の方向)が与えられたとき、私の梅の木の香りだけがとどく日数が最も多い家を答える。
候補が多い場合は、家を昇順にならべて答える。
制約
1 ≤ H,R ≤ 100)

• 1,000 ≤ 座標 ≤ 1,000 以下の整数である。

0 ≤ w < 360, 1 ≤ du,dm,ds < 180 （単位は°）
0 < a ≤ 100
0 ≤ U, M, S ≤ 10

アルゴリズム

香りの境界の方向ベクトルを

木から家への方向ベクトルを
としたとき、距離がa以内かつ、がからccw, からcwの位置にあれば香りがその家にとどく。
ccwかcwかは外積の符号で決めればいい。

コード

Math.toRadiansの存在に初めて気付いた。

import java.awt.geom.Point2D;
import java.util.*;
public class aoj0269 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while (true) {
			int H = stdin.nextInt(), R = stdin.nextInt();
			if ((H|R) == 0) break;
			Point[] house = new Point[H];
			for (int i = 0; i < H; ++i) house[i] = new Point(stdin.nextDouble(), stdin.nextDouble());
			T[][] t = new T[3][];
			t[0] = new T[stdin.nextInt()];
			t[1] = new T[stdin.nextInt()];
			t[2] = new T[stdin.nextInt()];
			int[] ds = {stdin.nextInt(), stdin.nextInt(), stdin.nextInt()};
			for (int i = 0; i < t.length; ++i)
				for (int j = 0; j < t[i].length; ++j) t[i][j] = new T(stdin.nextInt(), stdin.nextInt(), ds[i]);
			T myU = new T(0, 0, ds[0]);
			int freq[][] = new int[H][2];
			for (int i = 0; i < H; ++i) freq[i][1] = i+1;
			for (int k = 0; k < R; ++k) {
				int w = stdin.nextInt(), a = stdin.nextInt();
				myU.input(w, a);
				for (int i = 0; i < t.length; ++i) for (int j = 0; j < t[i].length; ++j) t[i][j].input(w, a);
				LOOP: for (int h = 0; h < H; ++h) {
					if (!myU.contain(house[h])) continue;
					for (int i = 0; i < t.length; ++i) for (int j = 0; j < t[i].length; ++j) 
						if (t[i][j].contain(house[h])) continue LOOP;
					freq[h][0]++;
				}
			}
			Arrays.sort(freq, new Comparator<int[]>(){
				@Override public int compare(int[] o1, int[] o2) {
					return o1[0] != o2[0] ? o2[0] - o1[0] : o1[1] - o2[1];
				}
			});
			StringBuilder sb = new StringBuilder();
			if (freq[0][0] == 0) {
				sb.append("NA");
			} else { 
				sb.append(freq[0][1]);
				int m = freq[0][0];
				for (int i = 1; i < H; ++i) {
					if (freq[i][0] == m) sb.append(" ").append(freq[i][1]);
					else break;
				}
			}
			System.out.println(sb.toString());
		}
	}
	static class T {
		Point[] tri = new Point[3];
		int d, a;
		T(int x, int y, int d) {
			this.d = d;
			tri[0] = new Point(x, y);
		}
		void input(int w, int a) {
			this.a = a;
			double theta = Math.toRadians(w-d/2);
			tri[1] = new Point(Math.cos(theta), Math.sin(theta));
			theta = Math.toRadians(w+d/2);
			tri[2] = new Point(Math.cos(theta), Math.sin(theta));
		}
		boolean contain(Point p) { 
			return leq(p.distance(tri[0]), a) && 
				leq(0, tri[1].cross(p.sub(tri[0]))) && leq(0, p.sub(tri[0]).cross(tri[2]));
		}
	}
	public static final double EPS = 1e-9;
	public static boolean leq(double a, double b){ return a - b < EPS; }			// a <= b
	@SuppressWarnings("serial") public static class Point extends Point2D.Double {
		public Point(double x, double y){ super(x,y); }
		public final Point sub(Point p){ return new Point( x - p.x, y - p.y ); }
		public final double cross(Point p){ return x * p.y - y * p.x; }
	} //class Point
}

Modular Query(AOJ No. 0270)

N個の整数ci, とQ個の整数(クエリ)qjが与えられ、各クエリごとにを答える。
制約
2 ≤ N ≤ 300,000
2 ≤ Q ≤ 100,000
1 ≤ ci, q_j ≤ 300,000

アルゴリズム

cを入力した後、LB[k] = lower_bound(c, c+N, k-1)を求めとく(kより小さい最大のci).
qが与えられると、LB[max(c)]からLB[1]の方向へ探索する。
ci = kだったとき、剰余p = ci % qjを求めて解答候補を更新(最大値を保存)する。
次の探索位置は、k-pより小さい最大のci。
k' = LB[k-p]の位置にスキップして探索する。
これを繰り返すとで求まる。
qが大きく、ciが密集しているときに効率がよくなる。

コード

import java.util.*;
public class aoj0270 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 300001, LB[] = new int[N];
	static final boolean C[] = new boolean[N];
	public static void main(String[] args) {
		int n = stdin.nextInt(), Q = stdin.nextInt(), m = -1;
		for (int i = 0; i < n; ++i) { int c = stdin.nextInt(); C[c] = true; m = Math.max(m, c); }
		for (int i = 0, j = 0; i < m+1; ++i) { LB[i] = j; if (C[i]) j = i; }
		while (Q-- > 0) {
			int q = stdin.nextInt(), ans = 0, p;
			for (int i = m; i > 0; i = LB[i-p]) {
				p = i % q;
				ans = Math.max(ans, p);
				if (i - p < 0) break;
			}
			System.out.println(ans);
		}
	}
}

Cats Going Straight(AOJ No.0265)

リポジトリ

Points for a Perfect Scorer(AOJ No.0265)

塀が多角形で表され、いくつかの頂点にえさを置く。
猫が塀を登って、内部に侵入し、えさに向かって直進する。
猫がどこから入ってきても、塀にぶつからないようにえさを配置するとき、必要なえさの数の最小値を答える。
制約
3 ≤ 多角形の頂点の数n ≤ 16

• 1000 ≤ 頂点座標xi, yi ≤ 1000

アルゴリズム

えさの配置場所の組み合わせに対し、猫の侵入場所(線分)からえさ(頂点)への可視性の検証を行い探索する。
残念ながら頂点間の可視性を見ているだけでは駄目。
辺を分割してカバーできる場合がある。http://warp.ndl.go.jp/info:ndljp/pid/8086159/web-ext.u-aizu.ac.jp/pc-concours/2012/03/pdf/2012pre_editorial.pdf
辺の分割は、多角形の頂点を結ぶ直線と辺の交点で分割すればいい。
分割辺から頂点への可視性を求め、配置したえさで全ての分割辺をカバーできているかを調べけばおk。
分割辺から頂点への可視性は、分割辺の中点から頂点への線分が多角形の内部にあるかどうかできまる。
（頂点間を結ぶ直線の交点で分割したので、分割辺のどの点をとっても可視性は変わらないはず。
なので、分割辺を内分する点から頂点が見えていればその分割辺は可視。）

コード

EPS=1e-10じゃwrong answerだった。。EPS調整してAcceptしました。
分割辺を求める際、隣り合う交点(の中点)を辺の始点からの距離でソートして求めているが、
距離野代わりに、辺ベクトルと辺の始点から交点へのベクトルとの内積とかでソートした方が速いかもしれない(距離だと√の計算が重そうなので)。

import java.awt.geom.Point2D;
import java.util.*;
public class aoj0265 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while (true) {
			int n = stdin.nextInt();
			if (n == 0) break;
			Point[] polygon = new Point[n];
			for (int i = 0; i < n; ++i) polygon[i] = new Point(stdin.nextDouble(), stdin.nextDouble());
			List<Point> seg = new ArrayList<Point>(n*n);
			for (Point p : polygon) seg.add(new Point(p));
			for (int k = 0; k < n; ++k) {
				Line r = new Line(polygon[k], polygon[(k+1)%n]);
				List<Object[]> crosspoints = new ArrayList<Object[]>();
				for(int i = 0; i < n; ++i) for(int j = i+1; j < n; ++j) {
					Line l = new Line(polygon[i], polygon[j]);
					if (!l.parallel(r)) {
						Point p = l.intersectionLLPoint(r);
						if (equal(p.distancePS(r), 0)) 
							crosspoints.add(new Object[]{ l.start.distance(p), p});
					}
				}
				Collections.sort(crosspoints, new Comparator<Object[]>() {
					@Override public int compare(Object[] o1, Object[] o2) {
						int d = Double.compare((Double)o1[0], (Double)o2[0]);
						return d != 0 ? d : ((Point)o1[1]).compareTo((Point)o2[1]);
					}
				});
				for(int i = 0; i < crosspoints.size()-1; ++i)
					seg.add((((Point)crosspoints.get(i)[1]).add((Point)crosspoints.get(i+1)[1])).div(2));
			}
			int reachability[] = new int[seg.size()];
			for(int i = 0; i < n; ++i) for(int j = 0; j < seg.size(); ++j) {
				Line l = new Line(polygon[i], seg.get(j));
				if (contains(polygon, l)) reachability[j] |= bit(i);
			}
			int ans = n;
			LOOP: for(int S = 0; S < bit(n); ++S) {
				int popCount = Integer.bitCount(S);
				if (ans <= popCount) continue;
				for (int reachable : reachability) if ((reachable & S) == 0) continue LOOP;
				ans = popCount;
			}
			System.out.println(ans);
		}
	}
	static String toString(int field, int n) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; ++i) sb.append((field & bit(i)) != 0 ? "1" : "0");
		return sb.toString();
	}
	static void print(int field, int n) { System.out.println(toString(field, n)); }
	static int bit(int bit) { return (1 << bit); }
	public static final double EPS = 1e-2;
	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 leq(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 boolean geq(double a, double b){ return leq(b,a); }				// a >= b
	@SuppressWarnings("serial") public static class Point extends Point2D.Double implements Comparable<Point>{
		public Point(double x, double y){ super(x,y); }
		public Point(Point p){ super(p.x, p.y); }
		public final double norm(){ return Math.sqrt( normsq() ); }
		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 Point div(double k){ return new Point( x/k, y/k ); }
		//compareTo ascending order. priority 1. The x coordinate, 2. The y coordinate.
		@Override public final int compareTo(Point o){
			return (this.x != o.x) ? java.lang.Double.compare(this.x, o.x) : java.lang.Double.compare(this.y, o.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)
		}
		public final Point projection(Line l){
			Point a = l.dirV();
			Point b = this.sub(l.start);
			return l.start.add(a.mul(a.dot(b)/a.normsq()));
		}
		public final double distancePS(Line s){
			Point proj = projection(s);
			return proj.intersectsPS(s) ? distance(proj) : Math.min(distance(s.start), distance(s.end));
		}
		public final boolean intersectsPS(Line s) {
			//return s.ccw(this) == 0; //これでもおk
			return equal(s.start.distance(this) + this.distance(s.end), s.end.distance(s.start)); //三角不等式で等号が成り立つとき
		}
	} //class Point

	public static class Line{
		private final Point start;
		private final Point end;
		public Line(Point start, Point end){ this.start = new Point(start); this.end = new Point(end); }
		public Point dirV() { return end.sub(start); } //directional vector
		public double distance() { return end.distance(start); }
		public final int ccw(Point p){ return start.ccw(end, p); }
		public final boolean parallel(Line m) { return equal(this.dirV().cross(m.dirV()), 0); }
		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 Point intersectionLLPoint(Line m){
			Point mp = m.dirV(), lp = this.dirV();
			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
	public static boolean contains(Point[] polygon, Point p) {
		boolean in = false;
		for (int i = 0, n = polygon.length; i < n; ++i) {
			Point a = polygon[i].sub(p), b = polygon[(i+1)%n].sub(p);
			if (a.y > b.y){ Point temp = b; b = a; a = temp; }
			if (a.y <= 0 && 0 < b.y) //点pからxの正方向への半直線が多角形の頂点をとおるとき、最終的に交差数を偶数回にするためどちらかを<=ではなく、<にする
				if (a.cross(b) < 0) in = !in; //=0 -> a//b -> on 
			if (equal(a.cross(b), 0) && leq(a.dot(b), 0)) return true; //on edge
		}
		return in; //in out
	}
	public static boolean contains(Point[] polygon, Line s) {
		final int n = polygon.length;
		List<Object[]> numl = new ArrayList<Object[]>();
		numl.add(new Object[]{0., s.start});
		numl.add(new Object[]{s.distance(), s.end});
		for (int i = 0; i < n; ++i) {
			Point p = s.intersectionSSPoint(new Line(polygon[i], polygon[(i+1)%n]));
			if (p != null) numl.add(new Object[]{p.distance(s.start), p});
		}
		Collections.sort(numl, new Comparator<Object[]>(){
			@Override public int compare(Object[] o1, Object[] o2) {
				int d = Double.compare((Double)o1[0], (Double)o2[0]);
				return d != 0 ? d : ((Point)o1[1]).compareTo((Point)o2[1]);
			}
		});
		for (int i = 0; i < numl.size()-1; ++i) 
			if(!contains(polygon, ((Point)numl.get(i)[1]).add((Point)numl.get(i+1)[1]).div(2))) return false;
		return true;
	}
}

Points for a Perfect Scorer(AOJ No.0256), Railway Ticket(AOJ No.0257), Kitchen Garden(AOJ No.0258), All Numbers Lead to 6174(AOJ No.0259), Salary for a Plumber(AOJ No.0260), Mayan Crucial Prediction(AOJ No.0261), Making Sugoroku(AOJ No.0262), Beat Panel(A

リポジトリ

Points for a Perfect Scorer(AOJ No.0256)

足し算する。

コード

import java.util.*;
public class aoj0256 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int sum = 0;
		while (stdin.hasNext()) sum += stdin.nextInt();
		System.out.println(sum);
	}
}

Railway Ticket(AOJ No.0257)

要するに、a1, a2, bが与えられて、a1+a2 = 2 or b = 1 なら"Open"そうでないなら"Close"と答える。

コード

import java.util.*;
public class aoj0257 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int a = stdin.nextInt() + stdin.nextInt(), b = stdin.nextInt();
		System.out.println(a == 2 || b == 1 ? "Open" : "Close");
	}
}

Kitchen Garden(AOJ No.0258)

数列が与えられる。ある数を１つ除くと等差数列になるので、その数を答える。

コード

全探索。めんどいから。

import java.util.*;
public class aoj0258 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		L: while (true) {
			int n = stdin.nextInt(), a[] = new int[n+1], tmp[] = new int[n];
			if (n == 0) break;
			for (int i = 0; i <= n; ++i) a[i] = stdin.nextInt();
			LOOP: for (int s = 0; s <= n; ++s) {
				for (int i = 0, j = 0; i <= n; ++i) if (i != s) tmp[j++] = a[i];
				int diff = tmp[1] - tmp[0];
				for (int i = 2; i < n; ++i) if (diff != tmp[i] - tmp[i-1]) continue LOOP;
				System.out.println(a[s]);
				continue L;
			}
		}
	}
}

All Numbers Lead to 6174(AOJ No.0259)

• N の桁それぞれの数値を大きい順に並べた結果得た数を L とする
• N の桁それぞれの数値を小さい順に並べた結果得た数を S とする
• 差 L-S を新しい N とする(1回分の操作終了)
• 新しい N に対して 1. から繰り返す

与えられたNに対してこの操作を何回すれば、6174になるかを答える。
与えられたNが全桁が同じ数字なら6174に収束しないので、NAと答える。

コード

import java.util.*;
public class aoj0259 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while (true) {
			String s = stdin.next();
			if (s.equals("0000")) break;
			char[] c = s.toCharArray();
			if (c[0] == c[1] && c[1] == c[2] && c[2] == c[3]) { System.out.println("NA"); continue; }
			int ans = 0;
			for (ans = 0; !s.equals("6174"); ++ans) {
				Arrays.sort(c);
				StringBuilder sb = new StringBuilder(new String(c));
				int S = Integer.parseInt(sb.toString()), L = Integer.parseInt(sb.reverse().toString());
				s = String.format("%04d", L-S);
				c = s.toCharArray();
			}
			System.out.println(ans);
		}
	}
}

Salary for a Plumber(AOJ No.0260)

n個のパイプの長さとn-1個のジョイントの長さが与えられる。
パイプはジョイントと組み合わせて１つのパイプにすることができる。
パイプの本数×パイプの長さの総和の最大値を答える。
ジョイントは全て使わなくてよい。
制約
2 ≤ n ≤ 65000
1 ≤ パイプの長さ、ジョイントの長さ ≤ 1000

アルゴリズム

１個のパイプを作る場合からはじめて、使っているジョイントを外して、2個、...、n個のパイプを作る場合を考える。
計算式を見ると外すジョイントは小さい順にすればいいことが分かる。
はじめにジョイントの長さとパイプの長さの総和を求めて候補とし、ジョイントを昇順にソートしておく。
昇順にジョイントを外した場合のパイプの本数×パイプの長さを計算し、現在の候補より大きければそれを候補として更新していけば最大値が求まる。

コード

intじゃなくてlongにしませう。

import java.util.*;
public class aoj0260 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while (true) {
			int n = stdin.nextInt();
			if (n == 0) break;
			int[] j = new int[n-1];
			long sum = 0;
			for (int i = 0; i < n; ++i) sum += stdin.nextInt();
			for (int i = 0; i < n-1; ++i) { j[i] = stdin.nextInt(); sum += j[i]; }
			long ans = sum;
			Arrays.sort(j);
			for (int i = 0; i < n-1; ++i) { sum -= j[i]; ans = Math.max(ans, sum * (i+2)); }
			System.out.println(ans);
		}
	}
}

Mayan Crucial Prediction(AOJ No.0261)

マヤ長期暦では、以下の単位で暦を表す。

• １キン＝１日
• １ウィナル＝２０キン
• １トゥン＝１８ウィナル
• １カトゥン＝２０トゥン
• １バクトゥン＝２０カトゥン

b.ka.t.w.ki (マヤ長期暦の日付)または、y.m.d は(西暦の日付)が与えられたとき、西暦またはマヤ長期暦に変換する。
ただし、マヤ長期暦の 0.0.0.0.0 は西暦の 2012.12.21 に対応する。
また、0.0.0.0.0から13バクトゥンたつと一周回って、0.0.0.0.0になる。
制約
マヤ長期暦

b	バクトゥン	(0 ≤ b< 13)
ka	カトゥン	(0 ≤ ka < 20)
t	トゥン	(0 ≤ t< 20)
w	ウィナル	(0 ≤ w < 18)
ki	キン	(0 ≤ ki < 20)

西暦

y	年	(2012 ≤ y ≤ 10,000,000)
m	月	(1 ≤ m ≤ 12)
d	日	(1 ≤ d ≤ 31)

アルゴリズム

ユリウス日とy,m,dの相互変換の仕方を知ってると簡単。

• 西暦からマヤ長期暦への変換

西暦のユリウス日-2012.12.21のユリウス日がマヤ長期暦0.0.0.0.0を基準としたときの日数になる。これから上の表に従って、変換する。
変換の際、13バクトゥン分の日数の剰余をとっておく。

• マヤ長期暦から西暦への変換

0.0.0.0.0からの日数を上の表に従って求めて、これを2012.12.21のユリウス日に足せば、西暦のユリウス日になる。
このユリウス日を西暦に変換する。

コード

import java.util.*;
public class aoj0261 {
	static final Scanner stdin = new Scanner(System.in);
	enum Solver {
		VER1 { @Override long Greg2JulianDay(int y, int m, int d, boolean modflag) { return GregToJulianDay(y, m, d, modflag); } }, 
		VER2 { @Override long Greg2JulianDay(int y, int m, int d, boolean modflag) { return GregToJD(y, m, d, modflag); } };
		long Greg2JulianDay(int y, int m, int d, boolean modflag) { return 0L; }
	}
	static final Solver solver = Solver.VER2;
	static final long base_mod = solver.Greg2JulianDay(2012, 12, 21, true), base = solver.Greg2JulianDay(2012, 12, 21, false);
	static final int maya[] = {20*18*20*20, 20*18*20, 20*18, 20, 1}, rotate = 20*18*20*20*13;
	public static void main(String[] args) {
		while (true) {
			String[] d = stdin.next().split("\\.");
			if (d[0].charAt(0) == '#') break;
			StringBuilder sb = new StringBuilder();
			if (d.length == 3) {
				long jday = solver.Greg2JulianDay(Integer.parseInt(d[0]), Integer.parseInt(d[1]), Integer.parseInt(d[2]), true) - base_mod;
				jday %= rotate;
				for (int unit: maya) {
					sb.append('.').append(jday/unit);
					jday %= unit;
				}
			} else {
				long jday = base;
				for (int i = 0; i < d.length; ++i) jday += maya[i]*Integer.parseInt(d[i]);
				int[] ans = JulianDatyToGreg((int)jday);
				for (int ymd : ans) sb.append('.').append(ymd);
			}
			System.out.println(sb.substring(1));
		}
	}
	public static final int[] JulianDatyToGreg(int jd){
		int temp = jd + 32044; // +0.5
		int y = -4800;

		jd = temp/146097;			temp %= 146097;			y += (jd * 400);
		jd = (temp/36524 + 1)*3/4;	temp -= (jd * 36524);	y += (jd * 100);
		jd = temp/1461;				temp %= 1461;			y += (jd * 4);
		jd = (temp/365 + 1)*3/4;	temp -= (jd * 365);		y += jd;

		int m = (temp*5 + 308)/153 -2;
		int d = temp - (m + 4)*153/5 + 122;
		y += ((m + 2)/12 );

		m = (m+2) % 12 + 1;
		d++;
		return new int[]{ y, m, d };
	}
	public static final long GregToJulianDay(int y, int m, int d, boolean modflag) { 
		y += 4800;
		if (m < 3){ --y; m += 12; }
		return - (modflag ?  2400001L : 0L) + 365L*y + y/4 - y/100 + y/400 + (153L*m - 457)/5 + d-32045;
	}
	public static final long GregToJD(int y, int m, int d, boolean modflag){ // Ver. 2
		int a  = (14-m)/12;
		y = y + 4800 - a;
		m = m + 12*a -3;
		return - (modflag ?  2400001L : 0L) + d + (153L*m + 2)/5 + 365L*y + y/4 - y/100 + y/400 - 32045;
	}
}

Making Sugoroku(AOJ No.0262)

すごろく。ルーレットが出す数の最大値max、「ふりだし」と「あがり」以外のマスの数が与えられる。
各マスには指示を表す数 di(-n ≤ di ≤ n) がかいてある。di がゼロのときは指示が書いていないことを、正の数のときは |di| 進む指示を、負の数のときは |di| 戻る指示を表す。
マスの指示で進んだり戻ったりしたあとのマスの指示には従わない。
指示により「ふりだし」より前に戻とうとする場合は、「ふりだし」でとまる。「あがり」より先に進もうとした場合は、あがったことになる。
全てのパターンを考えたとき、永遠にゴールに辿りつけなくなるハマリパターンがあるかどうかを答える。

アルゴリズム

各マスから１ターンで到達可能なマスへの有向辺を張る。
その逆グラフ上で、「あがり」から到達可能なマスを調べる。
もとのグラフ上で、「ふりだし」から到達可能マスを調べる。
元のグラフ上の到達可能マスがすべて、逆グラフ上の到達可能マスに含まれていたら、ハマリなし。

コード

import java.util.*;
public class aoj0262 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while (true) {
			int max = stdin.nextInt();
			if (max == 0) break;
			int n = stdin.nextInt(), map[] = new int[n+2];
			for (int i = 1; i <= n; ++i) map[i] = stdin.nextInt();
			boolean M[][] = new boolean[n+2][n+2], visited[] = new boolean[n+2], visited2[] = new boolean[n+2];
			for (int i = 0; i <= n; ++i) {
				for (int ii = 1; ii <= max; ++ii) {
					int j = i + ii;
					if (j >= n+1) {
						M[i][n+1] = true;
					} else {
						j += map[j];
						M[i][j <= 0 ? 0 : n+1 <= j ? n+1 : j] = true;
					}
				}
			}
			Queue<Integer> q = new LinkedList<Integer>();
			q.add(n+1); visited[n+1] = true;
			while (!q.isEmpty()) {
				int p = q.poll();
				for (int i = 0; i <= n+1; ++i) if (M[i][p] && !visited[i]) {
					q.add(i); visited[i] = true;
				}
			}
			q.add(0); visited2[0] = true;
			String ans = "OK";
			while (!q.isEmpty()) {
				int p = q.poll();
				if (!visited[p]) {
					ans = "NG";
					break;
				}
				for (int i = 0; i <= n+1; ++i) if (M[p][i] && !visited2[i]) {
					q.add(i); visited2[i] = true;
				}
			}
			System.out.println(ans);
		}
	}
}

Beat Panel(AOJ No.0263)

16個のボタンが並んでいる。一定間隔でビート音が鳴り最後に終了音が鳴る。ビート音が鳴ると同時に複数のボタンが光る。プレイヤーは、ビート音が鳴った直後から次の音が鳴るまでの間に両手の指を使って複数のボタンを１度だけ同時に押すことができる。終了音が鳴ったと同時にゲームは終了する。
プレイヤーは c 通りの押し方を習得しており、ビート音が鳴る度に、それらの押し方の中から１つ決めてボタンを押す。押したボタンが光っていれば、それらのボタンの光は消え、消えたボタンの数がプレイヤーのスコアに加算される。また、一度光ったボタンはそのボタンが押されるまで光は消えることはない。
ビート音が n 回鳴るときのボタンの光り方とプレイヤーがが習得している c 通りのボタンの押し方を入力とし、獲得することのできる得点の最大値を求める。
制約
1 ≤ n, c ≤ 30

アルゴリズム

DP.
DP[i][p]:=iターン目でパターン点灯したままの光のビットパターンがpになるときの最大スコア

コード

IntegerにbitCountってメソッドあったんですね。

import java.util.*;
public class aoj0263 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 16, DP[][] = new int[2][1<<N];
	public static void main(String[] args) {
		while (true) {
			int n = stdin.nextInt(), c = stdin.nextInt(), i = 0;
			if ((n|c) == 0) break;
			int[] a = new int[n], b = new int[c];
			for (i = 0; i < n; ++i) for (int j = 0; j < N; ++j) a[i] = (a[i]<<1) + stdin.nextInt();
			for (i = 0; i < c; ++i) for (int j = 0; j < N; ++j) b[i] = (b[i]<<1) + stdin.nextInt();
			Arrays.fill(DP[0], -1); DP[0][0] = 0;
			for (i = 0; i < n; ++i) {
				Arrays.fill(DP[(i+1)%2], -1);
				for (int j = 0; j < (1<<N); ++j) if (DP[i%2][j] != -1) {
					int on = j | a[i];
					for (int k = 0; k < c; ++k) {
						int off = on & b[k], next = on & ~off;
						DP[(i+1)%2][next] = Math.max(DP[(i+1)%2][next], DP[i%2][j] + Integer.bitCount(off));
					}
				}
			}
			int ans = 0;
			for (int x : DP[i%2]) ans = Math.max(ans, x);
			System.out.println(ans);
		}
	}
}

Finite Field Calculator(AOJ No.0264)

素数と式が与えられたときに、その素数の有限体で式を計算する。
0除算がある(割る数の逆元が存在しない)場合はNGと答える。

コード

簡単な問題なのに、入力部分をミスってruntime error出しまくった。

import java.util.*;
public class aoj0264 {
	static final Scanner stdin = new Scanner(System.in);
	static int mod;
	static String str;
	public static void main(String[] args) { 
		while (true) {
			String[] l = stdin.nextLine().split(":");
			mod = Integer.parseInt(l[0]);
			if (mod == 0) break;
			str = l[1].replace(" ", "");
			try {
				int ans = SyntacticAnalysis.calc(str);
				System.out.printf("%s = %d (mod %d)\n", str, ans, mod);
			} catch (ArithmeticException e) {
				System.out.println("NG");
			}
		}
	}
	static int negative(int a) { return (mod - a); }
	static int add(int a, int b) { return (a + b) % mod; }
	static int sub(int a, int b) { return  add(a, negative(b)); }
	static int mul(int a, int b) { return (a * b) % mod; }
	static int div(int a, int b) {
		int inverse = modInverse(b, mod);
		if (inverse == -1) throw new ArithmeticException();
		return (a * inverse) % mod;
	}
	static public class SyntacticAnalysis {
		static String eq;
		static int pos = 0;
		private static char next() { return eq.charAt(pos++); }
		public static int calc(String equation) {
			eq = equation + "$";
			pos = 0;
			return equation();
		}
		private static int equation() {
			int value = factor();
			for (char c = next(); c == '+' || c == '-'; c = next()) {
				if(c == '+') value = add(value, factor());
				else value = sub(value, factor());
			}
			--pos;
			return value;
		}
		private static int factor() {
			int value = term();
			for (char c = next(); c == '*' || c == '/'; c = next()) {
				if(c == '*') value = mul(value, term());
				else value = div(value, term());
			}
			--pos;
			return value;
		}
		private static int term() {
			char c = next();
			int value = 0;
			switch (c) {
			case '(':
				value = equation();
				c = next(); assert c == ')'; //skip ')'
				break;
			case '+':
				value = equation(); break;
			case '-':
				value = negative(equation()); break;
			default:
				if (Character.isDefined(c)) {
					while(Character.isDigit(c)) {
						value = value * 10 + (c - '0');
						c = next();
					}
					--pos;
				}
			}
			return value;
		}
	}
	public static final int modInverse(int a, int m){
		int[] x = new int[2];
		return (a > 0 && extGCD(a, m, x) == 1) ? (x[0] + m) % m : -1;
	}
	public static final int extGCD(int a, int b, int x[]){
		int g = a;
		x[0] = 1; x[1] = 0;
		if (b != 0){
			g = extGCD(b, a % b, x);
			swap(x, 0, 1);
			x[1] -= (a / b) * x[0];
		}
		return g;
	}
	public static final int[] swap(int[] x, int i, int j){
		int tmp = x[i]; x[i] = x[j]; x[j] = tmp; return x;
	}
}

Time Sale(AOJ No.0245), Bara-Bara Manju(AOJ No.0246), Ice Maze(AOJ No.0247)

リポジトリ

Time Sale(AOJ No.0245)

店のマップが横x、縦yのマスで構成される2次元 グリッドが与えられ、マスごとに通路、商品棚の どちらかが割り当てられている。
一つの商品棚には 1種類の商品があり、それは商品番号gで区別される。
同じ商品番号の商品を複数買ってはいけない。
商品棚からは、上下左右に隣接する通路のマスならどんな向きでも商品を取れる。
商品番号gによって 区別され、タイムセールの値引き額d、タイムセールの開始時刻sと売り切れ時刻eが与えられる。
時間は入店した時点で0から始まりまる。
移動は、何もないマスを４近傍で移動可能。
１回移動する毎に１単位時間経過する。商品を取る時間は考えない。
初期位置と商品のタイムセール情報を入力とし、取ることのできた商品の値引き額の合計の最大値を求める。
制約
2 < x, y < 21
0 < タイムセール情報の数n < 9

コード

座標と購入した商品のビットフィールドで一度来た場所を覚えて幅優先。
タイムセール開始前に商品がとれる位置に来た場合は、その場でまつパターンを入れてあるが、移動しないと時間経過しないのでは？
行ったり来たりして時間経過させることができるかもしれないが、そうするとその場所に到達して偶数時間たたないと元の場所に戻れない気がする。
他のルートを通って、商品の販売開始時間にその場所に到達かもしれないが、地形によってはできないこともある？
そうなると、座標と購入済み商品情報だけでなく、経過時間もあわせて既着判定しないといけないような。
なんでAcceptされたの？テストケースが緩いだけか？それともただの勘違いか？

import java.util.*;
public class aoj0245 {
	static final Scanner stdin = new Scanner(System.in);
	static final int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0}, id2idx[] = new int[10];
	static final boolean visited[][][] = new boolean[20][20][(1<<8)];
	static int W, H, N;
	public static void main(String[] args) {
		while (true) {
			W = stdin.nextInt(); H = stdin.nextInt();
			if ((W|H) == 0) break;
			char map[][] = new char[H][W];
			int sx = -1, sy = -1;
			for (int i = 0; i < H; ++i) {
				for (int j = 0; j < W; ++j) {
					Arrays.fill(visited[i][j], false);
					char c = stdin.next().charAt(0);
					if (c == 'P') { sy = i; sx = j; }
					map[i][j] = c;
				}
			}
			N = stdin.nextInt();
			Sale sale[] = new Sale[N];
			for (int i = 0; i < N; ++i) {
				int g = stdin.nextInt();
				sale[i] = new Sale(stdin.nextInt(), stdin.nextInt(), stdin.nextInt());
				id2idx[g] = i;
			}
			System.out.println(solve(sy, sx, map, sale));
		}
	}
	static int solve(int sy, int sx, char[][] map, Sale[] sale) {
		int ans = 0;
		for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) Arrays.fill(visited[i][j], false);
		Queue<State> q = new LinkedList<State>();
		q.add(new State(sy, sx, 0, 0, 0));
		visited[sy][sx][0] = true;
		while (!q.isEmpty()) {
			State p = q.poll();
			for (int i = 0; i < 4; ++i) {
				int nextY = p.y + dy[i], nextX = p.x + dx[i];
				State n = new State(p.y, p.x, p.time, p.sum, p.buy);
				if (!(0 <= nextY && nextY < H && 0 <= nextX && nextX < W) || visited[nextY][nextX][p.buy]) continue;
				if (!Character.isDigit(map[nextY][nextX])) { //move
					n.x = nextX; n.y = nextY; n.time++;
					visited[n.y][n.x][n.buy] = true;
					if (n.time <= 100) q.add(n);
					continue;
				} 
				//don't move
				int idx = id2idx[map[nextY][nextX] - '0'];
				if (!n.isPurchased(idx)) {
					switch (n.onSale(idx, sale)) {
					case 0: //on sale
						visited[n.y][n.x][n.buy] = true;
						n.buy(idx, sale);
						visited[n.y][n.x][n.buy] = true;
						ans = Math.max(ans, n.sum);
						if (!n.isAllPurchased()) q.add(n);
						break;
					case -1: //early
						n.wait(idx, sale);
						q.add(n);
						break;
					case 1: default:
					}
				}
			}
		}
		return ans;
	}
	static class State {
		int y, x, time, sum, buy;
		State(int y, int x, int time, int sum, int buy) {
			this.y = y; this.x = x; this.time = time; this.sum = sum; this.buy = buy;
		}
		boolean isPurchased(int idx) { return ((buy & (1 << idx)) != 0); }
		int onSale(int idx, Sale[] sales) {
			Sale s = sales[idx];
			return time < s.s ? -1 : s.s <= time && time < s.e ? 0 : 1;
		}
		void buy(int idx, Sale[] sales) {;
		this.buy |= (1<<idx);
		this.sum += sales[idx].d;
		}
		boolean isAllPurchased() { return buy == (1<<N)-1; }
		void wait(int idx, Sale[] sales) { this.time = sales[idx].s; }
	}
	static class Sale {
		int d = 0, s = 0, e = 0;
		Sale(int d, int s, int e) { this.d = d; this.s = s; this.e = e; }
	}
}

Bara-Bara Manju(AOJ No.0246)

１桁の自然数がn個与えられて、和が10になるグループを最大いくつつくれるかを答える。
制約
1 < n < 101

アルゴリズム

10の作り方は41個あるので、あらかじめそのパターンを作っとく。
そのパターンでDFS。
また、残っている自然数の総和sumを各イテレーションで計算しておいて、現在作られているグループの数 + が現在求まっている最大グループ数を超えた時点で枝刈りできる。
なお、正しいかどうかは証明してないけど、自然数を２つ作って10を作るパターン(1, 9), (2, 8), (3, 7), (4, 6), (5, 5)があれば、先にグループ化しておいても良さそう。

コード

import java.util.*;
public class aoj0246 {
	static final Scanner stdin = new Scanner(System.in);
	static final int twoPair[][][] = { {{1,1}, {9,1}}, {{2,1}, {8,1}}, {{3,1}, {7,1}}, {{4,1}, {6,1}}, {{5,2}}};
	static final int pair[][][] = {
			{{1, 2}, {8, 1}}, {{1,1}, {2,1}, {7,1}}, {{1,1}, {3,1}, {6,1}}, {{1,1}, {4,1}, {5,1}}, {{2,2}, {6,1}}, {{2,1}, {3,1}, {5,1}}, {{2,1}, {4,2}}, {{3,2}, {4,1}}, 
			{{1,3}, {7,1}}, {{1,2}, {2,1}, {6,1}}, {{1,2}, {3,1}, {5,1}}, {{1,2}, {4,2}}, {{1,1}, {2,2}, {5,1}}, {{1,1}, {2,1}, {3,1}, {4,1}}, {{1,1}, {3,3}}, {{2,3}, {4,1}}, {{2,2}, {3,2}}, 
			{{1,4}, {6,1}}, {{1,3}, {2,1}, {5,1}}, {{1,3}, {3,1}, {4,1}}, {{1,2}, {2,2}, {4,1}}, {{1,2}, {2,1}, {3,2}}, {{1,1}, {2,3}, {3,1}}, {{2,5}}, 
			{{1,5}, {5,1}}, {{1,4}, {2,1}, {4,1}}, {{1,4}, {3,2}}, {{1,3}, {2,2}, {3,1}}, {{1,2}, {2,4}}, 
			{{1,6}, {4,1}}, {{1,5}, {2,1}, {3,1}}, {{1,4}, {2,3}}, 
			{{1,7}, {3,1}}, {{1,6}, {2,2}}, 
			{{1,8}, {2,1}}, 
			{{1,10}}
	};
	static final int freq[] = new int[10];
	static int sum, ans, candidate;
	static boolean use(int[][] pat) {
		for (int[] f : pat) 
			if (freq[f[0]] < f[1]) return false;
		for (int i = 0; i < pat.length; ++i) freq[pat[i][0]] -= pat[i][1];
		sum -= 10; candidate++;
		return true;
	}
	static void back(int[][] pat) {
		sum += 10; candidate--;
		for (int i = 0; i < pat.length; ++i) freq[pat[i][0]] += pat[i][1];
	}
	public static void main(String[] args) {
		while (true) {
			int n = stdin.nextInt();
			if (n == 0) break;
			Arrays.fill(freq, 0);
			ans = 0; sum = 0; candidate = 0;
			while (n-- > 0) {
				int tmp = stdin.nextInt();
				freq[tmp]++;
				sum += tmp;
			}
			for (int i = 0; i < twoPair.length;) if (!use(twoPair[i])) i++;
			ans = candidate;
			DFS(0);
			System.out.println(ans);
		}
	}
	static void DFS(int prek) {
		for (int k = prek; ans < sum/10 + candidate && k < pair.length; ++k) {
			if (use(pair[k])) {
				DFS(k);
				back(pair[k]);
			}
		}
		ans = Math.max(ans, candidate);
	}
}

Ice Maze(AOJ No.0247)

平原、山、氷の属性があるx×yのマップが与えられ、スタート地点からゴール地点まで４近傍移動できる。（スタートとゴールは平原）
平原は移動可能、山は移動不可能、氷は４近傍で一つの氷としてつながっており、氷の面積の半分を超える回数移動するとその氷が割れて、ガメオベラ。
ゴールに到達するまでに掛かる最小の移動回数を求める。
制約
1 < x, y < 13

アルゴリズム

地形によってはかなり遠回りしないと行けなさそうなので、IDDFSとかやってみようとおもった。
氷ははじめにグループ化しておき、グループ毎に耐久度を覚えとく。
まだ、計算量が心配だったので、Iterative Deepneing A*:IDA*。
ヒューリスティック関数h*はゴールまでのマンハッタン距離でもいいかもしれないが、氷が無いときのゴールまでの最短距離をh*とした。
はじめに、ゴール地点からBFSして求めとけば良いだけだし、こちらの方が制限が強くて早めにバックトラックできるはず。
また、周りが既に到達済み（前にいた位置を除く）の場合は、無駄に迂回しているので枝刈り。
現在位置または近傍が氷の場合(氷を迂回する場合)でも、４近傍で氷がつながっているので、無駄に氷を踏んで耐久度を下げてることになる。
なのでこの枝刈りは正しいはず。

コード

デバッグめんどかった。

import java.util.*;
public class aoj0247 {
	static final Scanner stdin = new Scanner(System.in);
	static int W, H, sidx, gidx, lim;
	static final char map[] = new char[12*12];
	static final boolean visited[] = new boolean[12*12];
	static final int dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1}, INF = Integer.MAX_VALUE/2;
	static final int hstar[] = new int[12*12], hardness[] = new int[12*12], ice[] = new int[12*12];
	public static void main(String[] args) {
		while (true) {
			W = stdin.nextInt(); H = stdin.nextInt();
			if ((W|H) == 0) break;
			for (int i = 0; i < H; ++i) {
				String s = stdin.next();
				for (int j = 0; j < W; ++j) {
					char c = s.charAt(j);
					int idx = index(i,j);
					map[idx] = c;
					switch(c) {
					case 'S': sidx = index(i, j); map[idx] = '.'; break;
					case 'G': gidx = index(i, j); map[idx] = '.'; break;
					}
				}
			}
			calcHStar(gidx);
			Arrays.fill(hardness, 0); Arrays.fill(ice, -1);
			int iceNum = 0;
			for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) {
				int idx = index(i,j);
				if (map[idx] == 'X' && ice[idx] == -1) {
					discoverIce(idx, iceNum); 
					hardness[iceNum] /= 2;
					iceNum++;
				}
			}
			Arrays.fill(visited, false); visited[sidx] = true;
			for (lim = 0; !IDAStar(0, sidx, sidx) ;lim++);
			System.out.println(lim);
		}
	}
	static void calcHStar(int s) { //WFS
		Arrays.fill(hstar, INF);
		Queue<Integer> q = new LinkedList<Integer>();
		hstar[s] = 0;
		q.add(s);
		while(!q.isEmpty()){
			int v = q.poll();
			for(int k = 0; k < 4; ++k) {
				int ny = getY(v) + dy[k], nx = getX(v) + dx[k], nv = index(ny, nx);
				if(inRange(ny, nx) && (map[nv] == '.' || map[nv] == 'X') && hstar[nv] > hstar[v] + 1){
					hstar[nv] = hstar[v]+1;
					q.add(nv);
				}
			}
		}
	}
	static void discoverIce(int pos, int id) { //WFS
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(pos); ice[pos] = id; hardness[id]++;
		while (!q.isEmpty()) {
			int v = q.poll();
			for (int k = 0; k < 4; ++k) {
				int ny = getY(v) + dy[k], nx = getX(v) + dx[k], npos = index(ny, nx);
				if (inRange(ny, nx) && map[npos] == 'X' && ice[npos] == -1) {
					q.add(npos); ice[npos] = id; hardness[id]++;
				}
			}
		}
	}
	static boolean IDAStar(int depth, int pos, int prepos) {
		if (pos == gidx) return true;
		if (depth + hstar[pos] > lim) return false;
		for (int k = 0; k < 4; ++k) { //前にいた位置を除いて、周りが既に到達済みならバックトラック
			int ny = getY(pos) + dy[k], nx = getX(pos) + dx[k], npos = index(ny, nx);
			if (!inRange(ny, nx) || npos == prepos) continue;
			if (visited[npos]) return false;
		}
		for (int k = 0; k < 4; ++k) {
			int ny = getY(pos) + dy[k], nx = getX(pos) + dx[k], npos = index(ny, nx);
			if (!inRange(ny, nx) || visited[npos]) continue;
			boolean nextIce = (map[npos] == 'X');
			if (nextIce || map[npos] == '.') {
				if (nextIce && hardness[ice[npos]] <= 0) continue;
				if (nextIce) hardness[ice[npos]]--; 
				visited[npos] = true;
				if (IDAStar(depth+1, npos, pos)) return true;
				if (nextIce) hardness[ice[npos]]++; 
				visited[npos] = false;
			}
		}
		return false;
	}
	static int getX(int index) { return index%W; }
	static int getY(int index) { return index/W; }
	static int index(int y, int x) { return y * W + x; }
	static boolean inRange(int y, int x) { return 0 <= y && y < H && 0 <= x && x < W; }
}

Time to Study(AOJ No. 0238), Calorie Counting(AOJ No. 0239), Interest Rates(AOJ No. 0240), Quaternion Multiplication(AOJ No. 0241), Input Candidates(AOJ No. 0242), Filling Game(SOJ No. 0243), Hot Spring Trip(AOJ No. 0244)

リポジトリ

Time to Study(AOJ No. 0238)

要するにが与えられて、かどうかを答える。

コード

import java.util.*;
public class aoj0238 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while (true) {
			int t = stdin.nextInt();
			if (t == 0) break;
			int n = stdin.nextInt();
			while (n-- > 0) t += (stdin.nextInt() - stdin.nextInt());
			System.out.println(t <= 0 ? "OK" : t);
		}
	}
}

Calorie Counting(AOJ No. 0239)

要するにP, Q, R, C, nとn個のレコード(i p q r)が与えられて、を満たしている場合iを出力する。
満たしている物が一つもない場合はNAと答える。

コード

import java.util.*;
public class aoj0239 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while (true) {
			int n = stdin.nextInt();
			if (n == 0) break;
			List<int[]> l = new ArrayList<int[]>();
			while (n-- > 0) {
				int[] a = { stdin.nextInt(), stdin.nextInt(), stdin.nextInt(), stdin.nextInt(), 0 };
				a[4] = 4 * a[1] + 9 * a[2] + 4 * a[3];
				l.add(a);
			}
			int b[] = {0, stdin.nextInt(), stdin.nextInt(), stdin.nextInt(), stdin.nextInt()};
			boolean f = true;
			LOOP: for (int[] a : l) {
				for (int i = 1; i < a.length; ++i) if (a[i] > b[i]) continue LOOP;
				System.out.println(a[0]); f = false;
			}
			if (f) System.out.println("NA");
		}
	}
}

Interest Rates(AOJ No. 0240)

要するに年数とnとn個のレコード(銀行番号、金利の種類(単利 or 複利)、年利率(%)）が与えられて、最も元利が高くなる銀行番号を答える。
元利が最大となる銀行は１つしかない。

コード

import java.util.*;
public class aoj0240 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while (true) {
			int n = stdin.nextInt();
			if (n == 0) break;
			int y = stdin.nextInt(), ans = -1;
			double max = -1, charge = -1;
			while (n-- > 0) {
				int b = stdin.nextInt(), r = stdin.nextInt(), t = stdin.nextInt();
				charge = t == 1 ? (1 + y * r/100.) : Math.pow(1 + r/100., y);
				if (charge > max) { max = charge; ans = b; }
			}
			System.out.println(ans);
		}
	}
}

Quaternion Multiplication(AOJ No. 0241)

４元数(Quaternion)が２つ与えられて、その積を答える。

コード

import java.util.*;
public class aoj0241 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while (true) {
			int n = stdin.nextInt();
			if (n == 0) break;
			while (n-- > 0) {
				int x1 = stdin.nextInt(), y1 = stdin.nextInt(), z1 = stdin.nextInt(), w1 = stdin.nextInt(), x2 = stdin.nextInt(), y2 = stdin.nextInt(), z2 = stdin.nextInt(), w2 = stdin.nextInt();
				System.out.println(String.format("%d %d %d %d", x1*x2 - y1*y2 - z1*z2 - w1*w2, x1*y2 + y1*x2 + z1*w2 - w1*z2, x1*z2 - y1*w2 + z1*x2 + w1*y2, x1*w2 + y1*z2 - z1*y2 + w1*x2));
			}
		}
	}
}

Input Candidates(AOJ No. 0242)

アルファベットの単語列とアルファベットcが与えられて、頭文字がcの単語列のうち最も出現頻度が高い物を答える。該当単語が複数ある場合は、辞書順で答える。

コード

import java.util.*;
public class aoj0242 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while (true) {
			int n = stdin.nextInt();
			if (n == 0) break;
			stdin.nextLine();
			Map<String, Integer> freq = new HashMap<String, Integer>();
			while (n-- > 0) for (String s : stdin.nextLine().split(" ")) freq.put(s, (freq.containsKey(s) ? freq.get(s) : 0) + 1);
			char ch = stdin.next().charAt(0);
			List<T> l = new ArrayList<T>();
			for (Map.Entry<String, Integer> e : freq.entrySet()) if (e.getKey().charAt(0) == ch) l.add(new T(e.getKey(), e.getValue()));
			StringBuilder sb = new StringBuilder();
			if (l.isEmpty()) sb.append(" NA");
			else Collections.sort(l);
			for (T t : l) sb.append(" ").append(t.str);
			System.out.println(sb.substring(1));
		}
	}
	static class T implements Comparable<T>{
		String str; int freq;
		T(String s, int f) { str = s; freq = f; }
		@Override public int compareTo(T o) { return freq != o.freq ? o.freq - freq : str.compareTo(o.str); }
	}
}

Filling Game(SOJ No. 0243)

画面にはx列×y行の2次元グリッドが与えられる。

• グリッドのセルは赤(R)、緑(G)、茶(B)の3色のいずれかで塗られている。
• セルの色を変更するボタンR、G、Bがあり、このボタンが押下されると一番左上(0,0)のセルがその色に変更される。
• 一番左上のセルの色が変更されると、そのセルの元の色と同じ色に塗られた隣接するすべてのセルが指定された色に変わる(元の色が同じ色のセルでつながったセルはすべて指定された色に変更される)。

すべてのセルを同一色にするために必要な選択ボタンの操作回数の最小値を出力する。
制約
1 < x,y < 11

アルゴリズム

深さ、計算量の見積もりができなかったので、反復深化深さ優先探索（IDDFS: Iterative Deepening Depth-First Search）で解いた。
分岐係数をb, 深さをdとすると、IDDFSの空間計算量はO(bd), 時間計算量は。
この問題の場合、現在の(0, 0)の色と同じ色のボタンを押しても意味が無いので、他の２色のボタンを押すことになり、b=2となる。
また、色を変える操作がO(xy)なので、時間計算量は程度?

コード

java.awt.Point使ってやってたら、Memory Limit Exceededになったので、x, yをint変数一つで表すように変更した。
結局深さはどんくらいなのかな?

import java.util.*;
public class aoj0243 {
	static final Scanner stdin = new Scanner(System.in);
	static int W, H, lim;
	static final char map[][] = new char[20][20];
	static final int dx[] = {-1, 1, 0, 0};
	static final int dy[] = {0, 0, -1, 1};
	public static void main(String[] args) { 
		while (true) {
			W = stdin.nextInt(); H = stdin.nextInt();
			if ((W|H) == 0) break;
			for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) map[i][j] = stdin.next().charAt(0);
			for (lim = 0; !rec(0); ++lim);
			System.out.println(lim);
		}
	}
	static boolean rec(int depth) {
		char precolor = map[0][0];
		if (check()) return true;
		if (depth >= lim) return false;
		for (char color : "RGB".toCharArray()) {
			if (color == precolor) continue;
			List<Integer> list = new ArrayList<Integer>();
			changeColor(0, 0, color, list);
			if (rec(depth + 1)) return true;
			for (int p: list) map[p/W][p%W] = precolor;
		}
		return false;
	}
	static boolean check() {
		char c = map[0][0];
		for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) if (map[i][j] != c) return false;
		return true;
	}
	static void changeColor(int y, int x, char color, List<Integer> list) {
		char precolor = map[y][x];
		map[y][x] = color;
		list.add(y*W+x);
		for (int k = 0; k < 4; ++k) {
			int nx = x + dx[k], ny = y + dy[k];
			if (0 <= nx && nx < W && 0 <= ny && ny < H && map[ny][nx] == precolor) changeColor(ny, nx, color, list);
		}
	}
}

Hot Spring Trip(AOJ No. 0244)

出発地、目的地、及び中継地点の総数nと路線の数m、路線の接続情報、各区間の料金とスタートおよびゴールのバス停が与えられる。
好きな２区間を無料にすることができる。途中で目的地を通過しても、目的地にたどり着いたことにはならない。
出発地から目的地にたどり着くのに必要な最低料金を答える。
制約
出発地から目的地までの経路は必ず存在する。
1 < n < 101
0 < 区間料金 < 1, 001

アルゴリズム

チケットの使用状況と、現在位置を状態として持ったDijkstra。チケット使って途中下車しないように注意するだけ。

コード

import java.util.*;
public class aoj0244 {
	static final Scanner stdin = new Scanner(System.in);
	static final int INF = Integer.MAX_VALUE/2, T = 2;
	public static void main(String[] args) {
		while (true) {
			int n = stdin.nextInt(), m = stdin.nextInt();
			if ((n|m) == 0) break;
			List<List<Edge>> adjList = new ArrayList<List<Edge>>();
			for (int i = 0; i < n; ++i) adjList.add(new ArrayList<Edge>());
			for (int i = 0; i < m; ++i) {
				int src = stdin.nextInt()-1, dst = stdin.nextInt()-1, cost = stdin.nextInt();
				adjList.get(src).add(new Edge(dst, cost, 0));
				adjList.get(dst).add(new Edge(src, cost, 0));
			}
			System.out.println(solve(adjList));
		}
	}
	public static int solve(List<List<Edge>> list) {
		int n = list.size();
		int[][] dist = new int[T+1][n]; 
		for(int i = 0; i <= T; ++i) Arrays.fill(dist[i], INF);
		PriorityQueue<Edge> q = new PriorityQueue<Edge>();
		dist[T][0] = 0;
		q.add(new Edge(0, 0, T));
		while(!q.isEmpty()){
			Edge p = q.poll();
			int v = p.dst;
			if(dist[p.ticket][v] < p.cost) continue;
			if(v == n-1 && p.ticket != 1) return p.cost;
			if (1 <= p.ticket) for(final Edge u: list.get(v)) { 
				int newTicket = p.ticket - 1, newDist = dist[p.ticket][v];
				if(dist[newTicket][u.dst] > newDist){
					dist[newTicket][u.dst] = newDist;
					q.add(new Edge(u.dst, newDist, newTicket));
				}
			}
			if (p.ticket != 1) for(final Edge u: list.get(v)) { 
				int newTicket = p.ticket, newDist = dist[p.ticket][v] + u.cost;
				if(dist[newTicket][u.dst] > newDist){
					dist[newTicket][u.dst] = newDist;
					q.add(new Edge(u.dst, newDist, newTicket));
				}
			}
		}
		return INF;
	}
	static class Edge implements Comparable<Edge>{
		int dst, cost, ticket;
		Edge(int dst, int cost, int ticket){ this.dst = dst; this.cost = cost; this.ticket = ticket; }
		@Override public int compareTo(Edge o) {
			return cost != o.cost ? cost - o.cost : ticket != o.ticket ? o.ticket - ticket : dst - this.dst;
		}
	}
}

The Last Door(AOJ No.0237)

リポジトリ

The Last Door(AOJ No. 0237)

n個の２等辺三角形の座標(頂点座標x3)と 光の伸びる長さ dが与えられる。
2等辺三角形の底辺の長さをlとする。
三角形に触れると点灯し、底辺から底辺を含まない頂点に向かって、l×dの長方形の光がでる。
その光が他の三角形に当たると、連鎖して当たった三角形も点灯し光を放つ。
全ての三角形を点灯させるのに必要な、三角形に触れる回数の最小値を求める。
制限
与えられる２等辺三角形に正三角形はない。
光はそれを放つ三角形の頂点を含むような十分な長さを持つ。
0 < d < 1,001
0 < n < 101
三角形の頂点の座標は
2 点の距離が 0.01 以下の場合には、同一の点と処理する。
1 点とひとつの直線の距離が 0.01 以下の場合には、この点はこの直線上にあるとして処理する。

アルゴリズム

与えられた２等辺三角形をノードとして、ある三角形i'に触れると、１連鎖で点灯させることができる三角形jへのアークを持つ有向グラフを作る。
それを強連結成分分解して、強連結成分を１つの頂点に縮約しDAGを考える。
このDAGのうち入次数が0の強連結成分の数が触れる回数の最小値。

有向グラフを作るにあたっては、以下のことに気をつける。
長方形の光(の頂点座標)は、底辺の正規化法線ベクトルを±d倍して求める。法線ベクトルの向きに気をつけて符号を決める。
長方形(の光)iが他の三角形jを点灯させられる(i'からjへのアークがある)のは以下の場合

• iの辺とjの辺のが交差している(線分の交差判定)
• iがjの頂点を含んでいる または jがiの頂点を含んでいる(多角形と点の包含判定)
• iの辺とjの頂点との距離が0.01以下 または jの辺とiの頂点との距離が0.01以下(点と線分の距離)

コード

検証用のコードが入ってます。

import java.awt.geom.Point2D;
import java.util.*;
public class aoj0237 {
	static final Scanner stdin = new Scanner(System.in);
	static final double eps = 0.01;
	enum SCCMethod {
		DFS1 { 
			@Override List<Set<Integer>> getSCC(List<List<Edge>> adjList) { return getStronglyConnectedComponents(adjList);} 
		}, DFS2 {
			@Override List<Set<Integer>> getSCC(List<List<Edge>> adjList) { return Kosaraju(adjList);} 
		};
		List<Set<Integer>> getSCC(List<List<Edge>> adjList) { return null; }
	}
	static SCCMethod method = SCCMethod.DFS2;
	public static void main(String[] args) {
		while (true) {
			int n = stdin.nextInt(), d = stdin.nextInt();
			if ((n|d) == 0) break;
			T[] data = new T[n];
			List<List<Edge>> adjList = new ArrayList<List<Edge>>();
			for (int i = 0; i < n; ++i) {
				data[i] = new T(new Point[]{
						new Point(stdin.nextDouble(), stdin.nextDouble()), 
						new Point(stdin.nextDouble(), stdin.nextDouble()), 
						new Point(stdin.nextDouble(), stdin.nextDouble())
				}, d);
				adjList.add(new ArrayList<Edge>());
			}
			for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
				if (i == j) continue;
				if (data[i].canConnect(data[j])) {
					adjList.get(i).add(new Edge(i, j));
				}
			}
			List<Set<Integer>> sccs = method.getSCC(adjList);
			int k = sccs.size(), ans = 0, SCC[] = new int[n], indeg[] = new int[k];
			for (int i = 0; i < k; ++i) for (Integer v: sccs.get(i)) SCC[v] = i;
			for (List<Edge> l : adjList) for (Edge e : l) if (SCC[e.s] != SCC[e.d]) indeg[SCC[e.d]]++;
			for (int deg : indeg) if (deg == 0) ans++;
			System.out.println(ans);
		}
	}
	static class T {
		Line base, top;
		Point vertex;
		T(Point points[], int d) {
			//Line[] l = {new Line(p1, p2), new Line(p2, p3), new Line(p3, p1) };
			for (int i = 0; i < 3; ++i) {
				if (equal(points[i].distance(points[(i+1)%3]), points[i].distance(points[(i+2)%3]))) {
					vertex = points[i];
					base = new Line(points[(i+1)%3], points[(i+2)%3]);
					Point nv = base.end.sub(base.start).normalVector();
					int sign = 1;
					if (base.ccw(vertex) < 0) { sign = -1; }
					nv = nv.mul(sign * d);
					top = new Line(base.end.add(nv), base.start.add(nv));
					return;
				}
			}
		}
		boolean canConnect(T t) {
			Line rect[] = { base, new Line(base.end, top.start), top, new Line(top.end, base.start) };
			Line tri[] = { t.base, new Line(t.base.end, t.vertex), new Line(t.vertex, t.base.start) };
			for (Line l1 : tri) for (Line l2 : rect) if (l1.intersectsSS(l2)) return true;
			Point prect[] = { base.start, base.end, top.start, top.end };
			Point ptri[] = { t.base.start, t.base.end, t.vertex };
			for (Point p: ptri) {
				if (contains(prect, p)) return true;
				for (Line l: rect) if (p.distancePS(l) <= eps) return true;
			}
			for (Point p: prect) {
				if (contains(ptri, p)) return true;
				for (Line l: tri) if (p.distancePS(l) <= eps) return true;
			}
			return false;
		}
	}

	//geom
	public static final double EPS = 1e-10;
	public static boolean equal(double a, double b){ return Math.abs(a-b) < EPS; }
	public static boolean less(double a, double b){ return a - b < -EPS; }
	public static boolean greater(double a, double b){ return less(b,a); }
	public static boolean leq(double a, double b){ return a - b < EPS; }
	@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 norm(){ return Math.sqrt( normsq() ); }
		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 Point div(double k){ return new Point( x/k, y/k ); }
		public final Point normalVector(){
			double d = this.norm();
			return new Point(-y/d, x/d);
		}
		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)
		}
		public final Point projection(Line l){
			Point a = l.dirV();
			Point b = this.sub(l.start);
			return l.start.add(a.mul(a.dot(b)/a.normsq()));
		}
		public final double distancePS(Line s){
			Point proj = projection(s);
			return proj.intersectsPS(s) ? distance(proj) : Math.min(distance(s.start), distance(s.end));
		}
		public final boolean intersectsPS(Line s) {
			//return s.ccw(this) == 0; //これでもおk
			return equal(s.start.distance(this) + this.distance(s.end), s.end.distance(s.start)); //三角不等式で等号が成り立つとき
		}
	} //class Point
	public static class Line{
		private final Point start, end;
		public Line(Point start, Point end){ this.start = new Point(start); this.end = new Point(end); }
		public final int ccw(Point p){ return start.ccw(end, p); }
		public Point dirV() { return end.sub(start); } //directional vector
		public final boolean intersectsSS(Line t) {
			return ccw(t.start) * ccw(t.end) <= 0 && t.ccw(start) * t.ccw(end) <= 0;
		}
	} //class Line
	public static boolean contains(Point[] polygon, Point p) {
		boolean in = false;
		for (int i = 0, n = polygon.length; i < n; ++i) {
			Point a = polygon[i].sub(p), b = polygon[(i+1)%n].sub(p);
			if (a.y > b.y){ Point temp = b; b = a; a = temp; }
			if (a.y <= 0 && 0 < b.y) 
				if (a.cross(b) < 0) in = !in; //=0 -> a//b -> on 
			if (equal(a.cross(b), 0) && leq(a.dot(b), 0)) return true; //on edge
		}
		return in; //in out
	}

	//scc
	public static class Edge {
		protected int s, d;
		public Edge(int s, int d){ this.s = s; this.d = d; }
	}
	public static List<List<Edge>> inverseAdjacencyList(List<List<Edge>> adjList) {
		int n = adjList.size();
		List<List<Edge>> ret = new ArrayList<List<Edge>>();
		for (int i = 0; i < n; ++i) ret.add(new ArrayList<Edge>());
		for (List<Edge> l : adjList) for (Edge e : l) ret.get(e.d).add(new Edge(e.d, e.s));
		return ret;
	}
	private static class SCCDFSArg {
		int num = 0;
		Stack<Integer> stack = new Stack<Integer>();
		boolean[] used;
		List<List<Edge>> adjList;
		SCCDFSArg(int numV, List<List<Edge>> adjList) { used = new boolean[numV]; this.adjList = adjList; }
	}
	public static List<Set<Integer>> Kosaraju(List<List<Edge>> adjList) {
		int n = adjList.size();
		SCCDFSArg arg = new SCCDFSArg(n, adjList);
		for (int v = 0; v < n; ++v) if (!arg.used[v]) postOrderNumbering(v, arg);

		Arrays.fill(arg.used, false);
		arg.adjList = inverseAdjacencyList(adjList);
		List<Set<Integer>> ret = new ArrayList<Set<Integer>>();
		while (!arg.stack.isEmpty()) {
			int v = arg.stack.pop();
			if (!arg.used[v]) {
				Set<Integer> scc = new HashSet<Integer>();
				addSCC(v, arg, scc);
				ret.add(scc);
				arg.num++; //group number
			}
		}
		return ret;
	}
	private static void postOrderNumbering(int v, SCCDFSArg arg) {
		arg.used[v] = true;
		for (Edge e : arg.adjList.get(v)) if (!arg.used[e.d]) postOrderNumbering(e.d, arg);
		arg.stack.push(v);
	}
	private static void addSCC(int v, SCCDFSArg arg, Set<Integer> scc) {
		arg.used[v] =  true;
		scc.add(v);
		for (Edge e : arg.adjList.get(v)) if (!arg.used[e.d]) addSCC(e.d, arg, scc);
	}
	public static List<Set<Integer>> getStronglyConnectedComponents(List<List<Edge>> adjList) {
		ArrayList<Set<Integer>> ret = new ArrayList<Set<Integer>>();
		int n = adjList.size();
		int[] num = new int[n], low = new int[n];
		SCCDFSArg arg = new SCCDFSArg(n, adjList);
		for (int v = 0; v < n; ++v) if (num[v] == 0) sccDFS(v, arg, low, num, ret);
		return ret;
	}
	private static void sccDFS(int v, SCCDFSArg arg, int[] low, int[] num, List<Set<Integer>> SCCs) {
		low[v] = num[v] = ++arg.num; //num[v]:= topological number of v. low[v]:= minimum topological number in SCC including v. 
		arg.stack.push(v); arg.used[v] = true; //used[v] := whether arg.S contains v or not.
		for (Edge e: arg.adjList.get(v)) {
			if (num[e.d] == 0) { //case: e.d is non visited vertex
				sccDFS(e.d, arg, low, num, SCCs);
				low[v] = Math.min(low[v], low[e.d]);
			} else if (arg.used[e.d]) { //arg.used[e.d] == false -> has already created scc containing e.d. 
				low[v] = Math.min(low[v], num[e.d]);
			}
		}
		if (low[v] == num[v]) { 
			HashSet<Integer> scc = new HashSet<Integer>();
			int sccV = 0;
			do {
				sccV = arg.stack.pop(); arg.used[sccV] = false;
				scc.add(sccV);
			} while (v != sccV);
			SCCs.add(scc);
		}
	}
}

Eclipseの設定

mac版のeclipseのデフォルトエンコーディングがShift-JISになってるので、eclipse.iniに

-Dfile.encoding=utf-8

を追加しとくと安心。
これやってないと、プロジェクトをインポートするときめんどくさいことになる。

フォント/サイズは、Eclipseの環境設定で変更できるが、
プロジェクトエクスプローラとかのフォントサイズを変更する設定項目が見つからない（用意されていない?）
eclipse.ini中の

-Dorg.eclipse.swt.internal.carbon.smallFonts

をコメントアウトすると、多少大きく表示されるみたい。
※-Dorg.eclipse.swt.internal.carbon.smallFontsの記述が２個ある。
しかし、なぜ２個あるのか、ｺﾚｶﾞﾜｶﾗﾅｲ。

一応、eclipse.iniを編集したら-cleanオプションをつけて再起動して下さい! オナシャス!!