「みんなのプロコン 2018」

Noimin @noisy_noimin

みんプロの予選は終わりましたが、のいみんプロにはなれませんでした。

beet @beet_aizu

これで落ちてたら笑うが（さすがにね

btk @btk15049

@beet_aizu わーい

よすぽ @yosupot

@southerwolfie d[i] >= aなる最小のiを保存したら出来ると思います(まあ200じゃないね)

semiexp🍆 @semiexp

@southerwolfie @yosupot ソートされてるので，途中までは r で以降 d[i]

kuuso @kuuso1

「高橋君がk個売る→青木君はk個マスクする→高橋君は残りで買える価値を最大化（これをv)する，でこの時青木君はvが最小になるようにマスクを選んだことにする」じゃないのかな．．

NATSUGIRRRRI @natsugir

C 答えで二分法。2^Nの頂点のグラフで「到達したら購入できる頂点」を通らないように商品を壊すパスがあれば、答えはそれ未満

Япон Бүресе🏴‍☠️ @southerwolfie

@semiexp @yosupot rが徐々に変わっていきませんか？

有為 @uwitenpen

Eは最終的にほぼライブラリ貼るだけだった

beet @beet_aizu

3回くらい書いたのでさすがに階乗の逆数もライブラリにしとこ

Япон Бүресе🏴‍☠️ @southerwolfie

まあ貴重なワクコンだと思えばいいですね でも僕は正面からぶつかる系幾何が欲しいよ

くれない。 @kurenai3110

誤読してた、買ったら取引終了するのね

semiexp🍆 @semiexp

@southerwolfie @yosupot 前計算しておくと切り替わる位置はすぐ求められそう

かつっぱ@ 競プロYouTuber @catupper

あ〜　睡眠調整のためにみんプロでなかったのにこの時間まで目を開けていてしまったorz

beet @beet_aizu

C、最初勘違いしていてx個売った時点で青木くんがマスクするやつをx個選べると思っていてメモ化再帰だと思えなかった

koyumeishi @koyumeishi_

min(d[i], k) は std::set 使った

有為 @uwitenpen

高橋君が1個ずつ売るからまとめ売りするときと青木君の挙動違うと思ってた

やざてん🍆 @Yazaten

Eのググりたくなるポイントってどのへんなんだろう

Hideyuki Tanaka @tanakh

TLEするのはわかるけどWAで結構落ちてるのはなんでなんだろ

ＳＫＹ/sky58🍊 @skyaozora

C、3^18解も相当頭いいなこれ（先に青木君に都合よく閉じられたと仮定して、閉じられた分だけ売れるということにすればいいのか）あとやっぱ二分探索解もあるよね。二分探索も一瞬浮かんだけど解答に結び付けられなかった。ほんとちょっとでも難しい問題になると全く解けなくなるな･･･

merom686 @merom686

3^Nと言われて形が見えないのでまあ。

satanic@研究💪 @satanic0258

えぇΣ_k{C(n,k)×2^{n-k}}=O(3^n)って通るの

kuuso @kuuso1

あとで考えるか．．

satanic@研究💪 @satanic0258

かいてみるか

btk @btk15049

ちなみに、bitdpでループで立ってるbitのところだけ触るように高速化すると2^n×n^2から2^(n+1)×nまで落ちます