AtCoder Beginner Contest 153に参加しました

昨日のABC153に参加しました。

予定があり時間通りには参加できませんでしたが、一通り目を通して解けそうなものは解き切ることができました。ケアレスミスでB、Cで一度ずつWAを出しましたが、四完出来たのでかなり嬉しかったです。

参考として自分のACだったコードを載せるために、一つ前のブログで書いた内容のほかに下記記事を参考にVSCodeの機能を拡張しました。

co.bsnws.net

特にスクショの取り方については追記することはありませんが、コードを保存する際にファイル名を「(任意の文字列).cpp」としていないとコードが色付きで表示されませんでした。そういえば画像の保存でも末尾に.jpegとか.pngとかついてたなあ、ということを思い出すまでに少し時間がかかりました。あまり理解していませんがファイルを処理している方法(？)を表しているような気がする、くらいに認識しています。

わざわざ書く必要のないことかとも思ったのですが、私の情報技術に関する知識程度を示す例の一つになるかと思い書いておくことにしました。

今回VSCodeのスクショを載せますが、実際にコンテストに参加した際はAtCoder上のコードテスト機能を用いてコードを書いていました。今後はすべてVSCodeを利用してプログラミングをすることになると思います。

以下に私のAC回答と考えたことを記載します。また、私の使用言語はC++です。前回の記事で書いておくべきでしたが忘れていました。

復習が済み次第順次追記していく予定です。

A-Serval vs Monster

「問題文

サーバルはモンスターと戦っています。

モンスターの体力は $H$ です。

サーバルが攻撃を $1$ 回行うとモンスターの体力を $A$ 減らすことができます。 攻撃以外の方法でモンスターの体力を減らすことはできません。

モンスターの体力を $0$ 以下にすればサーバルの勝ちです。

サーバルがモンスターに勝つために必要な攻撃の回数を求めてください。

制約

• $1\le H\le {10}^4$
• $1\le A\le {10}^4$
• 入力中のすべての値は整数である。」

考えたこと

A*攻撃回数がモンスターの体力以上になる最小の回数を求めればいいので、(H + A - 1) / A としました。体力が一回の攻撃力で割り切れる場合と割り切れない場合で分けるのはめんどうなので一回で処理できるようにしました。精選１０問に出てきたと思います。

A-1をAで割った商は当然0になりますが、あまりが1以上あった場合は商が1になり、また余りがどれだけ大きくても当然商は2以上にはなりません。つまりHがAで割り切れた場合はHと(H + A - 1)のそれぞれをAで割った商は同じであり、HがAで割り切れなかった場合のみ攻撃回数が1回増えることになります。よって、この式を用いることで場合分けをすることなく体力以上の攻撃を加える最小回数を求めることができます。

A

B Common Raccoon vs Monster

「問題文

アライグマはモンスターと戦っています。

モンスターの体力は $H$ です。

アライグマは $N$ 種類の必殺技を使うことができ、$i$ 番目の必殺技を使うとモンスターの体力を $A_i$ 減らすことができます。 必殺技を使う以外の方法でモンスターの体力を減らすことはできません。

モンスターの体力を $0$ 以下にすればアライグマの勝ちです。

アライグマが同じ必殺技を $2$ 度以上使うことなくモンスターに勝つことができるなら Yes を、できないなら No を出力してください。

制約

• $1\le H\le {10}^9$
• $1\le N\le {10}^5$
• $1\le A_i\le {10}^4$
• 入力中のすべての値は整数である。」

考えたこと

必殺技の攻撃力を一度ずつ足した合計がモンスターの体力を上回っていたらYes、そうでなければNoを出力すればいいです。

vectorで必殺技の攻撃力を受け取り、そのたびに足していくことにしました。

B

C- Fennec vs Monster

「問題文

フェネックは $N$ 体のモンスターと戦っています。

$i$ 番目のモンスターの体力は $H_i$ です。

フェネックは次の $2$ 種類の行動を行うことができます。

• 攻撃：モンスターを $1$ 体選んで攻撃することで、そのモンスターの体力を $1$ 減らす
• 必殺技：モンスターを $1$ 体選んで必殺技を使うことで、そのモンスターの体力を $0$ にする

攻撃と必殺技以外の方法でモンスターの体力を減らすことはできません。

全てのモンスターの体力を $0$ 以下にすればフェネックの勝ちです。

