読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2305 Beautiful Currency

AOJ

Beautifulのスペルが覚えられないのは私だけじゃないはず.

問題文

Beautiful Currency | Aizu Online Judge

訳は載せませんが,美しい通貨群にするために必要な各々の変動レートの"最大値"を求める問題です.
総和と勘違いしてサンプルが合わず丸一日悩みました.

解法

N \le 20なのでbitDP...と思ってしまいそうですがそんなことはありません.
元の通貨の最大値をMとします.
冷静になると(ならなくても)以下の三つのことが分かります.

  • 各通貨について,変更後の通貨の値は2M以下でいいことが分かります.(2Mにするより1に変えたほうが結果が良くなるため)
  • 通貨の大小の順序を変える必要はない(同じ値になることはある)
  • i番目の変更後の通貨の値b_iは,i-1番目の通貨の値b_i-1の倍数であればよい.(再帰的にj < i-1番目の通貨の倍数になるため)

以上のことから,
dp(i,m):=i番目の通貨の値をmにしたときの変動レートの最大値の最小値
と定義できます.
この値について,貰うDPで値を求めていくとO(NM\sqrt(M))で間に合わなさそうな気がしますが,
配るDPにすると実はO(NMlogM)となり間に合います.
logになる理由はこの問題の解説を見るといいと思います.
No.390 最長の数列 - yukicoder