kanetaiの二次記憶装置

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

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

Online judge

リポジトリ

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)

数列 h_i (1\leq i \leq n+1)が与えられる。ある数を１つ除くと等差数列になるので、その数を答える。

コード

全探索。めんどいから。

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になるときの最大スコア
O(2^{16}nc)\rightarrow 58,982,400

コード

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;
	}
}