Hatena::Grouptopcoder

Hiro180の日記

 | 

2019-01-19

TopCoder SRM 747 02:57

DDCCと順番入れ替わるけど終わったばっかりなので許して

Easy

問題を把握する、N=2ならなんか適当に選べばよい、Nを1つ増やすと何が起こる? -> 今あるものと足してdになる個数最大を付ければ良い? -> 0とdがあると壊れるけど、最初に0とd以外を選べば絶対大丈夫 -> 出す

Medium

max固定DP以外で解けるものではないため -> long doubleとはいえ精度が怖いのでちょっと工夫して前計算をする -> 出す

Hard

区間DPをすれば解けるがそれはオーダーが壊れる -> プロットする -> 右下へのLISをやればOK -> x座標順に見ていくと、BITをノードにもつsegtreeがあれば良いから、できる -> 出す (上位陣速すぎませんか?)

challenge

System Test

通る、5位

Rating

2562 -> 2634

感想と反省

Hardでもたついた以外の反省がないけどMedもちょっと遅いし全般的に速度が足りないのかなぁ (比較対象がトプランなことには目を瞑る)

BITをノードにもつsegtreeはそろそろ良い感じにライブラリ化したいね

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/Hiro180/20190119
 |