TCO16 Algorithm R3B

連絡用なり @_n_ari

事前で変更した点だからなぁ

連絡用なり @_n_ari

また明日

連絡用なり @_n_ari

まぁグラフに落ちることが分かってただけ進歩かなぁ

連絡用なり @_n_ari

それでも1時間かかってようやくって感じだけど(2^26が若干不安で切り出せなかった

連絡用なり @_n_ari

というか乱択で通るのか(26頂点完全グラフって若干不安

連絡用なり @_n_ari

と思ったけどyukicoderのが通るんだしそうか

連絡用なり @_n_ari

Aquila掘りのせいで乱択アルゴリズムを疑い始めてるよ

連絡用なり @_n_ari

若干天下一Dを後悔してる(TCOはポ

連絡用なり @_n_ari

失ったものより得たことを見返すのです

連絡用なり @_n_ari

演習量が足りないんだなぁ……

連絡用なり @_n_ari

競プロって「考えるフェーズ」を鍛えるために過去問もじっくり解くべきか、「発想フェーズ」を鍛えるために過去問は解説読んで視点を増やす程度にすべきか、ちょっと悩ましい(時間は有限 問題は無限)

連絡用なり @_n_ari

ここら辺も受験数学に似てる気がして面白い

連絡用なり @_n_ari

ここで考えるフェーズというのは問題をいじって別問題に落としたり計算量を落とすフェーズで、発想フェーズとは問題を見て何を使えばいいのか具体的に見出すフェーズのことを言っています

連絡用なり @_n_ari

発想はつまりは典型力ですかね

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

ところでEasyって最大独立集合求める感じであってますか（想定解が割と気になっている）

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

1<<26が入ってる解が通ってるの、割ともやっとするなあ。

連絡用なり @_n_ari

独立集合以外、若干気になる(でもn^2はさすがにという感じ

連絡用なり @_n_ari

僕は指数時間のスライド見に行って自明な枝刈りだけ入れたらミリ秒に落ちてうれしうれししてた

よすぽ @yosupot

sugoi

よすぽ @yosupot

ちょっと考えたけど、26点のグラフから文字列が構築できるから少なくとも独立集合と同じぐらいの難しさがある気がする

連絡用なり @_n_ari

ところで独立集合で0が解だと1点も選べないことになるんですけどg[i][i]=0になって違和感がやばい(場合分けして殺した

よすぽ @yosupot

(a, b)に辺があったらs += “ab”, t += “ba”を全部の辺についてやる

よすぽ @yosupot

ただまあ26頂点ならそれっぽいことすれば大体通りそう

連絡用なり @_n_ari

9時起き散華なので寝ます

連絡用なり @_n_ari

Med読めばよかった(悩む材料が枯渇した