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);
}
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));
}
――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);
}
――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);
}
――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;
}
--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