ABC --013-A & B & C

AtCoder ABC 013 A&B&C AtCoder - 013

A - A

--If treated as char, it becomes 0 with X-'A'. When ʻA`, it is 1, so you can add +1.

	private void solveA() {
		char x = next().charAt(0);

		out.println(x - 'A' + 1);
	}

B-Lock

	private void solveB() {
		int a = nextInt();
		int b = nextInt();
		int wkA = Integer.max(a, b);
		int wkB = Integer.min(a, b);

		out.println(Integer.min(wkA - wkB, (10 - wkA) + wkB));
	}

C-Temperance

Perfect score method (transformed formula of 100 point solution method)

――I couldn't get the perfect score on my own, so when I looked at the editorial, ... --By transforming the expression, j could be uniquely determined instead of a loop.

	private void solveC3() {
		long n = nextLong();
		long h = nextLong();
		long a = nextLong();
		long b = nextLong();
		long c = nextLong();
		long d = nextLong();
		long e = nextLong();

		long cost = Long.MAX_VALUE;
		for (long i = 0; i <= n; i++) {
			//			long j = ((n - i) * e - h - b * i) / (d + e);
			//			long j = ceil((n - i) * e - h - b * i , d + e);

			/*
			 *The formula for determining satiety is as follows
			 * long currentManpuku = (h + i * b + j * d) - ((n - (i + j)) * e)
			 *The day when j has a simple meal in the above formula.
			 * -It doesn't matter whether it's a simple meal or a big meal, so decide the day.
			 *And i,You don't have to use one of the double loops in j.
			 * ->If you decide the number of days for one meal, the number of days for the other meal should be decided automatically.
			 *
			 *Satiety should not be less than 0, so
			 * (h + i * b + j * d) - ((n - (i + j)) * e) > 0
			 * (h + i * b + j * d) - (n - i - j) * e > 0
			 *Of these, transform into the form that finds i or j
			 *Here, it transforms into the formula for finding j
			 * h + i * b + j * d - n * e + i * e + j * e > 0
			 * j * d + j * e                             > - h - i * b + n * e - i * e
			 * j * (d + e)                               > (n - i) * e - i * b - h
			 * j                                         > ((n - i) * e - i * b - h) / (d + e)
			 *The minimum number of days to eat a simple meal could be derived from the above formula.
			 *However, as a condition
			 *  -j is 0 or more (minus means you don't have to eat a simple meal)
			 *  -j is((n - i) * e - i * b - h) / (d + e) "Larger"Must be
			 ** Must be larger than the result calculated based on the tentatively decided i
			 ** Therefore, in the calculation result+1
			 *    ※((n - i) * e - i * b - h) / (d + e)If the result of is 3, the valid value for j is 4 or more.
			 */

			long j = 0;
			/*
			 *When the positive / negative judgment was made based on the result of the following formula, the fraction was shifted, so
			 *   ((n - i) * e - i * b - h) / (d + e)
			 *Once, the positive / negative judgment is made only with the numerator (since the denominator is positive, only the positive / negative of the numerator should be sufficient)
			 *   (n - i) * e - i * b - h
			 *   (i - n) * e + i * b + h < 0
			 */
			if ((n - i) * e - i * b - h > 0) {
				/*
				 * j > ((n - i) * e - i * b - h) / (d + e)
				 *So((n - i) * e - i * b - h) / (d + e)To+1することToよって
				 * j >It is said.
				 * +1 or j((n - i) * e - i * b - h) / (d + e)Will not grow larger
				 */
				j = ((n - i) * e - i * b - h) / (d + e) + 1;
			}
			cost = Long.min(i * a + j * c, cost);
		}
		out.println(cost);
	}

Loop (100-point solution)

――I didn't get the last one

――Turn a loop instead of recursion ――In the first place, you should eat as much as you can eat a normal meal and a simple meal, and then skip the meal. ――Bring the last meal ――The number of days to skip a meal is calculated from the number of days you ate a normal meal and the number of days you ate a simple meal.

	private void solveC2() {
		long n = nextLong();
		long h = nextLong();
		long a = nextLong();
		long b = nextLong();
		long c = nextLong();
		long d = nextLong();
		long e = nextLong();

		long cost = Long.MAX_VALUE;
		//Gorgeous meal
		for (long i = 0; i <= n; i++) {
			//Simple meal
			for (long j = 0; j <= n; j++) {
				//Check your fullness by skipping meals for the remaining days
				long currentManpuku = (h + i * b + j * d) - ((n - (i + j)) * e);
				//This number of meals is adopted because the degree of fullness is greater than 0
				if (currentManpuku > 0) {
					cost = Long.min(i * a + j * c, cost);
				}
			}
		}
		out.println(cost);
	}

Recursion (10 points)

――I can't make it at all

	private void solveC() {
		int n = nextInt();
		int h = nextInt();
		a = nextInt();
		b = nextInt();
		c = nextInt();
		d = nextInt();
		e = nextInt();

		Map<Long, Long> memo = new HashMap<Long, Long>();
		long res = recursiveC(n, 0, 0, h, memo);
		out.println(res);
	}

	int a;
	int b;
	int c;
	int d;
	int e;

	private long recursiveC(int n, long currentDay, long cost, long manpuku, Map<Long, Long> memo) {
		if (manpuku <= 0) {
			return Long.MAX_VALUE;
		}
		if (memo.getOrDefault(currentDay, Long.MAX_VALUE) < cost) {
			return memo.get(currentDay);
		} else {
			memo.put(currentDay, cost);
		}
		if (currentDay >= n) {
			return cost;
		}

		long val1 = recursiveC(n, currentDay + 1, cost + a, manpuku + b, memo);
		long val2 = recursiveC(n, currentDay + 1, cost + c, manpuku + d, memo);
		long val3 = recursiveC(n, currentDay + 1, cost, manpuku - e, memo);
		long wk = (val2 <= val3) ? val2 : val3;
		long wk2 = (val1 <= wk) ? val1 : wk;
		memo.put(currentDay, wk2);
		return wk2;
	}

DP version (50 points)

--You can only get up to 50 points --In order to get 100 points, you have to make an array for DP for $ 10 ^ 5 $, but if you secure it, it will be MLE. ――Maybe DP can't solve it? ?? ??

	private void solveC4() {
		int n = nextInt();
		int h = nextInt();
		int a = nextInt();
		int b = nextInt();
		int c = nextInt();
		int d = nextInt();
		int e = nextInt();

		/*
		 * dp[i][j]:=Minimum value of food expenses when satisfaction j on day i
		 */
		//		final int DAY_MAX = 500005;
		final int DAY_MAX = n + 5;
		final int SATISFY_MAX = 100005;
		long[][] dp = new long[DAY_MAX][SATISFY_MAX];
		for (int i = 0; i < DAY_MAX; i++) {
			Arrays.fill(dp[i], Long.MAX_VALUE);
		}
		dp[0][h] = 0;

		/*
		 *Think about the next day's meal (DP to distribute)
		 *
		 *Ordinary meal: dp[i+1][j+b]=min(dp[i+1][j+b],dp[i][j]+a)
		 * ->
		 *Next day(i+1)Satiety(j+b)Cost at(dp[i+1[j+b])Is
		 *The day before(i)Satiety(j)Cost(dp[i][j])Add a to(dp[i][j]+a)
		 *Of these, the one with the lowest cost (initial value is filled with INF)&(Because it may be cheaper to choose a different meal)
		 *  ※i+1st day j+b may or may not be full
		 *
		 *Simple meal: dp[i+1][j+d]=min(dp[i+1][j+d],dp[i][j]+c)
		 *Without meals: dp[i+1][j−e]=min(dp[i+1][j−e],dp[i][j])
		 * ->
		 * j−e >Note that it is 0
		 */
		for (int i = 0; i < n; i++) {

			for (int j = 0; j < SATISFY_MAX; j++) {

				/*
				 *This day does not exist
				 */
				if (dp[i][j] == Long.MAX_VALUE) {
					continue;
				}

				/*
				 *Normal meal the next day
				 */
				dp[i + 1][j + b] = Long.min(dp[i + 1][j + b], dp[i][j] + a);
				/*
				 *The next day's simple meal
				 */
				dp[i + 1][j + d] = Long.min(dp[i + 1][j + d], dp[i][j] + c);

				/*
				 *Without meals
				 */
				if (j - e > 0) {
					dp[i + 1][j - e] = Long.min(dp[i + 1][j - e], dp[i][j]);
				}
			}
		}

		long res = Long.MAX_VALUE;
		/*
		 *Investigate the lowest cost satiety on day n
		 */
		for (int i = 0; i < SATISFY_MAX; i++) {
			res = Long.min(res, dp[n][i]);
		}
		out.println(res);
	}

Recommended Posts

ABC --013-A & B & C
ABC --023 --A & B & C
ABC --036-A & B & C
ABC --010 --A & B & C
ABC --028 --A & B & C
ABC --015 --A & B & C
ABC --128 --A & B & C
ABC --012-A & B & C
ABC --018 --A & B & C
ABC --054 --A & B & C
ABC --017 --A & B & C
ABC --029- A & B & C
ABC --022 --A & B & C
ABC --019 --A & B & C
ABC --020 --A & B & C
ABC --030- A & B & C
ABC --127 --A & B & C
ABC --007 --A & B & C
ABC --132- A & B & C
ABC --026 --A & B & C
ABC --014- A & B & C
ABC --016 --A & B & C
ABC --011-A & B & C
ABC --031 --A & B & C
ABC --021 --A & B & C
ABC --025 --A & B & C
ABC --024 --A & B & C
ABC --027 --A & B & C
ABC --080- A & B & C
ABC --129- A & B & C & D
ABC --133- A & B & C & D
ABC --122 --A & B & C & D
ABC --125- A & B & C & D
ABC --130- A & B & C & D
ABC --126 --A & B & C & D
ABC --134- A & B & C & D & E
ABC --131- A & B & C & D & E
diverta 2019 Programming Contest A & B & C & D
AtCoder Beginner Contest 169 A, B, C with ruby
atcoder ABC113 C problem
ABC093 C --Same Integers
atcoder ABC115 C problem
AtCoder Beginner Contest 170 A, B, C up to ruby
A person writing C ++ tried writing Java
Make a SOAP call in C #
Call a C function from Swift
NLP4J [006-034] 100 language processing knocks with NLP4J # 34 "A B"