ARC099

ABC100でD問題までいけたから今回はARC

開始時間忘れてて21:17からスタート

C - Minimization

まず全体の最小値を出す。

前から順番に見ていって、最小値ならば次の数字へ。

そうでない場合、その数からK個目の間に最小値があれば、その区間全体をつぶせばいいのでカウントを１個増やして現在地からK+1番目の数へ移動。

最小値がない場合、現在地の１個前をつかってK-1個を変換する必要があるため、カウントを増やして現在地からK番目の数へ移動。

この場合に、変換する領域が１個でも重なっていれば前後は問わないので、一番最初の数からK番目の数までに最小値がない場合でも、計算上の問題はない。

ここまでで14分。解く速さがほしいなあ。

D - Snuke Numbers

ためしに10000くらいまで計算してみるも、法則性がいまいちつかめない。

前の数と次の数の間隔が少なくなることはなく、その間隔は10の累乗であることはなんとなくわかった。

ということで、今の間隔と、その間隔に10をかけたもののそれぞれについて比較を行って、間隔を増やしたほうが値が小さくなるならば間隔を増やす、という処理を行ったところAC。

なんだけど時間が1分ほどオーバーしてた。

完全な証明を思いついてないのももやっとするなあ。

Dで詰まっている間にEを見ていて、問題は似たようなのを過去にやった気がするなあってなったけれどぱっと思いつかず。

ファミリーを作っていってどうこうって形だったと思うけど。

このへんは経験不足だね。