みんなのプロコン2018 参加後記 - 競プロっておいしいの？(仮)

みんプロ、お疲れ様でした。

企業コンだしWAペナないでしょｗｗｗｗとか言ってコンパイルしないで提出してWAペナ食らった人です。

みんプロ、去年と同じくCが鬼門でしたね...

サクッと解説書いていきますか。

去年と同じか？ソートしてエイ！(1WA)

問題文をよく読みましょう。

 cout<<(S.substr(0,3)=="yah"&&S[3]==S[4]?"YES":"NO")<<endl;

こんな感じで前三文字と後ろが一致してるかどうかを見れば終わり

Yahooさん、文字列大好きよね...かならず出る...

ans=ll((X/pow(10,K))+1)*(ll)pow(10,K);

前半部分の型キャスト....を忘れて1WA(コンパイルしろ)

Xを10^Kで割ったものに1を足して10^K倍してあげれば完成です。

K==0のときは1足しましょう。

これだよこれ、この明らかにbit使いそうな制約よ。

メッチャむずかったので解説してもらったことをまた解説します。

Nafmoさんのコメント付き解説ソースコード置いときます。

下の文章わけわからないと思うのでソースと一緒にご覧ください。

【訂正】13行目コメント「今の重さ(価値)」とありますが、これ価値ではなく値段です

これあれなんですが、間違ってるところあるらしいのでちょっと待ってください()

修正したつもり...(18/02/18 17:43追記) また間違ってたら教えていただけると...

問題概要

解法

売る部分と買う部分に分けて2回Bitを用いてDPをします。
買う部分のDPはナップザックですが....容量(値段)が大きく、価値も大きいので、2^Nで全探索するナップザックを書きます。
ただ、最大容量が変わると、最適解も変わるので、引数がすごいことになります....
最大容量(持ってるお金)を売った商品の数で表します、すると18通りに落とせます。
(売った数がわかれば今持ってるお金もわかるため)
どの商品が残ってるかのbitと最大容量を表すNをメモする再帰を書きます。
最大容量を表すNは変更できないので、ものを入れるナップザックをやるとやりにくいので、買わない商品を全体の値段の合計から引き算するナップザックをやります。買うパート終わり。
売るパートの話ですが、残ってる商品のbitがわかれば
- 何個目まで売ったか
- いま保持しているお金
など必要な情報がわかるため、メモするのはbitのみで良い
売ったら商品が一つなくなるのでN回ループを回して、何をなくすのが価値を最小化できるか調べる。
先の買うパートのDPに今ある商品のbitと何個売ったかを渡して呼ぶのと、売った状態の計算結果のmaxを取ったものを返して完成です。