フェネックが $K$ 回まで必殺技を使えるとき、モンスターに勝つまでに行う攻撃の回数 (必殺技は数えません) の最小値を求めてください。

制約

• $1\le N\le 2\times {10}^5$
• $0\le K\le 2\times {10}^5$
• $1\le H_i\le {10}^9$
• 入力中のすべての値は整数である。」

考えたこと

攻撃回数はモンスターの体力に依存するので、最小にするためには体力の多いモンスターから順に必殺技で倒していくことになります。必殺技を使い切ってもまだ残っているモンスターを攻撃で倒します。まず、必殺技の使用回数がモンスターの数を超えていた場合は攻撃回数は0回です。必殺技で倒しきれない場合体力の少ない順にソートして残りの(N - K)体のモンスターの体力を足していきます。制約を見るとint型で体力を受け取った場合オーバーフローする可能性があることが分かるので、私はAPG4をチラ見しながらlong longを使用しました。

C

D- Caracal vs Monster

「問題文

カラカルはモンスターと戦っています。

モンスターの体力は $H$ です。

カラカルはモンスターを $1$ 体選んで攻撃することができます。モンスターを攻撃したとき、攻撃対象のモンスターの体力に応じて、次のどちらかが起こります。

• モンスターの体力が $1$ なら、そのモンスターの体力は $0$ になる
• モンスターの体力が $X>1$ なら、そのモンスターは消滅し、体力が $\lfloor X/2\rfloor$ のモンスターが新たに $2$ 体現れる

（$\lfloor r\rfloor$ は $r$ を超えない最大の整数を表す）

全てのモンスターの体力を $0$ 以下にすればカラカルの勝ちです。

カラカルがモンスターに勝つまでに行う攻撃の回数の最小値を求めてください。

制約

• $1\le H\le {10}^{12}$
• 入力中のすべての値は整数である。」

考えたこと

最初はよくわかりませんでしたが、攻撃すると体力が半分になり小数点以下は切り捨てられる。そして同じ体力のモンスターが1体増える。また体力が0になるとモンスターが消滅する。消滅する場合モンスターは増えない。これらは体力の計算、消滅の判定、モンスターの増加判定の順に処理される。このように読み替えることができることに気づきました。つまり、ひとまずモンスターの増加は考えずにモンスターの体力を0にすることを考えました。この場合、おおまかにHを2で何回割る必要があるかということです。D問題は計算時間を考える必要があるとのことですが、O(logN)ということになるはずで、計算時間は大丈夫っぽいということが分かります。

そして攻撃のたびに、つまり一度2で割るごとにモンスターが倍になっていくので、攻撃回数も1回、2回、4回、8回、16回－－－－と増えていきます。これをシンプルに足すことにしました。体力と攻撃回数はC問題同様、intでは扱えない可能性があるのでlong longとしました。

D

ここまでが私の解いたものになります。

Dを解けたのは初めてだったので嬉しかったです。

前述のとおり復習し次第E、Fも追記します。

<2020/1/28追記>

解説を見るとDは再帰関数、EはDPやナップザック、Fは貪欲法などと言う解き方になるとのことでした。再帰関数はAPG4で見たものなので実際に解いてみました。その他については@drkenさんの記事で解説されているようなので、そちらを解いた後に解いてみようと思います。

また、昨日は問題なく動いたVSCodeでしたが、今朝使ったところ標準ライブラリを読み込まなくなりました。インクルードパスを設定してくださいとメッセージが出て、あまりよくわからないまま、順番にそれらしいところを指定したりしてみたりしましたが、結局うまくいかず、アンインストールからインストールしなおしました。結局自力ではどうにもならなかったので、いったん諦めてしばらくはweb上のAtCoderコードテストを利用してコーディングすることにしました。スクショを張るかわりに私の提出結果をリンクしておくことにします。

D - Caracal vs Monster

APG4の再帰関数を読み直すと確かに典型的なのかな？という気がしました。

attack(n / 2) * 2 + 1

再帰関数をイメージするのはかなり難しいですが、ある一体のモンスターが体力1の時には1回攻撃すればそのモンスターは増えることなく消滅し(if文内、ベースケース)、2以上の時は半分の体力(n / 2)のモンスターが2体、元のモンスターが1体(+1)で計3回攻撃するということになります。

Submission #9794370 - AtCoder Beginner Contest 153