ABC - 040- A&B&C

AtCoder ABC 040 A&B&C

AtCoder - 040

A問題

	private void solveA() {
		int numN = nextInt();
		int numX = nextInt();

		out.println(numN - numX > numX - 1 ? numX - 1 : numN - numX);
	}

B問題

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

		int res = 99999999;
		for (int i = 1; i <= numN; i++) {
			for (int j = 1; j <= numN; j++) {
				//タイルが何枚余るか
				int amari = numN - (i * j);
				//タイルを使い切っているならこれ以上の探索は無意味
				if (amari < 0) {
					break;
				}
				res = Math.min(Math.abs(i - j) + amari, res);
			}
		}

		out.println(res);
	}

C問題

• DPの一番初歩の形
  • 貰うDPと配るDPの両方を試した

private void solveC() {
		int numN = nextInt();
		int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();

		int[] dp = new int[numN];
		Arrays.fill(dp, Integer.MAX_VALUE - 1);

		/*
		 * 貰うDP
		 */
		//		dp[0] = 0;
		//		dp[1] = Math.abs(wk[1] - wk[0]);
		//		for (int i = 2; i < dp.length; i++) {
		//			for (int j = 1; j <= 2; j++) {
		//				dp[i] = Math.min(Math.abs(wk[i] - wk[i - j]) + dp[i - j], dp[i]);
		//			}
		//		}

		/*
		 * 配るDP
		 */
		dp[0] = 0;
		for (int i = 0; i < dp.length; i++) {
			for (int j = 1; j <= 2; j++) {
				if (i + j >= dp.length) {
					continue;
				}
				dp[i + j] = Math.min(Math.abs(wk[i] - wk[i + j]) + dp[i], dp[i + j]);
			}
		}

		out.println(dp[numN - 1]);
	}