2010-03-13

■ [others]Maximum Winter-Contest 2010 01:56

Maximumのコンテストは初めて参加しました。

陰険なコンテストとの呼び声が高いですが、あまりそのような感じはしませんでした。

ぱっと見ではわからないけれど時間をかけて考えて試していたら徐々に見えてくる、というセットで、5時間最後まで進展があったのが楽しかったです。

ログ

• A
  • わからん
  • 簡単なものから並んでるわけじゃないのね
  • とりあえず全部読もう
• G
  • ただのgreedyにしか見えない
  • 「g_i個以上」の意図がわからなかったが気にせず書いてみる
  • 通った
• I
  • 2^10通りの組み合わせを調べるだけにしか見えなかったので書く
  • WA
  • さすがに最後の問題がそんな簡単なはずがない、と思ってよーく問題を読む
  • 解釈を間違っていたことに気づいた
  • 買ったセットの中からカードを何枚か捨ててもいいんですね
  • なるほど、わからん。他へ移ろう
• D
  • これはやりさえすればできそう
  • 問題文にはっきり書いてないけど、入力に小数もありえるんですよね…？
  • 幾何は好きじゃないが、頑張って3点を通る円の中心を求めるなどする
  • WA
  • デバッグすると計算途中で1か所符号が逆になっていることを発見
  • まだWA
  • 誤差かなぁ
  • 有理数で扱おうにも入力が小数だと無理だし
  • テキトーにEPS入れてみた
  • 通った
• C
  • たくさん解いてる人いる
  • 単純な解法としてはnext_permutationで全通り調べるというのがあるのだけど、計算量大丈夫なのか
  • とりあえず書いてみた
  • 通った
• A
  • けっこう解いてる人がいるのでこれは通したい
  • 魔力の上限が10万とかだったらDPできるのだが2^46とは…
  • ひとまず単純に枝刈り探索してみた
  • やっぱりTLE
  • 手元でランダム最大ケース作って試してみても返ってこない
  • DP的解法をいろいろ考えるも、魔力の範囲が大きいので前の計算結果を使えるよう覚えておこうとすると記憶容量が足りない
  • やっぱり探索か
  • あ…この問題、ITmediaのアルゴリズマー連載でやった所だ！
  • N>20の部分だけ前計算で全探索してメモっておく
  • デバッグサブミットするくらいの気持ちで、ささっと書いたコードを投げてみたら、なんと一発で通った。これはうれしい
  • しかし2.5秒かかっているので作意解は別にあるのかも
• 残ったもので何人かが解いてるのはEとHがあるが、フローやグラフはよくわからないのでHを選択
  • とりあえず単純な幅優先探索を書いてみてTLEになることを確認
    • 手元でもランダム最大ケースは返ってこない
  • 何かうまい方法がないか考えるもわからない
  • しかし状態数10!（380万くらい）しかないのだから、幅優先でも最適化すればいけるんじゃないかと思うのだが…
  • 文字列処理が遅いんだろうので何とかできないか
  • そうか、文字数が最大10なので、1文字4ビットで扱って文字列を64bit整数にエンコードできるのか
  • Stringで扱ってたのをlongに書き直してみた
  • ランダム最大ケースが5秒くらいで終わるようになった。現実的な数字だがまだ不十分
  • あ、これ両側探索できるやん。やってみよう
  • 通った。両側探索偉大だなぁ

手を付けなかった問題について

• B
  • 大気がある高さのときに条件を満たすような橋のかけ方があるかどうか簡単に（O(NlogN)くらいで）判定できれば、大気の高さに関する二分探索でいけそうだが
  • Clarが出てるのを終了間際まで気づいてなかった…
  • 橋を全部使うのなら、判定はUnion-Find使えば簡単なのかな
• E
  • うーん…ワーシャルフロイドとか？
  • SRMだったら答えが0になるケースでいっぱい落とせそう
• F
  • 整数の積の和がFFTで高速に計算できる、というやつ？

結果

• AC：9問中5問
• ペナルティタイム：954分
• 順位：たぶん6位か7位あたり → 6位でした

