ABC - 119 - A&B&C&D

AtCoder ABC 119 A&B&C&D

AtCoder - 119

A問題

• dateformatを利用

	private void solveA() {

		try (Scanner scanner = new Scanner(System.in)) {
			String date = "";
			date = scanner.next();
			SimpleDateFormat sdFormat = new SimpleDateFormat("yyyy/MM/dd");
			Date uDate = sdFormat.parse(date);
			Date tDate = sdFormat.parse("2019/04/30");

			int diff = tDate.compareTo(uDate);
			if (diff == 0) {
				System.out.println("Heisei");
			} else if (diff > 0) {
				System.out.println("Heisei");
			} else {
				System.out.println("TBD");
			}

		} catch (ParseException e) {
			e.printStackTrace();
		}
	}

B問題

• primitiveで桁考えるのが面倒なのでBigDecimalで処理

	private void solveB() {

		try (Scanner scanner = new Scanner(System.in)) {
			int numN = 0;
			numN = scanner.nextInt();
			BigDecimal[] wkKane = new BigDecimal[numN];
			String[] wkNaiyo = new String[numN];

			BigDecimal[] wkRes = new BigDecimal[numN];
			BigDecimal rate = new BigDecimal("380000.0");
			for (int i = 0; i < numN; i++) {
				wkKane[i] = new BigDecimal(scanner.next());
				wkNaiyo[i] = scanner.next();
				if (wkNaiyo[i].equals("BTC")) {
					wkRes[i] = wkKane[i].multiply(rate);
				} else {
					wkRes[i] = wkKane[i];
				}

			}

			BigDecimal res = BigDecimal.ZERO;
			for (int i = 0; i < wkRes.length; i++) {
				res = res.add(wkRes[i]);
			}

			System.out.println(res.setScale(4, RoundingMode.HALF_UP));

		}
	}

C問題

• 全探索

• 竹の使い方は4 通り

  • 使わない
  • 長さAの竹の材料
  • 長さBの竹の材料
  • 長さCの竹の材料

• 合成するパターンを全部試してみて、足りない竹の長さは延長or縮小魔法を使うことにする

  • 合成した竹が、目標の長さよりも長ければ縮小、短ければ延長
    • これは、$|目標の竹の長さ ; - ; 合成した竹の長さ|$ を調べればよい

	private void solveC2() {

		try (Scanner scanner = new Scanner(System.in)) {
			int numN = scanner.nextInt();
			int numA = scanner.nextInt();
			int numB = scanner.nextInt();
			int numC = scanner.nextInt();

			int[] wk = new int[numN];

			for (int i = 0; i < wk.length; i++) {
				wk[i] = scanner.nextInt();
			}

			System.out.println(dfsC2(numA, numB, numC, wk, 0, 0, 0, 0));

		}
	}

	private int dfsC2(int numA, int numB, int numC, int[] wk, int currentI, int a, int b, int c) {

		//竹の数を全部カウントし終わったら完了
		if (currentI >= wk.length) {
			/*
			 * a,b,c全部の竹が最低値をクリアすること
			 * -> 0以下の場合は竹を作れていないということでNG
			 *
			 * -30しているのは、竹を0以上にするのに合成のためのMPを加算してしまっているから
			 * -30=-10*3　（aを0以上、bを0以上、cを0以上にするために余分にMPを消費している）
			 */
			if (a > 0 && b > 0 && c > 0) {
				return Math.abs(numA - a) + Math.abs(numB - b) + Math.abs(numC - c) - 30;
			}
			/*
			 * ここに来たということは、竹を正確に合成できなかったということ
			 * -> 長さが0の竹がある
			 * 条件を満たしていないのでとりあえずINF的な値を返す
			 */
			return 999999999;
		}
		//何も合成しない（・・現状の長さでOKとする）
		int val0 = dfsC2(numA, numB, numC, wk, currentI + 1, a, b, c);
		/*
		 * aに竹を接ぐ
		 * +10は竹を接ぐためのMP
		 */

		int val1 = dfsC2(numA, numB, numC, wk, currentI + 1, a + wk[currentI], b, c) + 10;
		/*
		 * bに竹を接ぐ
		 * +10は竹を接ぐためのMP
		 */
		int val2 = dfsC2(numA, numB, numC, wk, currentI + 1, a, b + wk[currentI], c) + 10;
		/*
		 * cに竹を接ぐ
		 * +10は竹を接ぐためのMP
		 */
		int val3 = dfsC2(numA, numB, numC, wk, currentI + 1, a, b, c + wk[currentI]) + 10;

		return Math.min(Math.min(val0, val1), Math.min(val2, val3));
	}

