どう考えてもとてもめんどくさいことになりそうなので、機械的に解きたいと思ってやってみたら、案外間に合った。
解法
現在の速度や、速度が上限に達する時間が整数でなくなる瞬間があるのが面倒くさいポイントだが、おそらくたかだか小数点以下1ケタくらいで収まるだろうということは予想できる。
なので、をそれぞれ10倍してやれば、以下のような機械的なDPを導出できる。
現在時間、速度をそれぞれ
としたとき、所与の条件を満たしつつ最終的に速度
に辿り着けるか
これはメモ化再帰で簡単に求めることができ、各についてtrueである最大の
を値とするグラフの横軸となす図形の面積が答えとなる。
しかし、制約がそこそこ大きくなりそうなので、時間計算量は大丈夫なのか？というところが気になる。
とすれば、
だから、
。遷移先はたかだか3つなので、各遷移は
と言ってよい。
また、最大のでOKなことが確認できれば良いので、枝刈りもある程度できる。
なので、高速な言語であればまあ間に合うかなという見積もりができる。(CとかC++とかRustとか)
時間計算量については以上の通りだが、Rustではデフォルトのスタックサイズが非常に小さいので、メモ化再帰におけるスタック消費が激しいことも相まって、スタックオーバーフローでREが出てしまった。
これはstd::thread::Builderでスタックサイズを増強したスレッドを作ってやることで回避できた。
結果的には300msec強程度と、速度的にも特に問題なくACすることができた。
時間計算量は、上にも述べた通り。実装例は以下の通り。
