ABC - 077- A&B&C

#AtCoder ABC 077 A&B&C
[AtCoder - 077](https://atcoder.jp/contests/abc077)

#A問題

```java
	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$

```java
	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問題参考リンク】に記載


```java
	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

```java
	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](https://qiita.com/shihou22/items/62f3e31de61054154505)