AtCoder Regular Contest 084
Updated:
Source codes
Solutions
C - Snuke Festival
imos 法を 2 回やった。計算量は $O(N)$ である。
ポイント
set と lower_bound を使う方法が想定解だろうと思ったら案の定そうだった。
D - Small Multiple
私がどこまでできて、どこから先ができなくて、どうすればよかったか、という順番で書く。
私ができたこと
まず $100 \dots 000$ を足すコストが 1 であること、ルール上はこれを 9 回まで足していいが、実際は 10 回以上足すつもりで動かして問題ないこと、なんとなくダイクストラ法だろうということ。これらはわかっていた。また、頂点は $\mathrm{mod} K$ で $0$ を目指すのもわかっていた。
私ができなかったこと
辺の数が多すぎる。つまり、 $\{ 10^s \in \mathbb{N} \mid s = 0, 1, \dots \}$ は無限集合であるから、ダイクストラ法で辺が張れない。しかしサンプルを見るとコスト 36 の例が出ている。遷移が複数回必要である。
どうすればよかったか
「$100 \dots 000$ を足す」という操作でなくて、次の $2$ つに分解すればよかった。
- 「$1$ を足す」…コスト 1
- 「$10$ 倍する」…コスト 0
この方法だとグラフを作る必要もない。全ての頂点でこの 2 つの辺しか出ていないからである。 よって計算量は $O(K \log K)$ である。
ポイント
グラフがある。辺が多くある時にどうするか？ という問題は印象に残っている。この問題は、 辺をより基本的な辺の組み合わせに分解することで、却って辺が減る というものであった。
次の 2 つの問題が記憶にある。
CODE FESTIVAL 2016 Final / G - Zigzag MST
グラフを組み替え、無限本の辺を重ね合わせて、コストが一番小さい辺だけ残して有限個にする。 具体的には最小全域木のクラスカル法を後から使うことを考慮し、同値なグラフを作る。 円周上に辺が無限個、他は有限個になるようにする。
Xmas Contest 2015 / B - Broken Christmas Tree
完全グラフから使えない辺を除かれたグラフが与えられる。使えない辺を set で持っておき、辺を使っていいかどうかを set に問い合わせ、 DFS 木を作る。
E - Finite Encyclopedia of Integer Sequences
ポイント
F - XorShift
ポイント
Others
D は解きたかった。もう少しで届きそう。
コンテストに参加する人間の年齢層は、だいたい アイドルマスター SideM の年齢層に似ていると思う。私は現在 28 歳なので、 S.E.M みたいなものか。主要なコンテスタントから見れば後期高齢者みたいなものである。
しかし「どんなに歳を取っても遅すぎるってことはないんですね〜」と山下がこの日放送のエムマス 5 話で言っていた。私もそんな気持ちなのよね、 AtCoder をやるのは。