Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

2016年ドワンゴからの挑戦状 本選-A

atcoder.jp

概要

0からN(1 <= N <= 10^18)まで、xずつ加算したい。はじめ、xは1である。最小の加算回数は?ただし、次の★の操作は任意回行ってよい。

★ xをニコ数倍する。ニコ数とは、2 or 5からのみで構成されるかつ、同じ数字が隣り合わない数のことである。例えば、5, 25, 52, 2525, 52525252525など。

ACするまで

1. 10^18という制約は余りにも大きいため、一旦それなりに小さい数だと思って考える。
2. ニコ数という何の脈絡もない数が絡むNが作れるか系の問題は、直感的にDPであると気付く。
3. DPの遷移を考えてみる。xをa倍してちょうどNにならないときは、最初のx==1の時に何回か足したことにすればxをa倍してちょうどNにできる。実質余りを無視して、a倍などの関係を考察できる。
4. 漸化式が出来上がる。(これで部分点はとれる)
5. しかしこのままだとメモリが足りない(N <= 10^18なので)。つらい。mapをどう応用すれば・・・


6. メモ化再帰の性質を利用する。具体的には、メモ化再帰は必要になった場所しか計算されない!(つまりスカスカ配列にできる -> std::mapなどの連想配列)

考察

ACするまでにあるように、このようないくつが作れるか、もしくは何通りあるかの問題で、使うパーツに数学的な性質が特に見当たらない場合(例えば、XORをさせるとかも実は数学的な意味がないことがあったりする。)は、動的計画法で解かれることが多い。(この問題のように、すんなりと行かせてはくれないものも多いが)」

このことを念頭に、次のようなDPテーブルを定義する。
dp[i] := 0でx = 1の時から、xをいい感じにニコ数倍して、足したりして i を作るときに、かかる足し算の最低の手数。
これは「いくつが作れるか?」系の問題での典型的なDPテーブルの定義である。

ACするまでの3番のとおりに、ニコ数xを考える。 i % x == 0の時はiはニコ数xの数倍なので、xを事前でx倍しておけば、1回の加算で作れる。そして、xは純粋なニコ数のみならず、ニコ数同士の積でもよい。(演算としては、xをニコ数数個倍して加算することを意味してる)。
さて、i % x != 0のときはどうだろうか?実をいうと、これはx = 1の時にあらかじめ i % x だけ足せばよい(そして、x =1での操作なので、もちろんそれだけの加算回数もかかる)のである。例えば、i == 7, x == 5の時にx=1の時に2回加算されて、xを5倍してもう一回加算されたことにすればよい。最初は1ずつ数を足せるので、あらかじめ余りを足したことにすれば、実質的に i % x == 0 しか考えなくてよいとわかる。

また、iを作るときに、一番足す手数が多いのは x = 1 のままi回足すことであるので、これを念頭に踏まえて漸化式を考える。

dp[i] = min(i, dp[i / x] + (i % x)); (ただし、xはニコ数)

この式を0からNまでループを回して計算すれば部分点解法となる。

満点解法での上記の問題点は、ひとえに10^18までNを回す時間もメモリもないということである。ここで、更新式をよく見てみる。

dp[i] <- dp[i / x]

これは、i / x (を切り捨てたもの)を数回重ねて表せる数字しか、計算するときに参照されないとわかる。このように、DPテーブル更新式で実は参照する数が非常に少なく、スカスカな場合は、連想配列でDPテーブルを実装すればうまくいく。

ちなみにこの時、ニコ数自体は10^18以下ではたかだか40個未満であり、それらが積となってもたかだか10万以下である。(ソースは解説。非厳密だが、そう多くないと直感でもわかる。)よって、メモ化再帰すれば、必然的に必要になったか所しか計算されないので、実質的に計算量が減り、満点解法が得られる。

ACコード:
Submission #8540238 - 第2回 ドワンゴからの挑戦状 本選(オープンコンテスト)

一言

スカスカDPの新タイプ。