ABC - 092- A&B&C

AtCoder ABC 092 A&B&C

AtCoder - 092

A問題

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

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

			int wkBus = numA < numB ? numA : numB;
			int wkTrain = numC < numD ? numC : numD;

			System.out.println(wkBus + wkTrain);

			System.out.println("");

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

B問題

• $day = 1A+1 , 2A+1 , 3A+1 , 4A+1 , 5A+1 ,6A+1 , 7A+1 , , , , $

	private void solveB() {
		Scanner scanner = null;
		int numN = 0;
		int numD = 0;
		int numX = 0;

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

			int[] wk = new int[numN];

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

			int res = numX;
			for (int i = 0; i < numN; i++) {
				//とりあえずD回ぶん回せば足りる
				for (int j = 0; j < numD; j++) {
					//System.out.println((i + 1) + ":人目");
					if (j == 0) {
						/*
						 * 1日目は必ず食べる
						 * System.out.println(j + 1 + " :day");
						 */
						res++;
					} else {
						/*
						 * day = 1A+1,2A+1,3A+1,4A+1,5A+1,,,,,,
						 */
						int day = (j) * wk[i] + 1;
						if (day <= numD) {
							//System.out.println(day + " :day");
							res++;
						} else {
							break;
						}
					}
				}
			}

			System.out.println(res);

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

C問題

• 全探索だとTLEになるので累積和に修正

1. 先に全ての金額を生成しておく
2. 生成した金額を結果用の配列にfillをする
3. 結果の配列に、地点iを飛ばした場合の金額を計算して埋めていく

• 詳細はコードのコメント

	private void solveC2() {

		try (Scanner scanner = new Scanner(System.in)) {

			int numN = scanner.nextInt();

			int[] wk = new int[numN + 1];
			//最初に全てを回ったときの金額を生成しておく
			int[] result = new int[numN + 1];

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

			int cnt = 0;
			/*
			 * 観光スポット i-1 から i に移動してくるための金額の総和を算出しておく
			 */
			for (int i = 0; i < wk.length; i++) {
				if (i == 0)
					continue;
				cnt += Math.abs(wk[i] - wk[i - 1]);
			}
			//最終地点から最初の地点まではループしているのでそれも足す
			cnt += Math.abs(wk[wk.length - 1] - wk[0]);

			/*
			 * 配列に全てを当てはめておく
			 * この配列を元に、各地点を飛ばした場合の金額を足し引きする。
			 */
			Arrays.fill(result, cnt);

			/*
			 * 訪問を取りやめた場合の金額計算
			 */
			for (int i = 0; i < result.length; i++) {
				if (i == 0) {
					//スタート地点は0円でリセット
					result[i] = 0;
					continue;
				}
				/*
				 * resultには全ての地点をきちんと訪問した場合の金額でfillされている
				 * ここでは、地点iの訪問取り止めた場合の金額を計算して入れなおしている
				 * 地点iを飛ばす場合、金額を二つ考える必要がある
				 * i-1 , i , i+1 と3地点あるところ、
				 * i-1 ,   , i+1 と2地点にしなくてはいけない
				 * １：地点[i]-[i-1]の金額
				 * ２：地点[i+1]-[i]の金額
				 * 上記2つの金額を引き、新たに
				 * [i+1]-[i-1] を足さなくてはいけない
				 *
				 */
				result[i] -= Math.abs(wk[i] - wk[i - 1]);

				if (1 <= i && i < result.length - 1) {
					result[i] -= Math.abs(wk[i + 1] - wk[i]);
					result[i] += Math.abs(wk[i + 1] - wk[i - 1]);
				} else if (i == result.length - 1) {
					//最後の地点はループで処理できないので特別処理
					result[i] -= Math.abs(wk[0] - wk[i]);
					result[i] += Math.abs(wk[0] - wk[i - 1]);
				}

			}

			/*
			 * iを飛ばした場合の金額を全て出力
			 */
			for (int i = 0; i < result.length; i++) {
				if (i == 0)
					continue;
				System.out.println(result[i]);
			}

		}
	}

C問題：TLE Version

• 愚直に全探索した
• 通るけど、時間掛かりすぎ

	/*
	 * TLE version
	 */
	private void solveC() {

		try (Scanner scanner = new Scanner(System.in)) {

			int numN = scanner.nextInt();

			int[] wk = new int[numN + 1];
			int[] result = new int[numN + 1];

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

			for (int i = 1; i <= numN; i++) {
				for (int j = 1; j <= numN; j++) {
					if (i == j) {
					} else if (i + 1 == j) {
						result[i] += Math.abs(wk[j] - wk[j - 2]);
					} else {
						result[i] += Math.abs(wk[j] - wk[j - 1]);
					}

					if (j == wk.length - 1) {
						if (i == j) {
							result[i] += Math.abs(wk[j - 1] - wk[0]);
						} else {
							result[i] += Math.abs(wk[j] - wk[0]);
						}
					}
				}
			}

			for (int i = 0; i < result.length; i++) {
				if (i == 0)
					continue;
				System.out.println(result[i]);
			}

		}
	}