TCO16 Algorithm R3B

chokudai(高橋 直大)@AtCoder社長 @chokudai

とりあえず自分が組んだのはO(n^1.6180)くらいの最大独立集合ソルバ。これは割と簡単に組める。

すぎむ @sugim48

最大独立集合問題の半分全列挙解法、最近出まくっているせいで easy の部分問題と化したのか…

よすぽ @yosupot

天下一でzerokugiが組んだ、「点をシャッフルして貪欲」*沢山が強すぎる

よすぽ @yosupot

強いというのは実装量的な意味も含みます

chokudai(高橋 直大)@AtCoder社長 @chokudai

半分全列挙で解く方法もあるらしい。

すぎむ @sugim48

@yosupot え、もしかして追加できる頂点を貪欲に追加していくだけでうまくいきますか

よすぽ @yosupot

@sugim48 はい

すぎむ @sugim48

@yosupot 今度から使お

chokudai(高橋 直大)@AtCoder社長 @chokudai

もうちょっとちゃんとやるだけで1.466まで落ちたらしい（調べた）

よすぽ @yosupot

@sugim48 次はいつ出るんですかね…

すぎむ @sugim48

@yosupot さあ…

すぎむ @sugim48

天プロで優位に立つために各種 NP-hard の問題に対する近似解法を用意しておくか…（いいえ）

rng_58 @rng_58_old

2^26 で多項式パート消すだけです

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

クソなぞなぞになりたい。

すぎむ @sugim48

りんごさんの easy、O(N * 2^N) に見えるけど、よく考えたら O(2^N) だ

rng_58 @rng_58_old

厳密に言うと多項式パートは消えてなくて bitset 的なことになってる

rng_58 @rng_58_old

Hard ヒント: FFT です

agw @masashinakata

TCO16 Algorithm R3B - Togetterまとめ: togetter.com/li/1017316