コンテストページ
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 問題で見ました。私は天才なので当然、これくらいは知っています。これは、切り上げ除算です。みなさん、わかりましたか? 切り上げ除算です。
おや、なにかみえましたか? 気のせいですね。
敵を座標でソートして左から順に見ていきましょう。最適解は、最も左の敵をなるべく右に爆弾を置いて倒すです。その敵の座標を x とすると、被害の範囲は等号付きで x + 2D + 1 までですから、C++ であれば upper_bound( ..., x + 2 * D + 1) でよいです。(ところで C# に LowerBound / UpperBound がなくて泣いたのですが……)(尺取りでもよいです。)
さて、被害範囲がわかったので、実際に被害を与えましょう。すぐに思いつく方法は、長さ N の配列を用意して、そこにダメージを記録しておくことです。そうすると、必要な分だけ攻撃すればよいです。しかしご存知のように、これではとても間に合いませんから、遅延評価で高速化をしましょう。
そこで、ダメージではなく、ダメージの隣接差を持ちましょう。すると更新は 2 箇所、+1 / -1 でよいです。ただしこうすると取得が不可能になるのですが、左から順に見ていますから、現在の累積和を別に管理すればよいです。これで AC ができます。(ところで実は +1 の更新はしなくても良いということもわかります。)
二分探索と尺取り法について
あきらかに尺取り法の方が楽です。こちらをお使いください!(泣)(C# に LowerBound / UpperBound がないからという事情もありますが。)
ツイッターのご様子
A について
すごいです すごい pic.twitter.com/Bv7vxC3Viq
— ぽかーん懐古DP@259家(桃音モモ) (@259_Momone) January 26, 2020
コンパイラ屋さんさん!?
やっぱりこういうところを見るとC#の最適化力ってそこまでなんだなあってなる(というかC++がガチ過ぎる) pic.twitter.com/HloYyeS0CW
— keymoon (@kymn_) January 26, 2020
これは悲しいお知らせです。
D について
これです。D、けっこう難しかったと思うのですが、みなさん強いです。 https://t.co/nuR8gQDZC2
— ながたかな (@ngtkana) January 26, 2020
とのことです。(実況放棄)
E について
Eは2べき倍した魔法を用意してナップサックした(気付いたとき嬉しかったけど他の方法がたくさんありそう)。Fは始点をモンスターの位置にして左から貪欲でいいけど、実装で頭が混乱した。
— deu (@charmychachacha) January 26, 2020
これは個数制限付きナップザックのアルゴリズムなのですが、自力でたどり着けるなんて強いです。(ちなみに順位表お隣さんです。)
E †比較関数全探索† pic.twitter.com/P9AS3IyvUN
— 神崎 (@knzk_ate) January 26, 2020
これ好きです。
F について
> 敵を座標でソートして右から順に見ていきましょう。
— ぽかーん懐古DP@259家(桃音モモ) (@259_Momone) January 26, 2020
誤字を指摘していただきました。
実は https://t.co/IyI1jChvhB これが指摘しているのは誤字ではありませんでした
— ぽかーん懐古DP@259家(桃音モモ) (@259_Momone) January 26, 2020
いえ、自分のアルゴリズムを線形だと思っている異常者を諌めるリプライでした。
問題F、A=1としてよい、気づかなかった勢です ^^;
— maspy (@maspy_stars) January 26, 2020
maspy さんがこういううっかりをしていると、萌えてしまします。(A = 1 をして、切り上げ除算が出来なったのは私です(泣))
X_iのdistinct制約は座圧向けでしょうか バリアフリーですね
— ぽかーん懐古DP@259家(桃音モモ) (@259_Momone) January 26, 2020
なるほどです(!?)
その他
文系ギャルが0から始める競技プログラミング 第一部
— マリー (@CBOX360) January 26, 2020
ー完ー pic.twitter.com/xzGmXttWQg
みんな大好きマリーさんです。5 完緑パフォで茶色昇格です。嬉しいですね。
— 競技プログラミングをするフレンズ (@kyopro_friends) January 26, 2020
writer さんです。1000 人に通されるのは想定外だったようです。実際私もびっくりしています。
一般には通されすぎてびっくりする回とその逆があるのですが、最近は前者なことが多いです。みなさん強いです。
すっごーい、参加人数が過去最大だよ!
— maspy (@maspy_stars) January 26, 2020
可愛らしいですね。
結果
98:00 全完 905 位 1437 水色パフォです。切り上げ除算さん……
E までが遅いのは、特に詰まったわけではありませんから、実験的な環境でコーディングしているからというのが強そうです。いまは、C# + Vim(カスタマイズほぼなし)ですから、コンパイルを通すのにかなり苦戦をしてしまします。