D問題

• D問題

  • 二分探索

• 要点としては

  • x[i]に一番近い左右の神社を探索
  • x[i]に一番近い左右の寺を探索
  • 神社(×2)と寺(×2)の組み合わせでどの組み合わせが一番近いかを比較する

例として、図のように配置されているとした場合、あり得る組み合わせ（通過順）は8通り
8通り試すために、(s1,s2)(t1,t2)を探せばよい。

1. s1 -> t1
2. s1 -> t2
3. s2 -> t1
4. s2 -> t2
5. t1 -> s1
6. t1 -> s2
7. t2 -> s1
8. t2 -> s2

神社			s1			s2
寺					t1				t2
神社			s1						s2
寺					t1	t2
神社					s1	s2
寺		t1						t2

	private void solveD() {

		try (Scanner scanner = new Scanner(System.in)) {
			int numA = scanner.nextInt();
			int numB = scanner.nextInt();
			int numQ = scanner.nextInt();

			long inf = (long) Math.pow(10, 11);
			/*
			 * +2しているのは二分探索用に左右を追加したいから
			 */
			long[] s = new long[numA + 2];
			/*
			 * index範囲対象外にならないように、端っこを作っておく
			 * こうやっておけば、必ずどこかの神社がみつかる
			 */
			s[0] = inf * -1;
			s[numA + 1] = inf;
			for (int i = 1; i < numA + 1; i++) {
				s[i] = scanner.nextLong();
			}
			long[] t = new long[numB + 2];
			//index範囲対象外にならないように、端っこを作っておく
			t[0] = inf * -1;
			t[numB + 1] = inf;
			for (int i = 1; i < numB + 1; i++) {
				t[i] = scanner.nextLong();
			}
			long[] x = LongStream.range(0, numQ).map(i -> scanner.nextLong()).toArray();

			for (long d : x) {
				long res = Long.MAX_VALUE - 1;
				/*
				 * 二分探索したら、自分と一致または、自分より大きいものの内
				 * 一番近いindexが返ってくるのでそのひとつ前をとればx[i]の左右が取れる
				 * 正確には、ひとつ前は一番近くない可能性はある（普通に一致するindexが取れた場合）けど
				 * その場合、それを選択しなければいい話なので無視
				 */
				int sIndex = Arrays.binarySearch(s, d);
				sIndex = sIndex >= 0 ? sIndex : ~sIndex;
				int tIndex = Arrays.binarySearch(t, d);
				tIndex = tIndex >= 0 ? tIndex : ~tIndex;
				/*
				 * 出発地点x[i]に一番近い左右の神社
				 */
				for (int i = sIndex - 1; i <= sIndex; i++) {
					/*
					 * 出発地点x[i]に一番近い左右のお寺
					 */
					for (int j = tIndex - 1; j <= tIndex; j++) {
						long res1 = (long) (Math.abs(d - s[i]) + Math.abs(s[i] - t[j]));
						long res2 = (long) (Math.abs(d - t[j]) + Math.abs(s[i] - t[j]));
						res = Long.min(Long.min(res1, res2), res);
					}
				}
				System.out.println(res);
			}

		}
	}