ABC 056 D - No Needとの戦い。
eiyaプロ。ありがとうございました。
Nafmoです。No Needを解き切りました(昨日)。
eiyaプロ。お世話になりました。
軽く解説していきたいなと
部分点→計算量落としでいきます。
間違ってるところを発見し次第報告ください
とりあえず部分点から
DP部分はbool値を返す。
そんでもって再帰関数は2つ書きました。
- iより前のカードで総和jを取れるか
- iより後ろのカードで総和kを取れるか
これで K-A[i]<=X<Kになるような部分集合の総和Xを探しましょう。
iをN回全部調べます
jを0~K、kをK-A[i]-j~Kの二重ループで動かしていきます。
存在したらbreak;して回していきましょう
片っ端からXを探して条件を満たすところでbreak;しましょう
O(N^2K)らしい
あああああああああああああああああああああああ
さて、300点とったら、高速化のお時間です。
さて、高速化ですが
私の知る限り
- 尺取
- 二分探索
- 実は低数倍高速化すると高速言語ならもしかして...?
- (Clangの力でゴリ押し)(やってないからわからない)(反転)
私は二分探索を取りました
b<aのときaが不必要なとき、bもいりません。
計算してください。解説読んでください。解説動画見てください。
対偶証明とかでもいけます。とにかく理解してください。(ここに2日かかる)
で、この単調性を使って二分探索ができます。
部分点解のようにN回調べる必要がなくなります(logNで済むらしい)
で、これで二分探索します。
・・・・・・・・
クッソがああああああああああああ
[]と[)で少し二分探索に誤差?があった模様。
プロにhackしてもらって解決。
感想。
初めて解いた600点問題。すごい辛かった
DPだって未だにかけないし...
ゆっくり解いて実力あげたいですね...
私は頑張って迷惑かけながら精進していきますので
よろしくお願いします。
それでは。また明日。