Hatena::Grouptopcoder

gnarl,TopCoder

 | 

2010-05-09

Google Code Jam 2010 Qual

19:39

初挑戦。

A Large以外は解けて76点。

しかし9時間くらいやってた……。

A: Snapper Chain

  • Snapperという機械(スイッチみたいなもん)がN個直列につながってる
  • 一方の端には電源がつながってる
  • snapすると、電源が供給されているSnapperはOn/Offが切り替わる
  • 電源が供給されていて、なおかつOn状態のSnapperにつながっているSnapperには電源が供給される

k回snapしたとき、端まで電源が供給されるかどうかを求めよ。

勝手がわからず物凄くナイーブな方法で実装したらSmallは通ったけどLargeで死亡した……。

これ法則を見つければ瞬時に解けるみたいですね。

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

public class A {
	public static void main(String[] args) {
		final Scanner s = new Scanner(System.in);
		final int t = s.nextInt();
		for (int i = 0; i < t; i++) {
			final int n = s.nextInt();
			final int k = s.nextInt();
			final boolean result = calc(n, k);
			System.out.println("Case #" + (i + 1) + ": "
					+ (result ? "ON" : "OFF"));
		}
	}

	public static boolean calc(int n, int k) {
		boolean[] states = new boolean[n];
		int powered = 0;
		for (int i = 0; i < k; i++) {
			for (int j = 0; j < n; j++) {
				powered = j;
				if (!states[j])
					break;
			}
			for (int j = 0; j <= powered; j++) {
				states[j] = !states[j];
			}
		}
		for (int j = 0; j < n; j++) {
			powered = j;
			if (!states[j])
				break;
		}

		return powered == n - 1 && states[n - 1];
	}
}

B: Fair Warning

a_1,a_2,...,a_N が与えられる。a_1+y,a_2+y,...,a_N+yの最大公約数が最大(T)となるような最小のyを求めよ。

これはどうすれば解けるのか全くわからなかったけど、なぜか「0,a_2-a_1, ... , a_N-a_1 の最大公約数が可能な最大公約数である」という気がしたのでそうしてみたらうまくいってしまった。

謎のバグでSmall送信時にさんざん失敗したけど、よく見直したら0を返すべきときにTを返してしまうバグがあったので修正。

Small,Large通した。

import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Scanner;

public class B {
	public static void main(String[] args) {
		final Scanner s = new Scanner(System.in);
		final int C = s.nextInt();
		for (int i = 0; i < C; i++) {
			final int N = s.nextInt();
			final BigDecimal[] nums = new BigDecimal[N];
			for (int j = 0; j < N; j++) {
				nums[j] = s.nextBigDecimal();
			}
			System.err.println("Case #" + (i + 1));
			System.err.println("  input: " + Arrays.asList(nums));
			final BigDecimal res = calc(nums);
			System.err.println("  output: " + res);
			System.out.println("Case #" + (i + 1) + ": " + res);
		}
	}

	public static BigDecimal calc(BigDecimal[] nums) {
		Arrays.sort(nums);
		final BigDecimal base = nums[0];
		for (int i = 0; i < nums.length; i++)
			nums[i] = nums[i].subtract(base);
		final BigDecimal gcd = gcd(nums);
		System.err.println("  gcd:" + gcd);
		final BigDecimal y;
		if (gcd.equals(BigDecimal.ONE)) {
			y = BigDecimal.ZERO;
		} else {
			final BigDecimal remainder = base.remainder(gcd);
			y = remainder.equals(BigDecimal.ZERO) ? BigDecimal.ZERO : gcd
					.subtract(remainder);
		}

		return y;
	}

	public static BigDecimal gcd(BigDecimal[] nums) {
		if (nums.length == 0)
			throw new IllegalArgumentException();
		if (nums.length == 1)
			return nums[0];
		BigDecimal gcd = nums[0];
		for (int i = 1; i < nums.length; i++) {
			gcd = gcd(gcd, nums[i]);
		}
		return gcd;
	}

	public static BigDecimal gcd(BigDecimal m, BigDecimal n) {
		if (m.compareTo(n) < 0)
			return gcd(n, m);
		if (n.equals(BigDecimal.ZERO))
			return m;
		final BigDecimal remainder = m.remainder(n);
		if (remainder.equals(BigDecimal.ZERO))
			return n;
		return gcd(n, remainder);
	}
}

C: Theme Park

最大k人乗れるジェットコースターがあって、乗客がグループに分かれて並んでる。先頭から順に乗っていって、グループ全員が乗れない場合は乗らない。乗り終わったグループはまた列の末尾に並ぶ。R回運転するときの収益を求めよ。

ナイーブな実装は簡単だがLargeで確実に死ぬので、繰り返しを検出したらその結果を利用するような処理を入れたらさんざんバグって困った。最適化したバージョンとしてないバージョンの計算結果をチェックするテストをひたすら書いたりした。

最終的にどうにかなって、Small,Large通した。

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

public class C {
	public static boolean noCache = false;

	public static void main(String[] args) {
		if (args.length > 0) {
			System.err.println("no cache mode");
			noCache = true;
		}
		final Scanner s = new Scanner(System.in);
		final int T = s.nextInt();
		for (int i = 0; i < T; i++) {
			final int R = s.nextInt();
			final int k = s.nextInt();
			final int N = s.nextInt();
			final int[] t = new int[N];
			for (int j = 0; j < N; j++) {
				t[j] = s.nextInt();
			}
			final long res = calc(R, k, t);
			System.out.println("Case #" + (i + 1) + ": " + res);
		}
	}

	public static long calc(int r, int k, int[] t) {
		int[] lastVisit = new int[t.length];
		Arrays.fill(lastVisit, -1);
		long[] prices = new long[t.length];
		long price = 0;
		{
			int cur = 0;
			int n = 0;
			boolean cycleFound = false;
			while (true) {
				if (n >= r)
					break;
				if (!noCache && !cycleFound && lastVisit[cur] != -1) {
					System.err.println("cycle found at step " + n);
					System.err.println(" current index=" + cur);
					cycleFound = true;
					// cycle found
					final int cycleLen = n - lastVisit[cur];
					final long cyclePrice = price - prices[cur];
					final int restLoop = r - n;
					final int wholeCycles = restLoop / cycleLen;
					price += cyclePrice * wholeCycles;
					n += wholeCycles * cycleLen;
					System.err.println(" price=" + cyclePrice);
					System.err.println(" cycle length=" + cycleLen);
					System.err.println(" number of whole cycle=" + wholeCycles);
					System.err.println(" earned from whole cycles="
							+ wholeCycles * cyclePrice);
					System.err.println("skip to " + n);
				}
				if (n >= r)
					break;

				lastVisit[cur] = n;
				prices[cur] = price;
				int next = cur;
				int people = 0;
				while (true) {
					if (people + t[next] > k)
						break;
					people += t[next];
					next = (next + 1) % t.length;
					if (next == cur)
						break;
				}
				price += people;
				n++;
				cur = next;
			}
		}
		return price;
	}
}

感想

  • 時間をかければどうにかなるものですね
  • トップの人は1問10分くらいで解いてるのですごい。生産性20倍くらい違う……
  • この手のコンテストは、きっちりテスト書いてるようじゃ負けなんだと思う。上位者はたぶん、問題見た瞬間に最適な解法を思いついて一発で正しく実装してsubmitしてる。
  • これって才能なのか努力なのか……
  • まあ場数を踏むことは重要ですね。がんばります。

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/gnarl/20100509
 |