ABC 056 D - No Needとの戦い。 - 競プロっておいしいの？(仮)

Nafmoです。No Needを解き切りました(昨日)。

eiyaプロ。お世話になりました。

部分点→計算量落としでいきます。

間違ってるところを発見し次第報告ください

DP部分はbool値を返す。

そんでもって再帰関数は2つ書きました。

これで K-A[i]<=X<Kになるような部分集合の総和Xを探しましょう。

iをN回全部調べます

jを0～K、kをK-A[i]-j～Kの二重ループで動かしていきます。

存在したらbreak;して回していきましょう

片っ端からXを探して条件を満たすところでbreak;しましょう

O(N^2K)らしい

あああああああああああああああああああああああ

さて、高速化ですが

私の知る限り

私は二分探索を取りました

b<aのときaが不必要なとき、bもいりません。

計算してください。解説読んでください。解説動画見てください。

対偶証明とかでもいけます。とにかく理解してください。(ここに2日かかる)

で、この単調性を使って二分探索ができます。

部分点解のようにN回調べる必要がなくなります(logNで済むらしい)

で、これで二分探索します。

・・・・・・・・

クッソがああああああああああああ

[]と[)で少し二分探索に誤差？があった模様。

プロにhackしてもらって解決。

初めて解いた600点問題。すごい辛かった

DPだって未だにかけないし...

ゆっくり解いて実力あげたいですね...

私は頑張って迷惑かけながら精進していきますので

よろしくお願いします。

それでは。また明日。