Dial Lock Key (hard)

2 secs 1024 MB
programgmg2's icon programgmg2
Tweet
問題
提出
テストケース
解説

解説

ダイヤルの動かし方をこのまま考えようとしても大変なので、まずは SS の数値を工夫してみます。簡単のため、一旦 +1+1 の操作のみに着目し、00と99の繋がりを排除して考えます。

ここで例えば、S=1234S = 1234のとき、左側の桁からの数字の増分をとった数列(左側から11桁目の部分は00からの増分)を考えると、 S′=(+1,+1,+1,+1)S' = (+1,+1,+1,+1) となります。この数値の意味を考えてみましょう。すると、si′>0s'_i > 0 のとき Si′=si′S'_i = s'_i ということは、000..000000..000 の左側から ii 番目の桁から一番右の桁までに対して +1+1 するという操作を si′s'_i 回 行った、と言い換えることができます。

次に、S=4321S = 4321のときを考えてみます。左側の桁から数字の増分をとった数列を考えると、 S′=(+4,−1,−1,−1)S' = (+4,-1,-1,-1) となります。si′<0s'_i < 0 のときも先程と同様に、00000000 の左側から ii 番目の桁から一番右の桁までに対して −1-1 するという操作を ∣si′∣|s'_i| 回 行った、と言い換えることができます。

ここで、例として左側から44桁目の部分に着目してみます。左側から44桁目の部分は、i=1i=1のときの操作で44回 +1+1 された後、i=2,3,4i=2,3,4のときの操作で33回 −1-1 されていますが、これはi=1i=1のときの操作で11回 +1+1 されただけであるとみなすことができます。同様に、左側から2,32,3桁目の部分もi=1i=1のときの操作でそれぞれ3,23,2回 +1+1 されただけであるとみなすことができます。

これらの考えは、imos法のような考え方で次のようにまとめられます。

  • +1+1 の操作のみで kk回操作が行われて000..000000..000 から SSとなるとき、i(1≤i≤k)i(1 \leq i \leq k)番目の操作で lil_i番目からri−1r_i-1番目までの桁が +1+1 されるならば、それぞれのiiについて sli′s'_{l_i} は +1+1 , sri′s'_{r_i} は −1-1 される。(ただしri=N+1r_i = N+1 ならば −1-1 は無視される。)

この考え方より、+1+1 の操作回数はNN個の00の数列(0,0,...,0)(0,0,...,0)に対してl,r(1≤l<r≤N+1)l,r(1 \leq l < r \leq N+1)番目の要素にそれぞれ +1+1 , −1-1 する操作をしてS′S'にするための最小の操作回数を求めれば良いと分かります。これは左側の要素から ll として貪欲に操作を行えば求めることができます。<br> 例えば、S=4321S = 4321のときは (0,0,0,0)→(1,−1,0,0)→(2,−1,−1,0)→(3,−1,−1,−1)→(4,−1,−1,−1)(0,0,0,0) \rightarrow (1,-1,0,0) \rightarrow (2,-1,-1,0) \rightarrow (3,-1,-1,-1) \rightarrow (4,-1,-1,-1)と操作を行えばよいです。

−1-1 の操作についても、00と99の繋がりを考慮したとしても、左側の桁からの数字の増分(-1の操作のときときは減分)をとって同様に考えればよいです。これらの操作が混在しているパターンもあります。例として、S=9191S = 9191のときを考えてみましょう。左側の桁からの数字の増分をとった数列(左側から11桁目の部分は00からの増分)を考えると、 S′=(−1,+2,−2,+2)S' = (-1,+2,-2,+2)となります。このような場合も、<br> (0,0,0,0)→(−1,+1,0,0)→(−1,+2,−1,0)→(−1,+2,−2,+1)→(−1,+2,−2,+2)(0,0,0,0) \rightarrow (-1,+1,0,0) \rightarrow (-1,+2,-1,0) \rightarrow (-1,+2,-2,+1) \rightarrow (-1,+2,-2,+2)といったように左側の要素から ll として貪欲に操作を行えば求めることができます。

さて、解法まであと一歩です。ここまで、左側の桁からの数字の増分をとった数列 S′S' を例示のために分かりやすいよう定めていました。 しかし、実は S′S' は無数に考えられます。例えば、S=123S = 123のとき、S′S' は (+1,+1,+1)(+1,+1,+1)の他に(+1,+1,−9),(+1,−9,+1),(+1,−9,−9)(+1,+1,-9),(+1,-9,+1),(+1,-9,-9)などが考えられます。これは、00と99が繋がっているので、ダイヤルが一周(1010回の操作)することでもともとの位置に戻ってくるからです。 ではどうすればいいのでしょうか？ここでは、各iiについて、 −9≤si′≤9-9 \leq s'_i \leq 9 となるような si′s'_i を全探索すればよいです。∣si′∣>9|s'_i| > 9 となる場合、ダイヤルが一周(1010回の操作)していることになり、余分な操作をしていることになるからです。ここで、−9≤si′≤9-9 \leq s'_i \leq 9 となるような si′s'_i は各iiについて (si−si−1)%10,−(si−1−si)%10(s_i-s_{i-1})\% 10,-(s_{i-1}-s_i)\% 10の2通りが考えられるため、これらの組み合わせを全探索することになります。時間計算量は全探索の部分がO(2N)O(2^N)、各S′S'における最小の操作回数を求める部分が適切に実装できてO(N)O(N)となり、全体でO(2N×N)O(2^N \times N)となるので、今回の制約においては実行時間制限に間に合います。よって、この問題を解くことができました。