競プロっておいしいの?(仮)

読者です 読者をやめる 読者になる 読者になる

ABC 056 D - No Needとの戦い。

 eiyaプロ。ありがとうございました。

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

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

軽く解説していきたいなと

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

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

とりあえず部分点から

DP部分はbool値を返す。

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

  1. iより前のカードで総和jを取れるか
  2. 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点とったら、高速化のお時間です。

さて、高速化ですが

私の知る限り

  1. 尺取
  2. 二分探索
  3. 実は低数倍高速化すると高速言語ならもしかして...?
  4. (Clangの力でゴリ押し)(やってないからわからない)(反転)

 


 

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

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

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

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

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

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

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


・・・・・・・・

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

 

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

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

私のソースはこちら

感想。

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

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

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

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

よろしくお願いします。

それでは。また明日。