AtCoder Beginner Contest 153 に参加した記録
AtCoder Beginner Contest 153 – AtCoder
ABC153 に参加しました。
結果はABCDEの5問ACでした。全体的に優しい難易度のコンテストという印象を持ちました。再帰関数やDPの典型問題もありましたしね。
EのDPをACするのに少しだけ時間がかかりましたが、それなりにすんなり解けました。F問題も時間をかけて取り組みましたが、残念ながら解けませんでした。
パフォーマンスは、水色1200くらいでレーティングは微増でした。なんにせよ典型問題をすんなり解けたので良かったです。
ということで問題を振り返ります。
A – Serval vs Monster
サーバルはモンスターと戦っています。
モンスターの体力は H です。
サーバルが攻撃を 1 回行うとモンスターの体力を A 減らすことができます。 攻撃以外の方法でモンスターの体力を減らすことはできません。
モンスターの体力を 0 以下にすればサーバルの勝ちです。
サーバルがモンスターに勝つために必要な攻撃の回数を求めてください。
同じような問題を以前見た気がします。
H がちょうど A で割り切れるときは H / A が答えになります。割り切れないときはもう一回攻撃したら倒せるので+1します。
var ans = H / A;
if (H % A > 0) ans++;
Console.WriteLine(ans);for文で回してもOKですし、H/A を小数で求めて切り上げで整数値にしてもOKです。
B – Common Raccoon vs Monster
アライグマはモンスターと戦っています。
モンスターの体力は H です。
アライグマは N 種類の必殺技を使うことができ、i 番目の必殺技を使うとモンスターの体力を Ai 減らすことができます。 必殺技を使う以外の方法でモンスターの体力を減らすことはできません。
モンスターの体力を 0 以下にすればアライグマの勝ちです。
アライグマが同じ必殺技を 2 度以上使うことなくモンスターに勝つことができるなら Yes を、できないなら No を出力してください。
必殺技のダメージ合計が H 以上になれば倒せます。
if (H <= A.Sum())
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}C – Fennec vs Monster
フェネックは N 体のモンスターと戦っています。
i 番目のモンスターの体力は Hi です。
フェネックは次の 2 種類の行動を行うことができます。
- 攻撃：モンスターを 1 体選んで攻撃することで、そのモンスターの体力を 1 減らす必殺技：モンスターを 1 体選んで必殺技を使うことで、そのモンスターの体力を 0 にする
- 攻撃と必殺技以外の方法でモンスターの体力を減らすことはできません。
全てのモンスターの体力を 0 以下にすればフェネックの勝ちです。
フェネックが K 回まで必殺技を使えるとき、モンスターに勝つまでに行う攻撃の回数 (必殺技は数えません) の最小値を求めてください。
K回の必殺技を、体力の多い敵から順番に必殺技を使うのが最適です。配列をソートしてK個分要素をスキップして、残ったものの合計が答えになります。
// 降順ソート
Array.Sort(H);
Array.Reverse(H);
// K個分スキップして残りを合計する
var ans = H.Skip(K).Sum();
Console.WriteLine(ans);D – Caracal vs Monster
カラカルはモンスターと戦っています。
モンスターの体力は H です。
カラカルはモンスターを 1 体選んで攻撃することができます。モンスターを攻撃したとき、攻撃対象のモンスターの体力に応じて、次のどちらかが起こります。
- モンスターの体力が 1 なら、そのモンスターの体力は 0 になる
- モンスターの体力が X>1 なら、そのモンスターは消滅し、体力が ⌊X/2⌋ のモンスターが新たに 2 体現れる
（⌊r⌋ は r を超えない最大の整数を表す）
全てのモンスターの体力を 0 以下にすればカラカルの勝ちです。
カラカルがモンスターに勝つまでに行う攻撃の回数の最小値を求めてください。
制約
1≤H≤1012
攻撃したら分裂する敵を何回攻撃すれば倒せるかという問題です。
これは再帰関数の典型問題です。
体力4のモンスターを攻撃すると体力2のモンスターが2体生まれます。この2体を再帰的に倒していくような計算を行います。
図を描くとわかりやすいです。
4 ┬ 2 ┬ 1
│ └ 1
└ 2 ┬ 1
└ 1こんな感じになります。
攻撃時に分裂して生まれる2体のモンスターは同じ体力なので1体を倒すのに必要な攻撃回数*2回の攻撃を行う必要があります。
コードにすると以下のようになります。
static void Main(string[] args)
{
var H = sc.ReadLong();
var ans = Rec(H);
Console.WriteLine(ans);
}
// 体力hの敵を倒すのに必要な攻撃回数を求める
static long Rec(long h)
{
if (h == 1) return 1;
var ret = 1 + Rec(h / 2) * 2;
return ret;
}体力が1の時は1回の攻撃で倒せます。1より大きい体力の場合、1回攻撃すると体力が h/2 の2体のモンスターに分裂するので、この体力で再帰的に関数を呼び出しています。
同じ体力のモンスターを2回倒すので単純に攻撃回数を2倍してやればそれでよいです。
これで答えが求まります。メモ化は必要ありません。
ここまではすんなりと解けました。
E – Crested Ibis vs Monster
トキはモンスターと戦っています。
モンスターの体力は H です。
トキは N 種類の魔法が使え、i 番目の魔法を使うと、モンスターの体力を Ai 減らすことができますが、トキの魔力を Bi 消耗します。
同じ魔法は何度でも使うことができます。魔法以外の方法でモンスターの体力を減らすことはできません。
モンスターの体力を 0 以下にすればトキの勝ちです。
トキがモンスターに勝つまでに消耗する魔力の合計の最小値を求めてください。
制約
- 1≤H≤104
- 1≤N≤103
- 1≤Ai≤104
- 1≤Bi≤104
E問題です。AtCoder Problems によると、Difficultyが 900 位の問題です。
Dまでが簡単だったのでなんとしても解きたいところでした。
最初に思ったのはダメージ効率のいい(A/Bが大きい)魔法を最優先で使って、残りをいい感じに決めればよいと思いました。が、実装してうまくいかなかったので、考えを改めました。
そこで頭によぎったことがあって、以前に似たような問題で似たような考えで間違ったことがあった気がします。それを思い出した瞬間にDPで解けるとすぐに思いつきました。ということで以下コードです。
// 入力
var H = sc.ReadInt();
var N = sc.ReadInt();
var A = new int[N];
var B = new int[N];
for (int i = 0; i < N; i++)
{
A[i] = sc.ReadInt();
B[i] = sc.ReadInt();
}
// DPの初期化
var dp = new int[H + 1];
for (int i = 0; i < dp.Length; i++)
{
dp[i] = int.MaxValue;
}
dp[0] = 0;
// 現在のダメージ0..H
for (int i = 0; i < dp.Length; i++)
{
// ダメージiになる組み合わせがない場合
if (dp[i] == int.MaxValue) continue;
// すべての魔法を試す
for (int j = 0; j < N; j++)
{
var a = A[j];
var b = B[j];
// Hより大きい場合はHにしておく
var ni = Math.Min(H, i + a);
// ダメージniを与えるのにより小さい魔力で実現できる場合は更新
dp[ni] = Math.Min(dp[ni], dp[i] + b);
}
}
var ans = dp[H];
Console.WriteLine(ans);体力Hが 104、魔法の数Nが 103 なので、すべての体力の状態からすべての魔法での遷移を試すと 107 になって計算量的にもOKです。107 だと計算量的にはぎりぎりですが、DPの場合は中身の処理自体が単純なのでまず間に合います。
DPを
DP[i] = モンスターの体力を i 減らすため消耗する魔力の最小値」
とすると考えて実装します。
具体的にDPでやっていることは以下の通りです。
- 体力が0の状態での消費魔力を0とします。これが初期状態です。
- 0..H-1の範囲ですべての魔法を試したときのダメージ遷移を試す。
- ダメージniを与えるのにより小さい魔力で実現できる場合はdp[ni]を更新します。
うまく説明するのが難しいですがこんな感じです。
結局はDPにたどり着いてからは実装に迷うことなく解けました。
結構典型的なDP問題だと思いますが、勉強していてよかったです。
F – Silver Fox vs Monster
Difficultyが水色の問題でしたが、私には難しかったです。。。精進します。
水色になるのはまだ壁がありそうです。。。
以上。
