CF Good Bye 2017 G: New Year and Original Order

http://codeforces.com/contest/908/problem/G

解法

上の桁から決めていく桁 DP により解くことができる。ソート済み整数はレピュニット数*1 の和で表せるという性質が役に立つ。たとえば 1122244 という整数の場合

1122244
1111111
  11111
     11
     11

という表現が可能である。$\underbrace{1\dots1}_n=(10^{n+1}-1)/9$ と表せるため、以下の表現も可能である。

$$1122244\times 9 + 9 = 10^8 + 10^6 + 10^3 + 10^3 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0$$

1122244 の次に 2 を使うとしよう。このとき次のような変化を見せる。

\begin{align}
1122244\times 9 + 9 &= \underline{10^8 + 10^6} + 10^3 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0 \\
11222244\times 9 + 9 &= \underline{10^9 + 10^7} + 10^3 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0
\end{align}

つまり 1 と 2 に対応するレピュニット数が 10 倍されて、それ以外はそのままになっている。ここまでわかると、1,2,3,...,9 に対応するレピュニット数の総和は独立に数え上げられることが分かる。よって、次のようなDPが可能となる。

\begin{align}
1122244\times 9 + 9 &= \underbrace{10^8}_{dp[i][less][1]} + \underbrace{10^6}_{dp[i][less][2]} + \underbrace{10^3}_{dp[i][less][3]} + 10^0 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0 \\
11222244\times 9 + 9 &= \underbrace{10^9}_{dp[i+1][less][1]} + \underbrace{10^7}_{dp[i+1][less][2]} + \underbrace{10^3}_{dp[i+1][less][3]} + 10^0 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0
\end{align}

\begin{align}
dp[i+1][j'][k] \gets \begin{cases}
10\times dp[i][j][k] & \text{$d \le k$} \\
dp[i][j][k] & \text{otherwise}
\end{cases}
\end{align}

ここで $d$ は遷移時に選んだ数字である。

Submission #33803662 - Codeforces

感想

アプローチの掛け方が少ないから少し考えれば解けるような問題だった。
レピュニット数は AtCoder でも最近見たしね。Eの方が圧倒的に難しい。