M-Judgeで開催されるコンテストはなぜか実力以上の結果が出ます（サンプル数2）

コード

【追記 2010-03-14 23:24】

解いたやつのコードを載っけておきます。コメントは後から付けたもの

• A

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class A {
	static Scanner sc = new Scanner(System.in);
	static long ans = 0;
	static long[] restL;
	static long[] restG;
	static long[] l;
	static long[] g;
	static long C;
	static int N;
	static ArrayList sts;
	static ArrayList memoL;
	static ArrayList memoG;

	public static void main(String[] args) throws Exception {
		N = sc.nextInt();
		C = sc.nextLong();
		while (N > 0 || C > 0) {
			l = new long[N];
			g = new long[N];
			for (int i = 0; i < N; ++i) {
				l[i] = sc.nextLong();
			}
			for (int i = 0; i < N; ++i) {
				g[i] = sc.nextLong();
			}
			// 枝刈り用
			restL = new long[N];
			restG = new long[N];
			long sumL = 0;
			long sumG = 0;
			for (int i = 0; i < N; ++i) {
				sumL += l[N - 1 - i];
				restL[N - 1 - i] = sumL;
				sumG += g[N - 1 - i];
				restG[N - 1 - i] = sumG;
			}
			sts = new ArrayList();
			memoL = new ArrayList();
			memoG = new ArrayList();
			if (N > 20) {
				rec2(20, 0, 0);
				Collections.sort(sts);
				// long prevL = -1;
				// for (int i = 0; i < sts.size(); ++i) {
				// 	if (sts.get(i).l == prevL) continue;
				// 	memoL.add(sts.get(i).l);
				// 	memoG.add(sts.get(i).g);
				// 	prevL = sts.get(i).l;
				// }
				// ↑本番で提出したコード
				// これだと、次のケースに対して202を返してしまう（期待値は203）ので間違い
				// 22 23
				// 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  2 3
				// 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 3 2

				// その消費量以下で集められる魔力の最大値を覚えておく
				long maxG = -1;
				for (int i = 0; i < sts.size(); ++i) {
					if (sts.get(i).g <= maxG) continue;
					maxG = sts.get(i).g;
					memoL.add(sts.get(i).l);
					memoG.add(sts.get(i).g);
				}
			}
			ans = 0;
			rec(0, 0, 0);
			System.out.println(ans);
			N = sc.nextInt();
			C = sc.nextLong();
		}
	}

	static void rec2(int index, long got, long lose) {
		if (lose > C) return;
		if (index == N) {
			sts.add(new St(got, lose));
			return;
		}
		rec2(index + 1, got, lose);
		rec2(index + 1, got + g[index], lose + l[index]);
	}

	static void rec(int index, long got, long lose) {
		if (lose > C) return;
		if (index == N) {
			ans = Math.max(ans, got);
			return;
		}
		if (index == 20) {
			long rest = C - lose;
			int i = Collections.binarySearch(memoL, rest);
			long cand = 0;
			if (i < 0) i = -i - 2;
			if (i < 0) {
				cand = got;
			} else if (i == memoG.size()) {
				cand = got + memoG.get(memoG.size() - 1);
			} else {
				cand = got + memoG.get(i);
			}
			ans = Math.max(ans, cand);
			return;
		}

		// 枝刈り
		if (restL[index] + lose <= C) {
			ans = Math.max(ans, got + restG[index]);
			return;
		}
		if (got + restG[index] <= ans) return;

		rec(index + 1, got, lose);
		rec(index + 1, got + g[index], lose + l[index]);
	}

	static class St implements Comparable {
		long g;
		long l;

		St(long g, long l) {
			this.g = g;
			this.l = l;
		}

		public int compareTo(St o) {
			if (this.l > o.l) return 1;
			if (this.l < o.l) return -1;
			if (this.g < o.g) return 1;
			if (this.g > o.g) return -1;
			return 0;
		}
	}

}

• C

import java.util.Arrays;
import java.util.Scanner;

