SRM370

Rate 1747 -> 1774
Room placeは13位と微妙だったけど，Division placeは185位とそんなに悪くなかったのでかろうじてRateは上昇．

250

やるだけ．一瞬doubleの精度がどうなのかと思ったけどたぶん問題ないと思って提出．226.17pt

500

動的計画法．なんだけど，最初使えるコストとi番目の中継点の場所を引数で最小rangeに関してDPかなと思ったけど100000 * 50 * 100って間に合わないよなと思ってよくよく考えるとrangeを固定した時i番目の中継点を位置を定めた時に残りのコストの最大なものを記憶していけばそのrangeで実行可能かわかるのでそれでできる．225.15pt

950

500解いたときにあと10分弱しかなくてsummary見たら500より950解いてる人の方が多くて問題選択ミスったかなと思ったらやっぱりミスってた気がする．

問題は数kが与えられた時約数の数がちょうどk個のもので最小の自然数を求めよという問題．自然数をnとしn= p_1^(a_1) p_2^(a_2)...p_m^(a_m)とするとnの約数の数は(a_1 + 1)(a_2+1)...(a_m+1)と書けるのでkを素因数分解してa_1,a_2,...a_mを定めていけばいい．ただし単純に貪欲でとるのは2^2を(3+1)ととるか(1+1)*(1+1)のどちらをとるかは必ずしも自明ではないので探索を書く必要がある．

チャレンジでは950で貪欲で解いてた人を1人みつけたのでそれにたいしてチャレンジをして+50pt

950は僕の部屋の人はほとんど探索を書いていてだいたいSystem testも通ってたけどDivision Summaryをみると950で貪欲で解いた人がかなりいてチャレンジで落ちてた人が結構いた．