srm424

調子の悪い時は書かないsrm日記。

div1:250

2〜9で与えられた数を割っていけば良い。最初2から割って100が2*2*5*5で4になってしまった(正しくは4*5*5で3)ので9から割るようにした。
passed system test 225.63

div1:600

600だけど簡単。strengthとintellectは50 * 1000 = 50000まで上げる事が可能だが1000あれば全てのmissionをクリア出来てしまうのでそれぞれ1~1000までしか考える必要が無い。またあるポイント配分に到達可能であると分かった時の残余ポイントは一意に定まるので、状態は1000*1000しかない。なので配列dp[1001][1001]を用意して到達可能なポイント配分をチェックしていけば良い。一見最悪ケースが1000 * 1000 * 50000 = 500億になるので終わらない気もするがdpは疎なのでなんとか終わる(最悪0.4secくらい)。こんなんで良いのか〜？と思ったけどなんか通ってしまった。
passed system test 365.79

div1:900

ナイーブにやると400億になって死ぬ所まで読んだ。
opened

div1全体で85位になれたのでどんだけ上がるか楽しみだ〜