public class C {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) throws Exception {
		int T = sc.nextInt();
		for (int i = 0; i < T; ++i) {
			int N = sc.nextInt();
			int M = sc.nextInt();
			int[] S = new int[N];
			int[][] A = new int[N][M];
			for (int j = 0; j < N; ++j) {
				for (int k = 0; k < M; ++k) {
					A[j][k] = sc.next().charAt(0) - 'A';
				}
				S[j] = sc.nextInt();
			}
			int[] ans = new int[26];
			for (int j = 0; j < M; ++j) {
				ans[26 - 1 - j] = 1;
			}
			int c = 0;
			do {
				boolean valid = true;
				for (int j = 0; j < N; ++j) {
					int match = 0;
					for (int k = 0; k < M; ++k) {
						if (ans[A[j][k]] == 1) ++match;
					}
					if (match != S[j]) {
						valid = false;
						break;
					}
				}
				if (valid) ++c;
			} while (nextPermutation(ans));
			System.out.println(c);
		}
	}

	public static boolean nextPermutation(int[] a) {
		for (int i = a.length - 1; i > 0; --i) {
			if (a[i - 1] < a[i]) {
				int swapIndex = find(a[i - 1], a, i, a.length - 1);
				int temp = a[swapIndex];
				a[swapIndex] = a[i - 1];
				a[i - 1] = temp;
				Arrays.sort(a, i, a.length);
				return true;
			}
		}
		return false;
	}

	private static int find(int dest, int[] a, int s, int e) {
		if (s == e) {
			return s;
		}
		int m = (s + e + 1) / 2;
		return a[m] <= dest ? find(dest, a, s, m - 1) : find(dest, a, m, e);
	}

}

• D

import java.util.Scanner;

public class D {
	static Scanner sc = new Scanner(System.in);
	static int N;
	static final double EPS = 1e-9;

	public static void main(String[] args) throws Exception {
		N = sc.nextInt();
		while (N > 0) {
			double[] x = new double[N];
			double[] y = new double[N];
			for (int i = 0; i < N; ++i) {
				x[i] = sc.nextDouble();
				y[i] = sc.nextDouble();
			}
			System.out.println((has(x, y) ? "Yes" : "No"));
			N = sc.nextInt();
		}
	}

	static boolean has(double[] x, double[] y) {
		for (int i = 0; i < N; ++i) {
			for (int j = i + 1; j < N; ++j) {
				if (x[i] == x[j] && y[i] == y[j]) return false;
			}
		}
		for (int i = 0; i < N; ++i) {
			for (int j = i + 1; j < N; ++j) {
				double dx1 = x[j] - x[i];
				double dy1 = y[j] - y[i];
				double cx1 = (x[i] + x[j]) / 2;
				double cy1 = (y[i] + y[j]) / 2;
				double p1 = dx1 * cx1 + dy1 * cy1;
				for (int k = j + 1; k < N; ++k) {
					double dx2 = x[k] - x[i];
					double dy2 = y[k] - y[i];
					if (dx1 * dy2 == dy1 * dx2) return false; // 同一直線上
					double cx2 = (x[i] + x[k]) / 2;
					double cy2 = (y[i] + y[k]) / 2;
					double p2 = dx2 * cx2 + dy2 * cy2;
					double det = (dx1 * dy2 - dx2 * dy1);
					double centerX = (p1 * dy2 - p2 * dy1) / det;
					double centerY = (-p1 * dx2 + p2 * dx1) / det;
					double r2 = (x[i] - centerX) * (x[i] - centerX) + (y[i] - centerY) * (y[i] - centerY);
					for (int l = 0; l < N; ++l) {
						if (l == i || l == j || l == k) continue;
						double r = (x[l] - centerX) * (x[l] - centerX) + (y[l] - centerY) * (y[l] - centerY);
						if (Math.abs(r - r2) < EPS) return false; // 同一円上
					}
				}
			}
		}
		return true;
	}
}

• G

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Scanner;

