ABC - 077- A&B&C

AtCoder ABC 077 A&B&C

AtCoder - 077

A問題

	private void solveA() {
		StringBuilder wk1 = new StringBuilder(next());
		StringBuilder wk2 = new StringBuilder(next());

		if (wk1.toString().equals(wk2.reverse().toString())) {
			out.println("YES");
		} else {
			out.println("NO");
		}

	}

B問題

• 求めたい値は $ \leqq\sqrt{N}$ となる最大の整数の２乗

1. $\sqrt{N}$ を求める
2. 少数を切り落とす
   • 平方数は整数
   • 整数に変換
3. ２乗する

または、

• $i^2$ が $n$ を初めて超えたときの、$(i − 1)^2$

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

		int wk = (int) Math.sqrt(numN);

		out.println((int) Math.pow(wk, 2));
	}

C問題

• Arrays#binarySearch(Object[],Object)に渡すkeyを加工している
  • Comparator版の実装はコメントアウトしている

解法

• 二分探索で値を探すことにする
• ただし、 A → B → Cと順に探索すると、二分探索が使えるのがB → Cの時にCを探すときしかない
  • A → BのBを探すのに二分探索を使えそうな気がするけど、B → CをやらなくてはいけないのでLoopは必要
• なので、順に探すのではなく、二分探索だけで済ませるために以下の手段を採用する
  • Bより小さい数値がいくつあるかをAから探す
  • Bより大きい数値がいくつあるかをCから探す
    • 実際には個数を探すのではなく、
      • Bより小さい数値があるかAのindexを探す。結果のindex番号がBより小さい個数
      • Bより大きい数値があるかCのindexを探す。結果のindex番号から最後のindex番号までが大きい個数

javaでの二分探索について

• 二分探索そのものはjavaにも関数（Arrays#binarySearch()）がある
• ただし、binarySearchをそのまま使うと値が複数合った場合に対応が出来ない
  • 検索対象の値に重複が存在しない場合は使えるけど、重複している場合の動作が今回の問題とマッチしない
• そのため、Cのlower_boundやupper_boundが欲しいけど、そのものズバリの関数がないので調べた
  • 結果は【C問題参考リンク】に記載

	private void solveC() {
		int numN = nextInt();
//		Long[] aA = IntStream.range(0, numN).mapToObj(i -> new Long(nextLong())).toArray(Long[]::new);
//		Long[] bA = IntStream.range(0, numN).mapToObj(i -> new Long(nextLong())).toArray(Long[]::new);
//		Long[] cA = IntStream.range(0, numN).mapToObj(i -> new Long(nextLong())).toArray(Long[]::new);
//
//		Arrays.sort(aA, (x, y) -> Long.compare(x, y));
//		Arrays.sort(bA, (x, y) -> Long.compare(x, y));
//		Arrays.sort(cA, (x, y) -> Long.compare(x, y));

		Double[] aA = IntStream.range(0, numN).mapToObj(i -> new Double(nextLong())).toArray(Double[]::new);
		Double[] bA = IntStream.range(0, numN).mapToObj(i -> new Double(nextLong())).toArray(Double[]::new);
		Double[] cA = IntStream.range(0, numN).mapToObj(i -> new Double(nextLong())).toArray(Double[]::new);

		Arrays.sort(aA, (x, y) -> Double.compare(x, y));
		Arrays.sort(bA, (x, y) -> Double.compare(x, y));
		Arrays.sort(cA, (x, y) -> Double.compare(x, y));

		long res = 0;
		for (int i = 0; i < bA.length; i++) {
			//			Long bP = bA[i];
			Double bP = bA[i];

			//			long aS = Arrays.binarySearch(aA, bP, new LowerBoundComparator<Long>());
			long aS = Arrays.binarySearch(aA, bP - 0.1);
			if (aS < 0) {
				aS = ~aS;
			}

			//			long cS = Arrays.binarySearch(cA, bP, new UpperBoundComparator<Long>());
			long cS = Arrays.binarySearch(cA, bP + 0.1);
			if (cS < 0) {
				cS = ~cS;
			}
			long resT = aS * (long) (numN - cS);
			res += resT;
		}

		out.println(res);
	}

	/**
	 * 指定した値以上の要素が初めて出現する場所を取得
	 * @author works
	 *
	 * @param <T>
	 */
	class LowerBoundComparator<T extends Comparable<? super T>> implements Comparator<T> {
		public int compare(T o1, T o2) {
			return (o1.compareTo(o2) >= 0) ? 1 : -1;
		}
	}

	/**
	 * 指定した値より大きい要素が初めて出現する場所を取得
	 * @author works
	 *
	 * @param <T>
	 */
	class UpperBoundComparator<T extends Comparable<? super T>> implements Comparator<T> {
		@Override
		public int compare(T o1, T o2) {
			return (o1.compareTo(o2) > 0) ? 1 : -1;
		}
	}

C問題：愚直にLoopでTLE

	private void solveC2() {
		int numN = nextInt();
		Long[] aA = IntStream.range(0, numN).mapToObj(i -> new Long(nextLong())).toArray(Long[]::new);
		Long[] bA = IntStream.range(0, numN).mapToObj(i -> new Long(nextLong())).toArray(Long[]::new);
		Long[] cA = IntStream.range(0, numN).mapToObj(i -> new Long(nextLong())).toArray(Long[]::new);

		Arrays.sort(aA, (x, y) -> Long.compare(x, y) * -1);
		Arrays.sort(bA, (x, y) -> Long.compare(x, y) * -1);
		Arrays.sort(cA, (x, y) -> Long.compare(x, y) * -1);

		long res = 0;
		for (int i = 0; i < aA.length; i++) {
			long aP = aA[i];
			for (int j = 0; j < bA.length; j++) {
				long bP = bA[j];
				if (aP >= bP) {
					break;
				}
				for (int k = 0; k < cA.length; k++) {
					long cP = cA[k];
					if (bP >= cP) {
						break;
					}
					res++;
				}
			}
		}

		out.println(res);
	}

C問題参考リンク

javaでlower_bound/upper_bound