ABC - 034- A&B&C

AtCoder ABC 034 A&B&C

AtCoder - 034

2019/05/14追記
　C問題の満点解法を追記

A問題

	private void solveA() {
		int x = nextInt();
		int y = nextInt();

		out.println(x < y ? "Better" : "Worse");
	}

B問題

• 奇偶判定

	private void solveB() {
		int numN = nextInt();

		out.println((numN & 1) == 1 ? numN + 1 : numN - 1);
	}

C問題：満点解法/逆元の利用(2019/05/14追記)

• 参考サイト

解法の考え方と、その実装方法

• 高1スタンダードレベル数学ⅠAⅡB最短経路

• 順列と組み合わせの違い・カンタンな見分け方を教えます！

  • そもそもの解法の意味が分からない場合は上記二つで。。。年取ると物忘れが激しい。

• 「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜

  • 解法がわかっても逆元がわからないと実装しても桁あふれする

• よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方

  • こちらの実装も試したが、現時点では実装した内容が理解範囲外だったためjavaのライブラリで実装

• 合同式の証明や問題の解き方を解説！大学受験で使いこなそう！

逆元の求め方ですが、javaだとBigIntegerがそのものずばりの#modInverse()を持っているので其方を利用

	/*
	 * 経路組み合わせ
	 *
	 */
	private void solveC() {
		final long CONST_MOD = (long) (Math.pow(10, 9) + 7);

		int w = nextInt() - 1;
		int h = nextInt() - 1;

		long mole = 1;
		for (int i = 1; i <= w + h; i++) {
			mole *= i;
			mole %= CONST_MOD;
		}
		long deno = 1;
		for (int i = 1; i <= w; i++) {
			deno *= i;
			deno %= CONST_MOD;
		}
		for (int i = 1; i <= h; i++) {
			deno *= i;
			deno %= CONST_MOD;
		}
		/*
		 * mod 100000007における denoの逆元を求める
		 * deno^-1(mod CONST_MOD)
		 */
		BigInteger denoModInverse = new BigInteger(Long.toString(deno))
				.modInverse(new BigInteger(Long.toString(CONST_MOD)));

		out.println(new BigInteger(Long.toString(mole)).multiply(denoModInverse)
				.mod(new BigInteger(Long.toString(CONST_MOD))));
	}

C問題：MLEのため100点です。101点解法ではありません。

• メモ化再帰で書いたけど、、、解説の101点解法が理解できない。。。。
  • DPではないけれど、メモ化すれば100点は取れた。

/*
	 * MLE version
	 */
	private void solveC2() {
		int w = nextInt();
		int h = nextInt();

		long[][] memo = new long[w + 1][h + 1];

		out.println(dfsC2(w, h, 1, 1, memo) % CONST);
	}

	private long dfsC2(int w, int h, int currentW, int currentH, long[][] memo) {

		if (w == currentW && h == currentH) {
			return 1;
		}
		if (memo[currentW][currentH] != 0) {
			return memo[currentW][currentH];
		}

		long val1 = 0;
		if (currentW < w) {
			val1 = dfsC2(w, h, currentW + 1, currentH, memo) % CONST;
		}
		long val2 = 0;
		if (currentH < h) {
			val2 = dfsC2(w, h, currentW, currentH + 1, memo) % CONST;
		}

		return memo[currentW][currentH] = (val1 + val2) % CONST;
	}

C問題：DP・・・これもMLE

	/*
	 * DP version
	 */
	private void solveC() {
		int w = nextInt();
		int h = nextInt();

		long[][] memo = new long[w + 2][h + 2];
		memo[1][1] = 1;

		for (int i = 1; i <= w; i++) {
			for (int j = 1; j <= h; j++) {
				memo[i + 1][j] = (memo[i + 1][j] + memo[i][j]) % CONST;
				memo[i][j + 1] = (memo[i][j + 1] + memo[i][j]) % CONST;
			}
		}
		out.println(memo[w][h]);
	}