public class G {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) throws Exception {
		int N = sc.nextInt();
		int D = sc.nextInt();
		while (N > 0 && D > 0) {
			sc.nextLine();
			ArrayList
 ps = new ArrayList
();
			for (int i = 0; i < N; ++i) {
				String[] line = sc.nextLine().split(" +");
				int p = Integer.parseInt(line[0]);
				int c = line.length / 2 - 1;
				for (int j = 0; j < c; ++j) {
					String name = line[j * 2 + 2];
					int pc = Integer.parseInt(line[j * 2 + 3]);
					ps.add(new P(name, p + pc));
				}
				Collections.sort(ps);
				// 全部覚えるとたぶんメモリに乗らないのでコストが少ないやつだけ取っておく
				int add = 0;
				ArrayList
 next = new ArrayList
();
				HashSet used = new HashSet();
				for (int j = 0; j < ps.size(); ++j) {
					if (used.contains(ps.get(j).name)) {
						continue;
					}
					used.add(ps.get(j).name);
					next.add(ps.get(j));
					++add;
					if (add > D) break;
				}
				ps = next;
			}
			long ans = 0;
			for (int i = 0; i < ps.size() && i < D - 1; ++i) {
				ans += ps.get(i).cost;
			}
			System.out.println(Math.min(ps.size(), D - 1) + " " + ans);
			N = sc.nextInt();
			D = sc.nextInt();
		}
	}
}

class P implements Comparable
 {
	String name;
	int cost;

	P(String name, int cost) {
		this.name = name;
		this.cost = cost;
	}

	public int compareTo(P o) {
		return this.cost - o.cost;
	}

	public String toString() {
		return name + "," + cost;
	}
}

• H

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

public class H {
	static Scanner sc = new Scanner(System.in);
	static HashMap map;

	public static void main(String[] args) throws Exception {
		String s = sc.next();
		while (!s.equals("-")) {
			map = new HashMap();
			for (char c : s.toCharArray()) {
				if (!map.containsKey(c)) {
					map.put(c, map.size());
				}
			}
			long sv = toLong(s);
			long tv = toLong(sc.next());
			int ans = solve(sv, tv, s.length());
			System.out.println(ans);
			s = sc.next();
		}
	}

	static int solve(long sv, long tv, int N) {
		if (sv == tv) {
			return 0;
		}
		HashSet setS = new HashSet();
		ArrayList curS = new ArrayList();
		setS.add(sv);
		curS.add(sv);
		HashSet setT = new HashSet();
		ArrayList curT = new ArrayList();
		setT.add(tv);
		curT.add(tv);
		int c = 0;
		while (true) {
			++c;
			ArrayList next = new ArrayList();
			for (long v : curS) {
				for (int start = 0; start < N - 1; ++start) {
					for (int end = start + 1; end < N; ++end) {
						long nv = 0;
						long mask = (1l << (start * 4)) - 1;
						nv |= (v & mask);
						int mv = (end + 1) * 4;
						nv |= ((v >> mv) << mv);
						for (int i = start; i <= end; ++i) {
							long cv = ((v >> (4 * i)) & 0xF);
							int pos = start + (end - i);
							nv |= (cv << (4 * pos));
						}
						if (!setS.contains(nv)) {
							if (setT.contains(nv)) {
								return c;
							}
							setS.add(nv);
							next.add(nv);
						}
					}
				}
			}
			curS = next;

			++c;
			next = new ArrayList();
			for (long v : curT) {
				for (int start = 0; start < N - 1; ++start) {
					for (int end = start + 1; end < N; ++end) {
						long nv = 0;
						long mask = (1l << (start * 4)) - 1;
						nv |= (v & mask);
						int mv = (end + 1) * 4;
						nv |= ((v >> mv) << mv);
						for (int i = start; i <= end; ++i) {
							long cv = ((v >> (4 * i)) & 0xF);
							int pos = start + (end - i);
							nv |= (cv << (4 * pos));
						}
						if (!setT.contains(nv)) {
							if (setS.contains(nv)) {
								return c;
							}
							setT.add(nv);
							next.add(nv);
						}
					}
				}
			}
			curT = next;
		}
	}

	// 文字列を64bit整数にエンコード
	static long toLong(String str) {
		long ans = 0;
		for (int i = 0; i < str.length(); ++i) {
			ans |= ((long) map.get(str.charAt(i)) << (4 * i));
		}
		return ans;
	}
}