AtCoder Regular Contest 084

更新日時:

AtCoder Regular Contest 084

ソースコード

解法のメモ

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

ポイント

その他

D は解きたかった。もう少しで届きそう。

コンテストに参加する人間の年齢層は、だいたい アイドルマスター SideM の年齢層に似ていると思う。私は現在 28 歳なので、 S.E.M みたいなものか。主要なコンテスタントから見れば後期高齢者みたいなものである。

しかし「どんなに歳を取っても遅すぎるってことはないんですね〜」と山下がこの日放送のエムマス 5 話で言っていた。私もそんな気持ちなのよね、 AtCoder をやるのは。

コメントする