LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@shihou22

ABC - 123- A&B&C&D

Last updated at Posted at 2019-04-07

AtCoder ABC 123 A&B&C&D

AtCoder - 123

2019/05/22
　問題名を追記

A - Five Antennas

  • A,B,C,D,Eすべての組み合わせで$>K$となるかどうかを判定する
    • $(A-B>K)$ , $(B-C>K)$ , $(C-D>K)$ , $(A-E>K)$, $(A-C>K)$ ・・・・・
  • 最大値と最小値の差もK以内でなければいけない
  • 配列に変えてソートし、最初と最後を比較すればよい
	private void solveA() {
		int numA = nextInt();
		int numB = nextInt();
		int numC = nextInt();
		int numD = nextInt();
		int numE = nextInt();
		int numK = nextInt();

		int[] wk = new int[] { numA, numB, numC, numD, numE };
		Arrays.sort(wk);
		if (wk[4] - wk[0] > numK) {
			out.println(":(");
			return;
		}

		out.println("Yay!");
	}

B - Five Dishes

  • 一番最後にどの料理を選ぶのか?で決まる

    • 途中でどの料理を選んでも、結局10の倍数分が来るまで待たないといけない
    • 一番最後の料理のみ、料理到着時の時刻が大切
      • 到着時刻を最速にするには
        • 10分で割り切れるものは途中で注文する
        • 10分で割り切れないものの内、1分に一番近い食べ物を一番最後に注文するとよい

  • 値を配列に詰めて独自のComparator作成してソート

    • 注文する順にソート
      • 10で割り切れるものは最初に、あとは余りが少ないものを後ろに

  • ソートした結果を単純に足していく

	private void solveB() {
		Integer[] wk = new Integer[5];
		for (int i = 0; i < wk.length; i++) {
			wk[i] = nextInt();
		}

		Arrays.sort(wk, new SortComparator());

		int res = 0;
		for (int i = 0; i < wk.length; i++) {

			/*
			 * 前の食べ物の端数を先に埋める
			 * 最後だったら端数埋めが不要なので
			 */
			if (res % 10 != 0) {
				int temp = 10 - res % 10;
				res += temp;
			}
			res += wk[i];
		}
		out.println(res);
	}

	private static class SortComparator implements Comparator<Integer> {

		@Override
		public int compare(Integer o1, Integer o2) {
			int sabun1 = (o1 % 10);
			int sabun2 = (o2 % 10);

			if (sabun1 == 0) {
				return -1;
			}
			if (sabun2 == 0) {
				return 1;
			}
			sabun1 = 10 - sabun1;
			sabun2 = 10 - sabun2;
			if (sabun1 < sabun2) {
				return -1;
			} else if (sabun1 < sabun2) {
				return 1;
			} else {
				return 0;
			}
		}

	}

B - Five Dishes：放送解法

  • 全探査
    • こちらのほうが自分の解法よりキレイ
  • 勉強になるテクニック
    • $(n+9)/10 * 10$
      • $(29+9)/10 $ -> $3$ # $+9して1桁目を切り捨てる$
      • $3 * 10$ -> $30$ # $*10して元の桁に戻す$
	private void solveB2() {
		Integer[] wk = new Integer[5];
		for (int i = 0; i < wk.length; i++) {
			wk[i] = nextInt();
		}

		List<Integer> wkList = new ArrayList<Integer>();

		//途中でこの料理を選んだ場合、何分かかるかを別のListに保持する
		for (int i = 0; i < wk.length; i++) {

			if (wk[i] % 10 == 0) {
				wkList.add(wk[i]);
			} else {
				//				wkList.add(wk[i] - wk[i] % 10 + 10);
				wkList.add((wk[i] + 9) / 10 * 10);
			}
		}

		/*
		 * 注文するものを全検査
		 * 二つのリストの内、最後に選択するものをどれにするのか？
		 * それを2重ループで表現している。
		 */
		int bestTime = Integer.MAX_VALUE;

		//最後に足すものを選択するループ
		for (int i = 0; i < wk.length; i++) {
			int sumTime = 0;
			//途中で足すものを選択するループ
			for (int j = 0; j < wk.length; j++) {
				/*
				 * iの番号については最後扱い
				 * i以外は途中で運ばれる食べ物扱い
				 */
				if (i == j) {
					sumTime += wk[j];
				} else {
					sumTime += wkList.get(j);
				}
			}
			bestTime = Math.min(sumTime, bestTime);
		}
		out.println(bestTime);
	}

C - Five Transportations

  • 律速段階がある場合、各段階の速度は律速と等速になる

各都市間の移動時間：すべて1（）
移動しなくてはいけない人数：N
移動の律速となる運搬能力：M
移動する都市数：5（->各都市の運搬能力=A,B,C,D,E）
全ての移動を完了するのに最低限必要な移動の時間：L

  1. 律速となる運搬能力を求める
    • $M=min(A,B,C,D,E)$
  2. 1分間に何人運搬可能か？ -> 最後の人が都市1に到着する時刻
    • $ceil(N/M)=X$　（ceilで最小の整数に変換）
  3. [2.]で最後の人を運ぶのに必要な最小の時間を足す

例：都市間の移動にかかる時間を1分/運ばなくてはいけない人数を5人とした場合の図

