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

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

AGC - 044 - A - Pay to Win

atcoder.jp

概要

最初にx=0という数字を持っている。あなたは、次の操作のうち任意のものを任意の順番で、任意の回数回だけ行える。

  • (操作1)xを2xで置き換える。
  • (操作2)xを3xで置き換える。
  • (操作3)xを5xで置き換える。
  • (操作4)xを+1もしくは-1する。

操作1~4をするには、それぞれ1回あたりコストA, B, C, D円かかる。
あなたは最終的にx=Nにしたい。それに必要なコストの合計の最小値を求めよ。

制約: 1 <= N <= 10^18, 1 <= A, B, C, D <= 10^9


ACするまで

1. 動的計画法が想定解っぽそう。
2. 前から単純にDPをするとできるけど、O(N)かかる。倍々していくので、実操作回数はそう多いはずがないけど。
3. 実は、Nの状態から減らしていくことを考えると、証明から実は限られた個数にしか毎回アクセスしない!
4. 実装に手間取る(<-wwwww)


5. 用心深くコピペやモジュール化を進めて、書き直してAC

考察

まず、2, 3, 5倍するにあたって、「+1を繰り返す」 or 「操作1~3を利用する」の2通りがあって、元のx次第でどちらが小さいのかが分からないため、p倍するのならば、

  • +1を繰り返すで、(p - 1) * D円
  • 操作1~3を利用するで、A or B or C円

になり、そのうちの小さい方を取ればよい。

この問題は、Nの大きさが10^5程度ならば、典型的なグラフの最短経路の問題である。
dp[i] := iを作るまでにかかる最低コスト
として、すべてINFで初期化して、dp[0]=0とする。今頂点iにいるとして、次の場所へと遷移する。
dp[i * 2] にdp[i] + min(A, i * D)
dp[i * 3] にdp[i] + min(B, i * D * 2)
dp[i * 5] にdp[i] + min(C, i * D * 4)
dp[i - 1] にdp[i] + D
dp[i +1] にdp[i] + D
で網羅できる。(遷移時のコストは上で述べた2通りのうちの小さい方を取るようにする)

さて、このアルゴリズムから無駄を落としていこう。
まず、直感的にわかるのが、1からNまでのすべての数字について、細かく最小遷移コストを計算する必要がない、ということ。イメージとしては、後半になってくるとp倍などでかなり多くの数字を飛ばすことになり、その間の数字は直感的にはあまり答えには寄与しない。

そして、この直感をより具体的なものにしてみる。
[1, N]のうち、例えば[N/2+1,N-1]までは直感的に細かく計算しなくてもよさそう
↓ ↓ ↓
Nから逆算した時、どうなるだろうか?

と、このように疑問が浮かぶ。
例えば、Nから逆算するのを考える。まず、2倍、3倍、5倍、はたまた+1 or -1をしてNになったのかはわからない。しかし、+1 or -1と倍数は根本的に2つの扱いをしよう(どこから来たのか?というのを考えるにあたっては根本的に遷移元が違うため)。直前で何かしらのp倍の倍率がかかったとすると、Nがpの倍数でなければ、+1 or -1で調整した、ということになる。
そして、直前の倍率はが2 or 3 or 5のどれかはわからない。なので、全部試してみてはどうだろうか?
でも、具体的な遷移の式に移る前に、考えておかないといけないことがまだある。

+1 or -1の調整について、Nが3の倍数から来たとして、Nから(N % 3)を引いてそれを3で割ることになる。ここで、引くのは(N % 3) + 3 * 1, (N % 3) + 3 * 2...などではだめなのか?
数学的に示そう。
Nについて、(N % p) + p * k回だけ-1をしてから、pで割ることを考える。 (kは自然数)
この時、最終的にこれは(整数同士の割り算が切り捨てされる前提として)、(N / p - k) -> Nの遷移の逆算をしたことになる。この時、かかってるコストは、cost_for_P + ( (N % p) + p * k) * D となる。
しかし、Nから(N % p)を引き、pで割ったのちに、kだけ引くことで同じように、(N / p - k) -> Nの遷移ルートが存在する。このルートによるコストは、cost_for_P + ( (N % p) + k) * Dであり、先ほどのよりもより低い。
よって、kは常に0であるほうが、一番低いコストで結果的には遷移できる。

同様に、Nに(N - (N % p))を足して、pで割るという逆算の作業も余計なものを足さないのが最適であるともわかる。

具体的な遷移に関しては、p倍していくらか足してNになった or p倍していくらか減らしてNになった or (そもそもNがpの倍数なら割るだけ)、それぞれ答えに寄与しうるので全部探索する必要がある。

これで、直前の倍率が分かったときの遷移については、問題なく解決した。

あとは、計算量分析である。この逆算という操作は体感アクセスすべき要素は少ないが、実際はどうだろうか。
解説PDFにもあるように、おおざっぱに計算量を抑えてみる。Nにするのに2倍をa回、3倍をb回、5倍をc回したとする。N <= 10^18の制約により、a <= 60 , b <= 40, c <= 30がそれぞれの指数の限界である(これは対数を取ってみるとわかる)。 2^a3^b5^c <= Nとして、左辺の約数はたかだか、2 * 61 * 41 * 31 = 155062通りである(この2はNに最後プラスの微調整かマイナスの微調整かの違い)。よって、Nから逆算するときに、アクセスする数の上限もたかだかその程度である。

計算量、ヨシ!w

しかし、最後で処理しなければならないことがある。オーバーフローである。

遷移を考えるときに、5倍していくらか足してNになったとすれば、遷移にかかるコストの式はmin(C, (N / 5) * 4 * D)となるが、(N / 5) * 4 * Dは最悪10^18 * 10^9なので、余裕でオーバーフローする。

解決法としては、あまりにも(N / 5) * 4が大きいのならば、Dと掛けない、という古典的なif文による場合分けがいいだろう。
実装例としては、

  • 10^18 / Dよりも(N / 5) * 4が大きいのなら、(N / 5) * 4 * Dを10^18のようなオーバーフローしない程度の大きな数として扱う。
  • 掛算でオーバーフローが起きてるので、cmathのlog10機能を使って、桁数を計算してlog10(N / 5 * 4) + log10(D) <= 18などで押さえる。

などの方法がある。いずれも条件式に三項演算子で直接埋め込むと可読性が死ぬので、関数化しよう!(1敗)

あとは、丁寧にコピペをして、コードを細心に修正していくだけである。

ACソースコード

Submission #13588273 - AtCoder Grand Contest 044

一言

寸暇ができたのでブログ進捗。悔しいと解説を詳しく書きがち