94. AtCoder参加記録（AtCoder Beginner Contest 246）

現状です。12回参加でレート 1012 です（14回参加するまでレート補正期間中）。

今回はパフォーマンス 1424 で、過去最高でした。

ABCEを通して、DFGExは未解答です。Eで1ペナです。

各問題の感想です。

A

Aにしてはちょっと難しいです。

色々やり方はあると思いますが、Dictionary を使って x, y 座標それぞれ数値 → 登場回数を保持して、1回しか登場していないものを出力しました。

B

として 。

C

どの商品も割引金額が基本同じなので、適当にクーポンを割り当てればよいです。

ただし、 円より小さいものは使うと損になるので、まずは 円以上のものをクーポンで割り引いていきます。この計算は、除算を使って定数時間で行うことで になります。

これでクーポンが余った場合、残った値段の高い順に並べ替えて、順番に1枚ずつ使っていきます。

全体としては です。

D

因数分解できる、けどここからどうすれば…？と悩んでいました。10分ほど考えて方針が立たないので、いったん E 問題に切り替えました。

E を解いてから戻ってきましたが、 の探索から逆算するのが良いのだろうな…と思いつつ、どのように探索すればよいか浮かばず、そのまま諦め。

になることは頭では分かっていたのですが、なぜかそこから二分探索へ発想が至りませんでした。うーん。

E

BFS しか方針が立たず、間に合うのか怪しかったので45度回転など色々考えましたが、イマイチだと思い愚直に書きました。 の偶奇が異なると到達不可能、という例外だけ書いて、後は普通に BFS です。制限時間が長いので行けるか…？とやってみると普通に通り、拍子抜けでした。

なお、1WA は凡ミスで、ここで TLE が出なかったのでそのまま通してみた感じでした。

（追記）

昨日のE、01-BFSとか知らないけど普通にBFSして通ったの何でだろ、と思ってたけど、よく考えたら状態数 O(N^2) だからそりゃ通るわ

— イバコ (@ibako_piyo) 2022年4月3日

F, G, Ex

見てないです。

今日もあんまり体調が良くなかったのですが、ベストエフォートだったと思います。E を通せたのでパフォーマンス的には十分よいですが、D 通せなかったのは大きな反省点です。