ABC 350 E — Toward 0

考察

サイコロで1が出ると、費用を払っても整数は変わらない。それでも次に同じ操作を選ぶ義務はなく、改めて二つの操作を比較できる。まず「一回操作し、その結果を見てから最適に続ける」費用の式を立てると、この自己ループを含めた最適化を整理できる。

入力の NN は最大 101810^{18} なので、全ての整数について順番に計算する配列DPは使えない。一方、確定操作の除数 AA は2以上で、サイコロも出目1を除けば整数を少なくとも半分にする。そこで、必要な状態だけを再帰的に求め、同じ整数に到達した計算を共有する方針を考える。

現在の整数を nn とし、そこから0にするまでに追加で払う金額の期待値の最小値を f(n)f(n) と定義する。既に払った金額は今後の選択を変えず、出目は過去と独立なので、履歴を状態に持つ必要はない。終端は f(0)=0f(0)=0 である。以降は n>0n>0 を考える。

確定操作を一回行い、その先で最適に行動する費用を DD と置く。

D=X+f(⌊nA⌋)D=X+f\left(\left\lfloor\frac{n}{A}\right\rfloor\right)

サイコロ操作では、まず YY 円を払い、出目を見てから次の操作を選ぶ。出目1なら同じ状態から最適に続けるので、その先の費用は f(n)f(n) である。自己ループ以外の部分を BB とまとめると、

B=Y+16∑b=26f(⌊nb⌋)B=Y+\frac{1}{6}\sum_{b=2}^{6}f\left(\left\lfloor\frac{n}{b}\right\rfloor\right)

となり、サイコロを一回選ぶ費用は B+f(n)/6B+f(n)/6 となる。操作を選ぶ時点ではまだ出目を知らないため、二操作の比較は確率平均の外側に置く。この一歩先の最適値を使う式をBellman最適方程式という。

f(n)=min⁡(D,B+f(n)6)f(n)=\min\left(D,B+\frac{f(n)}{6}\right)

右辺にも f(n)f(n) が残っているが、最小値をどちらが与えるかで場合分けすれば解ける。

  • 確定操作側が最小値を与えるなら f(n)=Df(n)=D である。この選択が式と整合する条件は D≤B+D/6D\leq B+D/6、すなわち D≤6B/5D\leq 6B/5 となる。
  • サイコロ側が最小値を与えるなら f(n)=B+f(n)/6f(n)=B+f(n)/6 である。移項すると f(n)=6B/5f(n)=6B/5 となり、この選択が式と整合する条件は 6B/5≤D6B/5\leq D となる。

等号のときはどちらを選んでも同じ値なので、まとめると次の漸化式を得る。

f(n)=min⁡(D,6B5)f(n)=\min\left(D,\frac{6B}{5}\right)

ここでサイコロ候補 E=6B/5E=6B/5 は、「状態が変わるまでサイコロを振り続け、変わった先では最適に選ぶ」方針の期待費用と解釈できる。出目1以外が出る確率は 5/65/6 なので、状態が変わるまでの期待試行回数は 6/56/5。最初の1以外の出目は2から6の五つが等確率になるため、

E=6Y5+15∑b=26f(⌊nb⌋)E=\frac{6Y}{5}+\frac{1}{5}\sum_{b=2}^{6}f\left(\left\lfloor\frac{n}{b}\right\rfloor\right)

である。これは最初から行動の選び直しを禁止した式ではなく、一歩式を解いて得た候補である。同じ状態に戻っても比較する二つの候補は変わらないので、状態が変わらない間は同じ最適行動を選び続けてよい。状態が変わった後は、その状態に応じて操作を選び直す。

公式入力例2の N=3,A=2,X=Y=20N=3,A=2,X=Y=20 で確かめよう。状態1では、どの2以上の除数でも0へ進むため、確定操作の費用は20、サイコロ候補は 6×20/5=246\times20/5=24。よって f(1)=20f(1)=20 である。状態3では、出目2・3が状態1へ、出目4・5・6が状態0へ進むので、

