LeetCode Weekly Contest 114

アルメリア @armeria_betrue

@tempura_cpp ひえー 知りたいです

夕叢霧香@競プロ @kirika_comp

これって全テストケースが time limit 以内に実行できないとだめなの?

てんぷら @tempura_cpp

@armeria_betrue 愚直にやると3^Nです(各数字についてAで使う、Bで使う、使わないのどれかなので)。 また最大化するものはどちらかで使ったものの和としていいです(最後に半分を出力するだけ)

てんぷら @tempura_cpp

@armeria_betrue このとき、差が同じになるような分け方に対しては和が大きいものだけ残しておけばいいのでdp[i][j]で(i番目までで差がjになるものの和のmax)とすれば今回は和の幅が狭いのでとても速くなります

アルメリア @armeria_betrue

@tempura_cpp おおおお天才 ありがとうございます、理解しました！

てんぷら @tempura_cpp

@armeria_betrue Nについてこの制約で3^Nからの高速化がbitで頑張るじゃなくて普通のナップサックDPなの少し罠ですよね笑

アルメリア @armeria_betrue

@tempura_cpp ですねー…2^Nで片方列挙＋もう片方としてあり得る値をbitset管理、なんかも書きましたけどTLEでした。ガッツリ計算量落ちるんですね…

てんぷら @tempura_cpp

@armeria_betrue 方針は上と同じで枝狩りの代わりに半分全列挙にしてもO(N*3^N)くらいになってACできました

てんぷら @tempura_cpp

DPは枝狩りだなという気持ち

ほげもち @hogemochi

@tempura_cpp 575

てんぷら @tempura_cpp

@hogemochi AC

てんぷら @tempura_cpp

@armeria_betrue O(N*3^N)が通るわけがなくて、O(N*3^(N/2))です

うし @ei1333

2292->2291(-1)

うし @ei1333

Eに貼るだけがあるのゆるせねえな（知らずにCを考え続けるうしくんもゆるせねえ

hogeover30 @hogeover30

1737 → 1611

てんぷら @tempura_cpp

最近のこどふぉの感じだとAtCでもAve. 2600 くらい出せてもおかしくなさそうに思えるなぁ

hogeover30 @hogeover30

年越し前に着水してしまいそうだ

hogeover30 @hogeover30

C解けたけどコレ知らなきゃ無理じゃん geeksforgeeks.org/sum-products-p…