AtCoder Beginner Contest 153の解説
全完です！嬉しいです！
時間が余ったので解説を書くことにしました…！
A - Serval vs Monster
小数点以下切り上げの割り算をする問題です。
forループを回して実際にシミュレーションをして解くこともできますが、このような「Aを最低何回使ったらH以上になるか？」みたいな問題は「(H+A-1)/A」で一発で求めることもできるので、覚えておくと便利です。
B - Common Raccoon vs Monster
アライグマが同じ必殺技を使わないように相手にダメージをいっぱい与えたいですね…
よく考えると、「全ての必殺技を1つずつ出せばいい！」ということが分かります。全ての必殺技を使ってそのダメージ合計が敵の体力に届かない（合計＜体力）の場合、相手を倒すことができません。
実装としては、forループを回しながら合計を数える変数に足していく…という方法が使えますが、C++の場合vectorを使うことでaccumulate(v.begin(), v.end(), 0)のように1行で書くこともできるので、覚えておくといいでしょう。
C - Fennec vs Monster
問題文を理解すると、「必殺技は使い切りたい！！」という気分になります。どの相手に必殺技を使うのが最適なのでしょうか。
よーく考えると、強い敵に必殺技を使うほうが良い、と分かります。巨大セルリアンを必殺技で倒しておいたほうが、あとは弱いセルリアンを倒したら全体として楽に倒せますね。
で、実装なのですが、C++の場合ソートを使うと楽です。ソートをすると右から大きい順に並ぶことになります。
ここで、体力をあらかじめ0にする…ということは既に倒されている→無視していい、ということなので、右からK体の体力を数えないように、つまりfor (int i = 0; i < N - K; i++) ans += v[i]; のようにすれば楽に実装ができます。
D - Caracal vs Monster
実際にどういうふうに分裂するのか、図に描いてみましょう。
それぞれの段ごとの縦線の本数が、1,2,4,8…と2倍になっています。段の高さを求めてしまえば、段の高さだけ1+2+4+…をすれば答えが求められることが分かります。段の高さは実際にシミュレーションをするといいです。半分、またその半分…となっていくので計算回数は意外と少なく済みます。
E - Crested Ibis vs Monster
ここから説明が雑になっていきます。
パッと見ですが、貪欲だと最後のあたりの処理で困っちゃうことが分かります。なので動的計画法を使いたいな…というお気持ちになります。
蟻本を読んだことがある人は、一瞬58ページの個数制限なしナップサック問題かな？と思うかもしれません。
しかしこの問題のミソは制約です。敵の体力が最大で10000、使える魔法も最大1000種類です。
なので、「dp[i] // 攻撃力の総和をiにするために必要なトキの魔力」という風にして、それらをまずはINFで初期化、dp[0] = 0; をしてから下から上るように配るDPをして、dp[H以上]の最小値を出力すればいいです。O(HN)で間に合います。
Hがたかだか10000、攻撃力もたかだか10000なので、dp[100000]のように大きめに配列を持っておくと、配列外参照を考える必要がなくなるので実装が簡単になります。
F - Silver Fox vs Monster
まず問題文を読みます。図に描いて表すのですが、ここでx-D以上x-D以下の範囲…と描くより、幅D*2+1の攻撃だ！！と考えたほうが楽になります。
ここで、数直線上に並んだものに区間を〇〇していく、という辺りで、あれ？なにか聞こえる？
…最小を求めなさい…
…Face…
…Face The…
…Face The Right Way（蟻本p.139）を思い出すのじゃ…
という声が聞こえてきます。ウソです。言い過ぎました。すいません…
このFace The Right Wayで使った考え方は、「左端のものから順番に考えていくと、それぞれ何回反転させればいいかが簡単に求められる」ということです。この問題でも、左端から考えていくと考えやすくなります。
今回の問題では「あと何回攻撃するべきか」というのが簡単に求められます。左端の敵のそのときの体力がH、攻撃力がAのとき、最低何回攻撃するべきか…そうです！A問題で問われたことと同じことが問われています。(H+A-1)/Aが使えますね。その回数だけ攻撃をすればいいことが分かります。
でも、例えば左端が「あと5回攻撃が必要！」と分かった所で、どのように攻撃するのが一番区間の使い方として賢いのでしょうか…？
よーく考えると、その部分を左端にして攻撃するのが一番いい、ということが分かります。
区間を一様に減らす…ということは遅延セグメント木が使えそうです…！
左から登場する順に体力を並べた配列を元に遅延セグメント木を作ります。
i番目の敵を左端で攻撃するとして、攻撃が重なる範囲までの敵の体力を-Aしたいので、ここで左から登場する順に敵の位置を並べた配列を使って、攻撃が何番目の敵まで当たるのかをlower_boundで求めて（右端の位置を使うといいです）、i番目の敵から二分探索で求めた位置までの区間をを(H+A-1)/A * -Aすればいいです。
あとは、左から順番に「体力が残っていれば攻撃する」を繰り返し、それをカウントしていけばいいです…！
僕はupper_boundを書いて1WAしました。気をつけましょう…
以上！
