Help us understand the problem. What is going on with this article?

atcoder ABC101

More than 1 year has passed since last update.

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数としていけば良い。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away