yukicoder No. 915 解説

yukicoder_915.txt

yukicoder No. 915 解説

・問題文
No.915 Plus Or Multiple Operation - yukicoder
https://yukicoder.me/problems/no/915


以下のような問題が解ければよい。

初期値 0 の変数 x に対し、以下の２種類の操作が可能である。
  [+i]: x += i, i∈[0, C)
  [*C]: x *= C
このとき x を A にするための最小操作回数を求めよ。
（C = 1 の場合は不可能なので C > 1 とする）

・例
A = 16, C = 5 の場合、
  0[+3][*5][+1] = 16
が最短なので、答えは 3 回である。


・補題１
最適な操作列に [*C][+?][+?] という連続部分列は不要である。

・証明
x[*C][+?] では作れないが x[*C][+?][+?] でなら作れる値の集合は [Cx + C, Cx + 2C - 2] である。
そして x[+1][*C][+?] で [Cx + C, Cx + 2C - 1] を作れるので、[*C][+?][+?] という操作は不要である。


・補題２
最適な操作列の先頭に [+?][+?][+?] は不要である。

・証明
0[+?] や 0[+?][+?] では作れず 0[+?][+?][+?] でのみ作れるのは [2C - 1, 3C - 3] である。
そして C > 2 なら 0[+1or2][*C][+?] で [C, 3C - 1] を作れ、C = 2 なら 0[+1][*2][+1] で { 3 } を作れるので、
どちらにせよ先頭が [+?][+?][+?] である必要はない。


操作 [+?] を n 回以下の回数行うことを <n> と書くことにする。このとき以下が成り立つ。

・定理
最適解を求める際には操作列として以下の形をした列のみを考えればよい。
  0 <2> [*C] <1> [*C] <1> [*C] <1> ……

・証明
補題１と２から明らか。