ABC108D

本日はAtCoderのお話．
暇なときに過去問を埋めていて，そのときにかなり詰まった問題があったので自戒を込めて解説してみる．

問題は，こちら：
atcoder.jp

ABCのほかにARCでも使われたっぽいですね．
2年弱前の問題．

であることを考えると，の二進展開っぽいことをすればよいというのまでは想像がついたが…

自分が通した解法

最初は二進展開っぽいことを二分木でやってみようとしたが普通に頂点

数がを超えた．そりゃそうだ．
他に良い手が思いつかなかったので，解説を眺めることに．
一直線のグラフを作って少しずつ調整するっぽいな，ということだけ認識してそこから自力でやってみることにした．

ここでかなり苦労したのだが，結果的に通せた解法を紹介してみる．

が冪の場合は簡単で，例えばの場合には図のようにすればよい．

冪でない場合が問題でである．
考察として，各点までで打ち切った場合に，どの長さのパスまで存在するかを書いてみる（半開区間で書いてあることに注意）．

最終的に，一番右下を にできればよいわけだ．
番目のノードまで，この図の形でグラフを作るとすると， までは何も手を加えなくても実現できていることが分かる．

そのため，まずは を満たす最大の を求める．
現状ではこんな感じ．

については良いことにすると，残るは である．
どこかに辺を足すことで残りの部分について対応していきたいが，各点までのパスの長さが から始まっていることを考えるとどこかに の長さの辺を足すのが妥当そうである．

例えば，のノードからのノードへと長さ の辺を足すことにすると，新たに の長さのパスが増えることになる．
これは， のときは追加してよいが，そうでない場合は過剰にパスが増えてしまう．
従って，この判定を繰り返すことで徐々に残りの区間が減っていき，正しく解答できる．

イメージとしてはこんな感じです．