ABC - 030- A&B&C

AtCoder ABC 030 A&B&C

AtCoder - 030

A問題

• 小数点を扱うのが面倒なので、掛け算に変更
  • {$b \div a < d \div c$}　または、{$b \div a > d \div c$} を判定したいので
  • {$b \times c < d \times a$}　または、{$b \times c > d \times a$} に変更

	private void solveA() {
		int a = nextInt();
		int b = nextInt();
		int c = nextInt();
		int d = nextInt();
		if (b * c > a * d) {
			out.println("TAKAHASHI");
		} else if (b * c < a * d) {
			out.println("AOKI");
		} else {
			out.println("DRAW");
		}
	}

B問題

• 時計の短針の角度計算はメンドイ
  • この計算方法では、23:59は正確に出るが、23:10とかだと180を超えてしまうので360から引く

	private void solveB() {
		int n = nextInt();
		int m = nextInt();

		double smallHand = n % 12 * 30 + m * 0.5;//n % 12 * (360 / 12) + m * (360 / 12 /  60)
		double longHand = m % 60 * 6;//m % 60 * (360 / 60)

		double res = Double.max(smallHand, longHand) - Double.min(smallHand, longHand);
		/*
		 * 23:10だと180より大きい
		 */
		if (res > 180) {
			out.println(360 - res);
		} else {
			out.println(res);
		}
	}

C問題：二分探索

• 二分探索を利用
  • 以下、探索終了（BinarySearchのindex取得がそれぞれの最終Indexを超えた）までループ
    • A空港を出発可能な最小時刻をBinarySearchで取得
      • 探索出来たら、現在時刻+Xと移動したことを記録
    • B空港を出発可能な最小時刻をBinarySearchで取得
      • 探索出来たら、現在時刻+Yと移動したことを記録
  • 移動したカウント/2が往復した回数
    • ただし、偶数だったら往復できたとみなせるが、奇数の場合は-1してから/2する
      • X->Yへの移動のみの場合を除去するため

	private void solveC2() {
		int n = nextInt();
		int m = nextInt();
		long x = nextInt();
		long y = nextInt();
		long[] aA = LongStream.range(0, n).map(i -> nextLong()).toArray();
		long[] bA = LongStream.range(0, m).map(i -> nextLong()).toArray();

		/*
		 * true = airport A
		 * false = airport B
		 */
		boolean isAirportA = true;
		long currentTime = 0;
		long moveCnt = 0;
		while (true) {
			/*
			 * 空港A出発かB出発か
			 */
			if (isAirportA) {
				/*
				 * 今現在の時間から出発可能なA空港の便を探す
				 */
				int aI = Arrays.binarySearch(aA, currentTime);
				aI = aI >= 0 ? aI : ~aI;
				//二分探索した結果、最後のindex位置までいってしまったらもう終了
				if (aI >= n) {
					break;
				}
				/*
				 * 次のB空港を出発可能な時間
				 */
				currentTime = aA[aI] + x;
				/*
				 * 次はB空港
				 */
				isAirportA = false;
				moveCnt++;
			} else {
				/*
				 * 内容はA空港の値を全てBに置き換えているだけ
				 */
				int bI = Arrays.binarySearch(bA, currentTime);
				bI = bI >= 0 ? bI : ~bI;
				if (bI >= m) {
					break;
				}
				currentTime = bA[bI] + y;
				isAirportA = true;
				moveCnt++;
			}
		}
		/*
		 * 移動回数が奇数の時は、X->Yに行っただけなので、
		 * 往復できていない。
		 * そのため、その回の移動はナシ
		 */
		if ((moveCnt & 1) == 1) {
			moveCnt -= 1;
		}
		/*
		 * 飛行機に乗った数の半分が往復できた回数
		 */
		out.println(moveCnt / 2);

	}

C問題：別解（二分探索を使わず、forだけで判定）

• $O(2N)$?　計算量ぇ

• 二分探索をすぐ思いついて実装できたけどなんか汚いので別のやり方を探していたらこちらでも実装できる気がしたので試し

• 毎回毎回$A[i]とB[i]$を全部探すのではなく、途中のindexを保持していれば両方の配列を1回ずつ回すだけで済むのでは？という発想

• A空港の出発時刻を探す

  • A空港の{$出発時刻+X$}を取得
    • B空港の出発時刻を探す
      • B空港の{$出発時刻+Y$}を取得 & (次回の検索開始Indexを取得して時刻探索を打ち切り)
        • A空港の出発時刻を探す
          • A空港の{$出発時刻+X$}を取得
            • ・・・・・以下ループ

	/*
	 * 全探索？
	 */
	private void solveC() {
		int n = nextInt();
		int m = nextInt();
		long x = nextInt();
		long y = nextInt();
		long[] aA = LongStream.range(0, n).map(i -> nextLong()).toArray();
		long[] bA = LongStream.range(0, m).map(i -> nextLong()).toArray();

		int bI = 0;
		long currentTime = 0;
		long moveCnt = 0;
		for (int i = 0; i < n; i++) {
			//現在の時間よりも小さい出発時刻は使えない
			if (currentTime > aA[i]) {
				continue;
			}
			//A空港を出発可能
			currentTime = aA[i] + x;
			//B空港の時刻を検索開始
			for (int j = bI; j < m; j++) {
				//現在の時間よりも小さい出発時刻は使えない
				if (currentTime > bA[j]) {
					continue;
				}
				/*
				 * この時刻は使えるので、
				 * ・次のA空港の出発時刻をセット
				 * ・次のB空港の時刻検索開始のindexをセット
				 */
				currentTime = bA[j] + y;
				bI = j + 1;
				//B空港を出発できたので往復できた
				moveCnt++;
				break;
			}
		}
		out.println(moveCnt);
	}