SRM 733

nico_shindannin（診断人） @nico_shindannin

でも、今日のとこは寝よう。お休みなさい～

agw @masashinakata

@kinaba (； ・`д・´)　ナ、ナンダッテー !!

NATSUGIRRRRI @natsugir

1000はO(n^3)がTLEした、そもそもバグがあった。再帰関数やめたら間に合ったりしないだろうか

agw @masashinakata

出る回数を減らすために出る、か...

(nは自然数) @n_vip

ケイリーはわりと好きなんだけど無断で辺にラベル付けたり根付きにしたりしてくるので地頭っぽくて嫌い

(nは自然数) @n_vip

数え上げの公式は勝手になんかしすぎ

ヘクト🐬 @osrehun

あまり良くないんですが、Medを解いて寝落ちしたら、この時間で -> 1949 (Highest)

satanic@研究💪 @satanic0258

数Mの各分割{v}(M=4=1+1+2=2+2など)についてP(n, |v|)を足すとn^(M-2)になるのかな(？)

ヘクト🐬 @osrehun

500はPrufer Sequence の構成法をもとに、縮約したグラフ上で各頂点の重みをもとに計算したら、なんか解けましたね...

satanic@研究💪 @satanic0258

えー全然違いますね

satanic@研究💪 @satanic0258

今の考え方どうしても実装も考察も大変なことになってしまうから，Cayleyの公式を元に考えてみるかぁ

ヘクト🐬 @osrehun

自分の場合、Medは \sum_{T \in Spanning tree set} \Pi_{i \in Components of the graph based on E} i番目の連結成分の頂点数^Tにおける縮約されたi番目の連結成分の次数 という感じ

ヘクト🐬 @osrehun

25位は良く考えると好成績じゃん!

ヘクト🐬 @osrehun

後輩のHighest Rateを抜いたので一安心? (いいえ、AtCoderも頑張ります)

ヘクト🐬 @osrehun

こんな変なものをどうやって数え上げるかというと、グラフの連結成分を頂点に縮約した頂点数kのグラフについて考えて、長さ k-2の Prüfer sequence を数え上げたくなる気持ちになれば、ゴールは近い。あとは、DPみたいな漸化式を立てられれば終わり en.wikipedia.org/wiki/Pr%C3%BCf…

ヘクト🐬 @osrehun

というか、今日のSRMの部屋内、強い人が多かったな (全体 25th 、Room内 6th なのビックリ)

(nは自然数) @n_vip

こんなに競プロ漬けの週末は久しぶりだったかも。まあ土曜だけだけど

ヘクト🐬 @osrehun

Prüfer sequenceを活用するのは、i の出現回数+ 1 が頂点 i の次数に対応するという事実があるので

(nは自然数) @n_vip

楽しかった

satanic@研究💪 @satanic0258

へー，長さn-2の列{a_i}(0<=a_i<n)をPrüfer sequenceってのと見なすと，n頂点のラベル付き木と一対一対応するんだ

有為 @uwitenpen

今日は GCJ2.5h(実質1.5h) HDOJ 2017中国大学生程序设计竞赛-杭州站-重现赛(4h) Helvetic (5h) ARC (実質1h) SRM (1.5h) に出ました

Conor Hoekstra @code_report

@topcoder SRM 733 Div II Problem 1 - MinimizeAbsoluteDifferenceDiv2 Solution Video youtu.be/ApEOvRWdZ7I?a

拡大

有為 @uwitenpen

13hぐらい？

satanic@研究💪 @satanic0258

んーPrüfer sequenceを理解できたようなできてないような