AtCoder ABC 013 A&B&C
A - A
- charとして扱えば
X-'A'で0になる。Aのとき1なので+1すればよい。
private void solveA() {
char x = next().charAt(0);
out.println(x - 'A' + 1);
}
B - 錠
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 - 節制
満点解法(100点解法の式を変形)
- 自力では満点取れなかったのでeditorialを見てみたところ、、、
- 式を変形すれば、jをループではなく一意に決めることができた
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);
/*
* 満腹度を判定する式は以下
* long currentManpuku = (h + i * b + j * d) - ((n - (i + j)) * e)
* 上記式の内、jが質素な食事をする日。
* -質素な食事でも豪勢な食事でもどちらでもいいので日を決める。
* そして、i,jの二重ループのうち片方を使わずに済ませる。
* ->片方の食事の日数を決めたらもう片方の食事の日数が自動的に決まるはず。
*
* 満腹度は0を下回ってはいけないので、
* (h + i * b + j * d) - ((n - (i + j)) * e) > 0
* (h + i * b + j * d) - (n - i - j) * e > 0
* このうち、iまたはjを求める形に変形
* ここでは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)
* 上記式で質素な食事をする最低日数は導出できた
* ただし、条件として
* - jは0以上（マイナスなら質素な食事をとる必要がない）
* - jは ((n - i) * e - i * b - h) / (d + e) "より大きく"ないといけない
* ※仮決めしたiをもとに算出した結果より大きくないといけない
* ※そのため、計算結果に+1している
* ※((n - i) * e - i * b - h) / (d + e)の結果が3の場合、jとして有効な値は4以上
*/
long j = 0;
/*
* 正負の判定を以下の式の結果で行うと端数がずれてしまったので、
* ((n - i) * e - i * b - h) / (d + e)
* 一旦、分子だけで正負判定を行う（分母が正なので分子の正負だけでいいはず）
* (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)
* なので、((n - i) * e - i * b - h) / (d + e)に+1することによって
* j > としている。
* +1しないと jが((n - i) * e - i * b - h) / (d + e)より大きくならない
*/
j = ((n - i) * e - i * b - h) / (d + e) + 1;
}
cost = Long.min(i * a + j * c, cost);
}
out.println(cost);
}
ループ(100点解法)
-
最後の1点は取れなかった
-
こざかしく再帰とかではなくループを回す
- そもそも、普通の食事と質素な食事をとれるだけ取って、その後に食事を抜けばいい
- 食事を抜くのを最後に持ってくる
- 食事を抜く日数は、普通の食事をした日数と質素な食事をした日数から求められる
- そもそも、普通の食事と質素な食事をとれるだけ取って、その後に食事を抜けばいい
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;
//豪勢な食事
for (long i = 0; i <= n; i++) {
//質素な食事
for (long j = 0; j <= n; j++) {
//残りの日数、食事を抜いて満腹度を確認
long currentManpuku = (h + i * b + j * d) - ((n - (i + j)) * e);
//満腹度が0より大きいのでこの食事回数は採用
if (currentManpuku > 0) {
cost = Long.min(i * a + j * c, cost);
}
}
}
out.println(cost);
}
再帰(10点)
- 全然間に合わない
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版(50点)
- 50点までしか取れない
- 100点をとるためにはDP用の配列を $ 10^5 $ とらないといけないが、確保したらMLEになってしまう
- おそらく、DPでは解けない？？？
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]:=i日目に満足度jの時の食費の最小値
*/
// 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;
/*
* 次の日の食事を考える（配るDP）
*
* 普通の食事 : dp[i+1][j+b]=min(dp[i+1][j+b],dp[i][j]+a)
* ->
* 次の日(i+1)の満腹度(j+b)でのコスト(dp[i+1[j+b])は、
* 前日(i)の満腹度(j)のコスト(dp[i][j])にaを足したもの(dp[i][j]+a)
* の内、コストが低いもの（初期値はINF埋め&別の食事を選択したほうがコストが安い場合があるので）
* ※i+1日目にj+bの満腹度はあったりなかったりする
*
* 質素な食事 : dp[i+1][j+d]=min(dp[i+1][j+d],dp[i][j]+c)
* 食事抜き : dp[i+1][j−e]=min(dp[i+1][j−e],dp[i][j])
* ->
* j−e > 0であることに注意
*/
for (int i = 0; i < n; i++) {
for (int j = 0; j < SATISFY_MAX; j++) {
/*
* この日は存在しない
*/
if (dp[i][j] == Long.MAX_VALUE) {
continue;
}
/*
* 次の日の普通な食事
*/
dp[i + 1][j + b] = Long.min(dp[i + 1][j + b], dp[i][j] + a);
/*
* 次の日の質素な食事
*/
dp[i + 1][j + d] = Long.min(dp[i + 1][j + d], dp[i][j] + c);
/*
* 食事抜き
*/
if (j - e > 0) {
dp[i + 1][j - e] = Long.min(dp[i + 1][j - e], dp[i][j]);
}
}
}
long res = Long.MAX_VALUE;
/*
* n日目に最低コストの満腹度を調査
*/
for (int i = 0; i < SATISFY_MAX; i++) {
res = Long.min(res, dp[n][i]);
}
out.println(res);
}