ABC - 057 - A&B&C

AtCoder ABC 057 B&C

AtCoder - 057

A問題

• 24hr表記
  • 23:59の次は0:00
• A時のB時間後が開催時刻

B時間後が開催時刻で24hr表記ということは、B時間後を足した後に$mod 24$をすればよい。

	private void solveA() {
		int numA = nextInt();
		int numB = nextInt();

		out.println((numA + numB) % 24);
	}

B問題

• 学生が$(x_i,y_i) = (a_i,b_i)$　座標にいる
• 一番近い $(c_j,d_j)$　座標に移動する

$(a_i,B_i)$ 座標を基準に、 一番近い $(C_j,d_j)$ 座標をloopで探す。

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

		int[][] ab = new int[numN][2];

		IntStream.range(0, numN).forEach(i -> {
			ab[i][0] = nextInt();
			ab[i][1] = nextInt();
		});

		int[][] cd = new int[numM][2];

		IntStream.range(0, numM).forEach(i -> {
			cd[i][0] = nextInt();
			cd[i][1] = nextInt();
		});

		for (int[] js : ab) {
			int res = Integer.MAX_VALUE;
			int index = -1;
			for (int j = 0; j < cd.length; j++) {
				int wk = Math.abs(js[0] - cd[j][0]) + Math.abs(js[1] - cd[j][1]);
				if (wk < res) {
					res = wk;
					index = j;
				}
			}
			out.println(index + 1);
		}

	}

C問題

• $N$ が与えられるので $N=A*B$ となる $(A,B)$ の組を求める
• $(A,B)$ の組それぞれの桁数のうち、大きいほうを採用する
• そうして求めた値のうち、最小の値を出力する

これ、単純にコーディングするとTLEになります。

• TLEのコードは一番最後に記載

計算量を減らす方法ですが、 $N = AB = BA$ が成り立ちます。
つまり、 $N=16$ とした場合、組み合わせは以下の5通り。

No	A*B	B*A
1	$ 1*16$	$ 16*1$
2	$ 2*8$	$ 8*2$
3	$ 4*4$	$4*4$
4	$ 8*2$
5	$ 16*1$

No.1-No.3までを計算すれば、No.4およびNo5は不要です。
$N=16$ なので削減量が少ない気がしますが、 $-10^8 <= N <= 10^8$ の範囲なので削減量は結構な量になりそうです。

/**
	 * 全列挙方法を修正
	 * numN = A * B = B * A
	 * ということは、
	 * digits(A) <= digits(B)となるものだけを列挙すればよい。
	 */
	private void solveC2() {
		long numN = nextLong();

		long res = Long.MAX_VALUE;
		/*
		 * 条件に当てはまるということはもう検査する必要がない。
		 * なぜなら、A*B=B*Aなのでこれより先のwkAは既に検査済み
		 *  1* 16 を検査したら、 16*1は検査する必要がない。
		 */
		long wkA = 1;
		long wkB = numN / 1;
		while (wkA <= wkB) {
			if (numN % wkA == 0) {
				res = Math.min(res, Math.max(chkDigit(wkA), chkDigit(wkB)));
			}
			wkA++;
			wkB = numN / wkA;
		}

		//		for (long i = 1; i < numN; i++) {
		//			long wkA = i;
		//			long wkB = numN / i;
		//
		//			/*
		//			 * 条件に当てはまるということはもう検査する必要がない。
		//			 * なぜなら、A*B=B*Aなのでこれより先のiは既に検査済み
		//			 *  1* 16 を検査したら、 16*1は検査する必要がない。
		//			 */
		//
		//			if (wkA >= wkB) {
		//				break;
		//			}
		//			if (numN % i == 0) {
		//				res = Math.min(res, Math.max(chkDigit(wkA), chkDigit(wkB)));
		//			}
		//		}

		out.println(res);
	}

	private int chkDigit(double num) {
		int cnt = 0;
		long wk = (long) num;
		while (wk != 0) {
			cnt++;
			wk /= 10;
		}
		return cnt;
	}

解法を間違えたC問題

削減せずにそのまま要件通りに実装しました。TLEです。

	/**
	 * numN = A * B
	 * numNの約数を全列挙
	 */
	private void solveC() {
		long numN = nextLong();

		//		Map<Long, Long> wk = new HashMap<Long, Long>();
		//		for (long i = 1; i < numN; i++) {
		//			if (numN % i == 0) {
		//				wk.put((long) i, numN / i);
		//			}
		//		}

		Map<Long, Long> wk = LongStream.range(1, numN).filter(i -> numN % i == 0)
				.collect(
						() -> new HashMap<Long, Long>(),
						(t, i) -> t.put((long) i, numN / i),
						(t, u) -> t.putAll(u));

		//		long res = Long.MAX_VALUE;
		//		for (Entry<Long, Long> en : wk.entrySet()) {
		//			res = Math.min(res, chkDigit(Math.max(en.getKey(), en.getValue())));
		//		}

		OptionalLong hoge = wk.entrySet().stream().mapToLong(entryS -> chkDigit(Math.max(entryS.getKey(), entryS.getValue()))).min();

		out.println(hoge.getAsLong());
	}