D=20+f(1)=40,E=6×205+2f(1)+3f(0)5=32\begin{aligned} D&=20+f(1)=40,\\ E&=\frac{6\times20}{5}+\frac{2f(1)+3f(0)}{5}=32 \end{aligned}

となり、f(3)=32f(3)=32 を得る。3ではサイコロを振り、1になったら確定操作へ切り替える。出目1で3に戻れば再びサイコロを選ぶ、という公式の方針とも一致する。

実装では f(0)=0f(0)=0 を先に返し、それ以外はメモに値があれば再利用する。未計算なら ⌊n/A⌋\lfloor n/A\rfloor と ⌊n/b⌋ (b=2,…,6)\lfloor n/b\rfloor\ (b=2,\ldots,6) の値を再帰で求め、DD と EE の小さい方をメモに保存する。自己ループを消したので、計算中の f(n)f(n) 自身を呼ぶことはない。答えは f(N)f(N) である。必要な状態数が少ない理由は計算量の節で示す。

典型の発動条件

期待値方程式のself-loop消去

同じ状態へ戻る確率があるときは、一回分の費用と、その後の期待費用を分けて式にする。行動も選べるなら、各行動の期待費用を比較する最適式を先に立てる。本問のように自己項以外が小さい状態だけで決まる場合は、場合分けと移項で再帰可能な式にできる。複数の状態を巡る循環には、この一状態の移項だけでは対処できない。

floor quotient memoization

巨大な整数から少数の整数除算だけで遷移するなら、実際に現れる切り捨て商をメモ化する。同じ商への到達経路を共有できるが、高速に解けると結論するには、除数の積の形などから相異なる状態数も評価する必要がある。

問題固有の要素

出目1だけが整数を変えず、他の出目では必ず小さくなる。このため、自己ループを取り除いた後は小さい状態からのDPになる。また、A≤6A\leq6 に注目すると、確定操作も含めた全ての除数の素因数が2・3・5に限られ、到達する商を三つの指数で数えられる。二操作を同じ少数の状態集合で扱えるのは、この除数の制約による。

正当性

現在の整数が同じなら、選べる操作も今後の出目の分布も同じであり、過去の履歴や支払額は将来の最小期待費用を変えない。したがって状態は現在の整数だけでよい。

f(0)=0f(0)=0 は正しい。小さい状態の最適値が求まっているとき、最初に確定操作を選ぶ場合とサイコロ操作を選ぶ場合で全ての選択肢を覆える。出目を見た後は到達した状態の最適値を使うので、一歩式 f(n)=min⁡(D,B+f(n)/6)f(n)=\min(D,B+f(n)/6) が成り立つ。考察の二場合の整理により、その解は一意に min⁡(D,6B/5)\min(D,6B/5) となる。

この値は実現できる。確定操作が最小ならそれを行い、サイコロ候補が最小なら状態が変わるまで振り直す。その後は小さい状態の最適な選択を使う。サイコロで状態が変わるまでの期待試行回数は 6/56/5 と有限で、状態が変わるたびに整数は少なくとも半分になるため、期待費用は有限である。一歩式が与える下界をこの方針が達成し、各状態の最小値が正しく求まる。自己ループ消去後の再帰先は全て小さいので、メモ化再帰は終端に達し、最終的に f(N)f(N) を返す。

実装上の注意

  • 状態とメモのキーには64 bit整数を使い、切り捨て商は整数除算で求める。NN を浮動小数点数に変換してから割ると、大きい整数の状態がずれる。
  • 費用の計算は double などの浮動小数点数で行う。例えば 6.0 * Y / 5.0 とし、整数除算による切り捨てと 6 * Y の32 bit整数でのオーバーフローを避ける。
  • 出目2から6の商が同じでも、その項は出目の個数分だけ足す。上の例の状態3では f(1)f(1) を二回加える。
  • n=0n=0 で操作を続けず、必ず0を返す。n=1n=1 では全ての再帰先が0となり、f(1)=min⁡(X,6Y/5)f(1)=\min(X,6Y/5) になる。
  • 絶対誤差または相対誤差 10−610^{-6} を満たせるよう、出力には十分な桁数を指定する。

