ABC182 感想

ABC182に出場しました。
全完+2ペナ(59:20)、順位は56位でした。
途中ネット接続が切れてしまい、Dの一度目の提出前に10分ほど離脱してしまいました。
ABCなので、そのあとは落ち着いてのぞめましたが、ARC,AGCなら発狂しているところでした。
今後は、万が一そういうことがあっても、残りの問題の考察ができるよう、試験が始まったら問題を全部開くようにしたいと思います。

atcoder.jp

A問題

書かれている内容を理解して整理するのに時間がかかるタイプの問題です。
しかしながら、実は制約を見るだけで答えがエスパー出来ます(ペナを出すと5分失うので、あまりお勧めできる方法ではありません)。

0:46でAC

B問題

B問題なので、あまり何も考えず全探索です。この問題は、制約が大きい場合でも解くことができそうです。

3:29でAC

C問題

前回は8の倍数判定ですが、今回は3の倍数判定です。各位の和が3の倍数になるようなもののうち、もっとも長さの長いものをbit全探索で求めます。
この問題も、制約が大きい場合を考えると面白そうです。
最後の詰めでミスをおかし、1ペナです。

8:22でAC

D問題

(累累積和)+(累積和のmax)の最大値を計算します。
N=1の場合に誤った出力をしてしまい、1ペナです(たぶん実装方針が悪かったです)。

28:32でAC(途中ネット接続が切れていました)

E問題

各電球が照らす領域を全探索します。
普通に探索すると、O((H+W)HW)になってTLEします。
そこで、途中で探索を打ち切ることを考えます。
別の電球に到達したら探索を打ち切ることによって、各マスにつき高々4方向しか探索されないので、O(HW)になって間に合います。

類題でございます。
atcoder.jp

35:37でAC

F問題

各硬貨は、「店員⇒ルンルン」「ルンルン⇒店員」「移動なし」の3通りです。
これを小さいものから順番にDPで数え上げていけばよいです。
(小さい順にDPするのは、実際にお金を払うときのことを思い出せば察しが付くと思います)
はじめ「借金X円」の状態から、iを増やしていくとルンルンの借金が変化していくわけですが、i番目までみたとき「借金[X/A_i]円」「借金[X/A_i]+A_i円」の二通りしかないことがわかるので、状態をまとめることができO(N)でとけます。
N<=50なのにO(N)で解けて変な気持ちになりますが、これはA_iのオーバーフローを避けるためなので、実はあまり気にしなくてOKです。

類題でございます(最適化か数え上げかの違いだけで、同じ解法です。)
atcoder.jp

49:20秒でAC

まとめ

おもしろかったです！！！