2019-01-19
■ TopCoder SRM 747
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はそろそろ良い感じにライブラリ化したいね
