Hatena::Grouptopcoder

TopCoder戦記

研究開発者・ellerのTopCoder挑戦記録。言語は主にJavaを使用しています。ドキュメンテーションコメントはSubmit完了後、ブログ掲載前に補完したものです。

2011-05-18SRM 504.5

久々の参加。

ox- +50 -0 で182.31pt、Ratingは1376に上がりました。

SRM 504.5 Easy

| 00:30

問題文:http://www.topcoder.com/stat?c=problem_statement&pm=11096&rd=14514

このEasyだけは落とすまいとテストケースを相当書きました。今の自分のRatingでは、Mediumを頑張って通すよりもEasyを確実に通してchallengeで稼ぐ方が確実だと考えるためです。

今回はEasyを落とす人が少なかったのでこれだけ通してもあまり嬉しくなかったのですが、方針として大きく誤ってはいないと思うのでしばらくこのEasy死守戦略を続けてみます。

public class TheNumbersWithLuckyLastDigit {
	public int find(int n) {
		if (n < 4 || n == 6 || n == 10)
			return -1;

		switch (n % 10) {
		case 4:
		case 7:
			return 1;
		case 0:
			return 5;
		case 2:
			return 3;
		case 6:
			return 4;
		case 8:
			return 2;
		default:
			if (n % 2 == 1) {
				int k = find(n - 7);
				return k == -1 ? -1 : k + 1;
			}
			return -1;
		}
	}

	// BEGIN CUT HERE
	public static void main(String[] args) {
		TheNumbersWithLuckyLastDigit temp = new TheNumbersWithLuckyLastDigit();
		System.out.println(temp.find(1) == -1);
		System.out.println(temp.find(2) == -1);
		System.out.println(temp.find(3) == -1);
		System.out.println(temp.find(4) == 1);
		System.out.println(temp.find(5) == -1);
		System.out.println(temp.find(6) == -1);
		System.out.println(temp.find(7) == 1);
		System.out.println(temp.find(8) == 2);
		System.out.println(temp.find(9) == -1);
		System.out.println(temp.find(10) == -1);
		System.out.println("===");

		System.out.println(temp.find(11) == 2);
		System.out.println(temp.find(12) == 3);
		System.out.println(temp.find(13) == -1);
		System.out.println(temp.find(14) == 1);
		System.out.println(temp.find(15) == 3);
		System.out.println(temp.find(16) == 4);
		System.out.println(temp.find(17) == 1);
		System.out.println(temp.find(18) == 2);
		System.out.println(temp.find(19) == 4);
		System.out.println(temp.find(20) == 5);
		System.out.println("===");

		System.out.println(temp.find(21) == 2);
		System.out.println(temp.find(23) == 5);
		System.out.println("===");

		System.out.println(temp.find(99) == 4);
		System.out.println(temp.find(11) == 2);
		System.out.println(temp.find(13) == -1);
		System.out.println(temp.find(1234567) == 1);
	}
	// END CUT HERE
}

今回は二重ループで解を求める形が最もシンプルで好ましかったのではと思います。ただループの回数が足りずに撃墜されているケースもあったので、最低でも何回ループするかをきちんと考えることが重要です。下1桁だけ考えればいいことに着目すると、4で終わる数は少なくとも6個以上にならないこと・7で終わる数は少なくとも10個以上にならないことが言えそう*1ですので、以下のような二重ループにすべきだったのでしょう。

	public int find(int n) {
		int result = Integer.MAX_VALUE;
		for (int i = 0; i < 6; ++i) {
			for (int j = 0; j < 10; ++j) {
				if ((i * 4 + j * 7) % 10 == n % 10 && i * 4 + j * 7 <= n && i + j > 0) {
					result = Math.min(result, i + j);
				}
			}
		}
		return result == Integer.MAX_VALUE ? -1 : result;
	}

*1:もっときちっと考えると削れそうですが、計算量的には大差ないのでこれでOKとする