ブログ名

競技プログラミングやお歌のお話をする高菜です。

ABC 153 解法

コンテストページ

AtCoder Beginner Contest 153 - AtCoder

✔A - Serval vs Monster

みなさんご存知ですか? こういうものはですね、切り上げ除算で対処することが出来ます。典型ですね。私は黄色コーダーです。こんなものを間違える余地があるでしょうか。ありませんね。この問題は 3 分ノーペナルティーで通しました。いやぁ、天才ですね。切り上げ除算のプロです。

✔B - Common Raccoon vs Monster

必殺技のダメージの合計値と敵の体力を比較です。

✔C - Fennec vs Monster

強い K 体を必殺技で倒せばよいです。答えは残っているものの体力の合計です。

✔D - Caracal vs Monster

これは面白いです。答えは、2 で割って切り捨てをするの出来る回数だけで決まります。この回数を N とおくと、答えは 1 + 2 + 4 + ... + 2N です。(ところで体力が 2 以上あるときの攻撃の効果を、「体力を 1 削る」にすると、これも面白そうです。)

✔E - Crested Ibis vs Monster

特定の量のダメージを与えるのに必要な最小の魔力を、ナップザック DP で求めましょう。

✔F - Silver Fox vs Monster

まず、敵の体力をすべて A で割っておくことにより、A = 1 としてよいです。 これは進研ゼミでやった典型ですね。A 問題で見ました。私は天才なので当然、これくらいは知っています。これは、切り上げ除算です。みなさん、わかりましたか? 切り上げ除算です。

f:id:ngtkana:20200126231756p:plain

おや、なにかみえましたか? 気のせいですね。

敵を座標でソートして左から順に見ていきましょう。最適解は、最も左の敵をなるべく右に爆弾を置いて倒すです。その敵の座標を x とすると、被害の範囲は等号付きで x + 2D + 1 までですから、C++ であれば upper_bound( ..., x + 2 * D + 1) でよいです。(ところで C# に LowerBound / UpperBound がなくて泣いたのですが……)(尺取りでもよいです。)

さて、被害範囲がわかったので、実際に被害を与えましょう。すぐに思いつく方法は、長さ N の配列を用意して、そこにダメージを記録しておくことです。そうすると、必要な分だけ攻撃すればよいです。しかしご存知のように、これではとても間に合いませんから、遅延評価で高速化をしましょう。

そこで、ダメージではなく、ダメージの隣接差を持ちましょう。すると更新は 2 箇所、+1 / -1 でよいです。ただしこうすると取得が不可能になるのですが、左から順に見ていますから、現在の累積和を別に管理すればよいです。これで AC ができます。(ところで実は +1 の更新はしなくても良いということもわかります。)

二分探索と尺取り法について

f:id:ngtkana:20200126234549p:plain

あきらかに尺取り法の方が楽です。こちらをお使いください!(泣)(C# に LowerBound / UpperBound がないからという事情もありますが。)

ツイッターのご様子

A について

コンパイラ屋さんさん!?

これは悲しいお知らせです。

D について

とのことです。(実況放棄)

E について

これは個数制限付きナップザックのアルゴリズムなのですが、自力でたどり着けるなんて強いです。(ちなみに順位表お隣さんです。)

これ好きです。

F について

誤字を指摘していただきました。

いえ、自分のアルゴリズムを線形だと思っている異常者を諌めるリプライでした。

maspy さんがこういううっかりをしていると、萌えてしまします。(A = 1 をして、切り上げ除算が出来なったのは私です(泣))

なるほどです(!?)

その他

みんな大好きマリーさんです。5 完緑パフォで茶色昇格です。嬉しいですね。

writer さんです。1000 人に通されるのは想定外だったようです。実際私もびっくりしています。

一般には通されすぎてびっくりする回とその逆があるのですが、最近は前者なことが多いです。みなさん強いです。

可愛らしいですね。

結果

f:id:ngtkana:20200126231243p:plain

98:00 全完 905 位 1437 水色パフォです。切り上げ除算さん……

E までが遅いのは、特に詰まったわけではありませんから、実験的な環境でコーディングしているからというのが強そうです。いまは、C# + Vim(カスタマイズほぼなし)ですから、コンパイルを通すのにかなり苦戦をしてしまします。