復習の核

  • 行動を選ぶのは観測の前か後かを確認する。確率平均と最小値の順序は、その時点で知っている情報に合わせる。
  • 自己ループ先にも行動の選択肢があるなら、まず最適値自身を右辺に置く。「同じ操作を繰り返す」方針でよい理由は、その最適式から説明する。
  • 巨大な整数をメモ化するときは、遷移の深さに加えて、異なる経路から生じる状態の総数を数える。

計算量と制約

時間

相異なる到達状態数を、終端0も含めて SS とする。正の整数 a,ba,b による切り捨て除算には、

⌊⌊N/a⌋b⌋=⌊Nab⌋\left\lfloor\frac{\lfloor N/a\rfloor}{b}\right\rfloor =\left\lfloor\frac{N}{ab}\right\rfloor

が成り立つ。実際、N=abq+r (0≤r<ab)N=abq+r\ (0\leq r<ab) と書くと、左辺も右辺も qq になる。従って、どの到達状態も除数の積 mm を使った ⌊N/m⌋\lfloor N/m\rfloor と表せる。

除数は A,2,3,4,5,6A,2,3,4,5,6 で、2≤A≤62\leq A\leq6 より素因数は2・3・5だけである。よって m=2p3q5r (p,q,r≥0)m=2^p3^q5^r\ (p,q,r\geq0) と書ける。正の状態では m≤Nm\leq N なので、

p≤⌊log⁡2N⌋,q≤⌊log⁡3N⌋,r≤⌊log⁡5N⌋p\leq\lfloor\log_2N\rfloor,\quad q\leq\lfloor\log_3N\rfloor,\quad r\leq\lfloor\log_5N\rfloor

となる。指数の三つ組は高々 O((1+log⁡N)3)O((1+\log N)^3) 個であり、異なる三つ組が同じ商になればメモでは一つに共有される。m>Nm>N の場合も全て状態0にまとまるため、S=O((1+log⁡N)3)S=O((1+\log N)^3) である。

一状態につき確定操作一つとサイコロの五つの遷移を調べる。ハッシュ表の検索・追加を平均 O(1)O(1) とすると、全体の期待時間計算量は O(S)=O((1+log⁡N)3)O(S)=O((1+\log N)^3)。N≥2N\geq2 では通常の表記で O((log⁡N)3)O((\log N)^3) となる。

空間

メモに O(S)O(S) の領域を使う。自己ループ消去後の再帰先は高々 ⌊n/2⌋\lfloor n/2\rfloor なので、再帰の深さは O(1+log⁡N)O(1+\log N)。合計の空間計算量は O(S+1+log⁡N)=O((1+log⁡N)3)O(S+1+\log N)=O((1+\log N)^3) となる。

制約との対応

公式制約は 1≤N≤10181\leq N\leq10^{18}、2≤A≤62\leq A\leq6、1≤X,Y≤1091\leq X,Y\leq10^9 で、入力は全て整数。実行時間制限は2秒、メモリ制限は1024 MiBである。

N≤1018N\leq10^{18} では p≤59,q≤37,r≤25p\leq59,q\leq37,r\leq25 なので、正の状態数は粗い上界でも 60×38×26=59,28060\times38\times26=59{,}280 個に収まる。終端を含む再帰の深さも高々61であり、全整数を配列で持たず、到達した商だけをメモに記録する方法が使える。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Toward 0 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 確率過程・期待値DP

主題
  • 確率過程・期待値DP: 意思決定時点で観測済みの情報を状態にし、行動の最適化と確率平均を正しい順序で組み合わせたBellman式を解ける。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 確率・期待値DP

    補助タグ: DPの最小十分状態

    執筆: abc-explanation-author1.1.1 / revision 3

    学習の位置

    体系上の位置: 確率過程・期待値DP

    • 意思決定時点で観測済みの情報を状態にし、行動の最適化と確率平均を正しい順序で組み合わせたBellman式を解ける。

    先に読む単元:

    この解説で扱わないこと:

    • 二人零和ゲームの勝敗・Grundy数。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題