c問題は簡単だったが、D問題は500点ということもあり難しかった。
https://atcoder.jp/contests/abc101
C問題
方針
1の範囲をどんどん増やしていき全てを1にする最小回数を求める問題。考える方針としては、まず1の位置から左にk-1個ず範囲を伸ばしていき、左端までの回数を求めその回数をlとし、右側についても同様に求めその回数をrとするとl+rで答えが求まるように思える。しかし、左の個数がk-1より少なかったりした場合を考えてみるとl+rは明らかに最小でないことがわかる。なので、まず1より左側の個数について詳しく見ていく。この個数をleftnumとすると、leftnum % (k-1) = 0 の時は、前述の理論で答えが導けることがわかる。しかし、leftnum % (k-1) != 0の時は、その(k-1-あまり分)を右側の範囲を網羅するのに使えることがわかる。よって、はじめの段階で、左側について、leftnum % (k-1)について場合分けをすることで答えを求めることができる。
D問題
方針
まず厳密な考察は解説pdfに任せるが、sunuke数を実験的に見ていくと
{1,2,3,4,5,6,7,8,9,19,29,39,49,59,69,79,89,99,199,299}
とsunuke数(n+1)はsunuke数(n)についてnの各桁+1の範囲で1を加えた数になっていることがわかる。よって、sunuke数を見つけたら、その数について(nの桁+1)桁まで各桁に+1した値のn/S(n)を求めていき、その中で最小のものを次のsunuke数としていけば良い。