都市1 都市2 都市3 都市4 都市5 到着
移動にかかる時間 1分 1分 1分 1分 1分
運搬能力 1 1 1 1 1 1
1分後 1人
2分後 1人 1人
3分後 1人 1人 1人
4分後 1人 1人 1人 1人
5分後 1人(最後の一人) 1人 1人 1人 1人 1人
6分後 1人(最後の一人) 1人 1人 2人 2人
7分後 1人(最後の一人) 1人 3人 3人
8分後 1人(最後の一人) 4人 4人
9分後 5人 5人 
	private void solveC() {
		double numN = nextLong();

		long[] wk = new long[5];
		for (int i = 0; i < wk.length; i++) {
			wk[i] = nextLong();

		}

		Arrays.sort(wk);

		long res = (long) (Math.ceil(numN / (double) wk[0]) + (wk.length - 1));
		out.println(res);
	}

D - Cake 123：1(TLE)

  • 美味しさの合計

    • すべての組み合わせを試してTLE
    • 計算量の削減が必要

  • 解説動画をそのまま実装してみたところ、javaだとTLEになります。。。

  • ソートの量を減らしてみてもTLEになります。。。

	private void solveD2() {
		long numX = nextLong();
		long numY = nextLong();
		long numZ = nextLong();
		long numK = nextLong();

		long[] aX = LongStream.range(0, numX).map(i -> nextLong()).toArray();
		long[] aY = LongStream.range(0, numY).map(i -> nextLong()).toArray();
		long[] aZ = LongStream.range(0, numZ).map(i -> nextLong()).toArray();

		Arrays.sort(aZ);
		Collections.reverse(Arrays.asList(aZ));

		/*
		 * X-Yの組み合わせ
		 */
		List<Long> wkXY = new ArrayList<Long>();
		for (int i = 0; i < aX.length; i++) {
			for (int j = 0; j < aY.length; j++) {
				wkXY.add(aX[i] + aY[j]);
			}
		}

		/*
		 * 組み合わせの結果をソートして降順に
		 */
		Collections.sort(wkXY, (x, y) -> Long.compare(x, y) * -1);

		/*
		 *  X-Yの組み合わせとZの組み合わせを作成
		 *  ただし、X-Yに関しては、X-Yの組み合わせの内、K番目より先の組み合わせはやる必要がない
		 *  なぜなら、Zを組み合わせた時点で必ず、K番目の組み合わせより大きくなる
		 */
		List<Long> wkXYZ = new ArrayList<Long>();
		for (int i = 0; i < Math.min(numK, wkXY.size()); i++) {
			for (int j = 0; j < aZ.length; j++) {
				wkXYZ.add(wkXY.get(i) + aZ[j]);
			}
		}

		Collections.sort(wkXYZ, (x, y) -> Long.compare(x, y) * -1);

		for (int i = 0; i < numK; i++) {
			out.println(wkXYZ.get(i));
		}

	}

D - Cake 123：2（計算量そのものを削減）


	/*
	 * Youtubeの解説動画
	 */
	private void solveD() {
		long numX = nextLong();
		long numY = nextLong();
		long numZ = nextLong();
		long numK = nextLong();

		List<Long> aX = new ArrayList<Long>();
		for (int i = 0; i < numX; i++) {
			aX.add(nextLong());
		}
		List<Long> aY = new ArrayList<Long>();
		for (int i = 0; i < numY; i++) {
			aY.add(nextLong());
		}
		List<Long> aZ = new ArrayList<Long>();
		for (int i = 0; i < numZ; i++) {
			aZ.add(nextLong());
		}

		Collections.sort(aX, (x, y) -> Long.compare(x, y) * -1);
		Collections.sort(aY, (x, y) -> Long.compare(x, y) * -1);
		Collections.sort(aZ, (x, y) -> Long.compare(x, y) * -1);

		List<Long> wkXYZ = new ArrayList<Long>();

		/*
		 * 組み合わせを試す
		 * 事前準備として、すべてのcollectionを降順にソートしておく
		 * （昇順でもいいけど、別途組み合わせ個数のカウンタを用意する必要があるので降順ソートが早い）
		 * ソートしておくことにより、組み合わせを試す際に合計が大きい順にListにaddできる
		 *
		 * Xの最大値->Yの最大値->Zの最大値
		 * Xの最大値->Yの最大値->Zの最大値-1
		 * ・
		 * ・
		 * Xの最大値->Yの最大値-1->Zの最大値
		 * ・
		 * ・
		 * Xの最大値-1->Yの最大値->Zの最大値
		 * Xの最大値-1->Yの最大値->Zの最大値-1
		 * ・
		 * ・
		 *
		 */
		for (int i = 0; i < aX.size(); i++) {
			for (int j = 0; j < aY.size(); j++) {
				/*
				 * X,Yの組み合わせの個数がKを超えた時点で
				 * Zの組み合わせを試す必要がないのでbreak
				 */
				if ((i + 1) * (j + 1) > numK) {
					break;
				}
				for (int k = 0; k < aZ.size(); k++) {
					/*
					 * 組み合わせの個数がKを超えたらこれ以上試す必要はないのでbreak
					 */
					if ((i + 1) * (j + 1) * (k + 1) > numK) {
						break;
					}
					wkXYZ.add(aX.get(i) + aY.get(j) + aZ.get(k));
				}
			}
		}

		Collections.sort(wkXYZ, (x, y) -> Long.compare(x, y) * -1);

		for (int i = 0; i < numK; i++) {
			out.println(wkXYZ.get(i));
		}

	}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?