SRM 548 DIV2 Hard: KingdomAndPassword

解法

oldPasswordが新しいパスワードにもなる場合がコーナーケース。

そうでない場合を考える。

先頭からi桁が等しいとする。つまり、新しいパスワードがoldPasswordと異なる最上位の桁をi(0-indexed)とする。この桁の値によって新しいパスワードがoldPasswordより大きいか小さいかが確定する。

(1)新しいパスワードのほうが大きい場合

dp[mask] = 使用した値がmaskであるときの新しいパスの最小値

(2)新しいパスワードのほうが小さい場合

dp[mask] = 使用した値がmaskであるときの新しいパスの最大値

の2種類のDPを解けば答えが求まる。

iは総当たりで固定。各iについてビットDPするので全体で

O(2^n＊n^2)

ミス

1<=oldPassword<=10^16-1

なのでoldPasswordは最大16桁ある。

配列を1<<15のサイズしか確保してなかった。