ABC - 038- A&B&C

AtCoder ABC 038 A&B&C

AtCoder - 038

A問題

	private void solveA() {
		String s = next();
		if (s.substring(s.length() - 1).equals("T")) {
			out.println("YES");
		} else {
			out.println("NO");
		}

		out.println("");
	}

B問題

• h1w1のディスプレイと、h2w2のディスプレイのhでもwでもどちらでもいいので長さが合えばよい。
• set使ってloopまわしてもよかったかも、、、ifが多いのが既にちょっとなぁ

	private void solveB() {
		int h1 = nextInt();
		int w1 = nextInt();
		int h2 = nextInt();
		int w2 = nextInt();

		if (h1 == h2 || h1 == w2 || w1 == h2 || w1 == w2) {
			out.print("YES");
		} else {
			out.print("NO");
		}

		out.println("");
	}

C問題

• 悩んだけど、累積和を使って解けた。多分、しゃくとり法でもいけると思う。

• 組み合わせの数(重複組み合わせ)

  • {$1,2,3,4,5$} を $(1,2),(1,3),(1,4),(1,5),(2,2)...(5,5)$とするには、$n*(n+1) / 2 $
  • $nH_r = {n+r-1}C_r$
    • $nH_2 = {n+1}C_2$
      • $((n+1)*n)/(2*1)$
        • $((n+1)*n)/2$

	private void solveC() {
		int numN = nextInt();
		int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();
		long res = 0;
		long[] rui = new long[numN];
		int ruiCnt = 0;
		rui[ruiCnt] = 1;

		for (int i = 1; i < wk.length; i++) {
			if (wk[i - 1] < wk[i]) {
				rui[ruiCnt] += 1;
			} else {
				ruiCnt++;
				rui[ruiCnt] = 1;
			}
		}
		for (long i : rui) {
			/*
			 * 重複組み合わせ
			 * nHr=n+r−1Cr
			 *
			 * nH2 = n+1C2
			 *
			 * n*(n+1) /2
			 */
			long tmp = (i * (i + 1)) / 2;
			res += tmp;
		}
		out.println(res);
	}

C問題：しゃくとり法

参考

しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ

• 参考サイトを読んで。とてもわかりやすい（わかりやすいと自分が実装可能は別の話ですが）

• 実際のところ、(1,1),(1,2),(1,3)...(5,5) という全ての組を一つ一つ数えているわけではない。

  • 具体的には、テストケース入力例1の場合の出力は(1,1),(1,2),(1,3),(2,2),(2,3),(3,3),(4,4),(5,5)となるが、
  • このロジックでは(left,right)=(2,2),(2,3),(3,3)は出現しない。

• res += right - left　で該当箇所が出現しているとして回収している

	private void solveC4() {
		int numN = nextInt();
		int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();
		long res = 0;
		int left = 0;
		int right = 0;
		while (left < numN) {
			/*
			 * 継続条件
			 * １：問題文の条件
			 * wk[right - 1] < wk[right]
			 *
			 * ２：これも問題文の条件
			 * left == right
			 * ->
			 * left == right は条件を満たしているため
			 * 同じ位置の場合はrightを進める
			 */
			while (right < numN && (left == right || wk[right - 1] < wk[right])) {
				right++;
			}
			/*
			 * 差分を+していく
			 * (left , right]
			 */
			res += right - left;
			/*
			 * 左を進める
			 */
			left++;
		}
		out.println(res);
	}