ABC - 094- A&B&C

AtCoder ABC 094 A&B&C

AtCoder - 094

A問題

• 猫がA
• 猫＋犬がB
• 猫がX匹いる条件は
  • $A \leqq X$
  • $X \leqq A+B$

	private void solveA() {
		Scanner scanner = null;
		int numA = 0;
		int numB = 0;
		int numX = 0;

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

			if (numX - numA <= numB && numA <= numX) {
				System.out.println("YES");
			} else {
				System.out.println("NO");
			}

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

B問題

1. 料金所の箇所を記録する
2. XからマスNまで移動した場合の金額を算出する
3. Xからマス0まで移動した場合の金額を算出する
4. [2]と[3] を比較する

	private void solveB() {

		try (Scanner scanner = new Scanner(System.in)) {
			int numN = scanner.nextInt();
			int numM = scanner.nextInt();
			int numX = scanner.nextInt();

			Set<Integer> wk = new HashSet<Integer>();

			for (int i = 0; i < numM; i++) {
				wk.add(scanner.nextInt());
			}
			int res1 = 0;
			for (int i = numX; i <= numN; i++) {
				if (wk.contains(i)) {
					res1++;
				}

			}
			int res2 = 0;
			for (int i = 0; i <= numX; i++) {
				if (wk.contains(i)) {
					res2++;
				}

			}

			System.out.println(Math.min(res1, res2));

		}
	}

C問題

• 普通に全探索を行うとTLEなので計算量を削減

• $l が奇数のとき，l個の数a_1,a_2,...,a_l$ の中央値は $(l+1)/2$ 番目に大きい値

• 偶数の数列から'i番目'を抜くので、数列は奇数となり上記の公式に当てはまる

• 問題は、　$i番目$を抜いたときに中央値はどのように変化するのか？

  • 偶数の時の中央値より大きければ、中央値の取得箇所が右
  • 偶数の時の中央値より小さければ、中央値の取得箇所が左
  • ただ、偶数の時の中央値を取得すると小数点が発生するため、最初から両方の中央値を取得しておき、片方の数値で判定すると誤差が出ない

	1	2	3	4	5	6	7	8	9	10
中央値の位置					↑	↑					偶数なので5と6の平均

	1	2	3	4	5	6	7	8	9
中央値の位置					↑						10の位置を抜いた

		2	3	4	5	6	7	8	9	10
中央値の位置						↑					1の位置を抜いた

private void solveC() {

		try (Scanner scanner = new Scanner(System.in)) {
			int numN = scanner.nextInt();
			//入力値
			long[] wk = new long[numN];
			//中央値算出用の配列
			long[] wk2 = new long[numN];

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

			//中央値の算出
			Arrays.sort(wk2);

			//中央値の準備（１：中央値より大きい位置が除外された時の中央値　２：中央値より小さい値が除外された時の中央値）
			long m1 = wk2[(numN / 2) - 1];
			long m2 = wk2[(numN / 2)];

			for (int i = 0; i < wk.length; i++) {
				if (wk[i] <= m1) {
					System.out.println(m2);
				} else {
					System.out.println(m1);
				}
			}
		}
	}