SRM 648

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

@evima0 え、本郷で労働してたんですか。

えびま @evima0

@1_000_000_007 家だと進まないので図書館でvexorian業やってます。

とーらす🌸📦🌕✨🍀 @torus711

書いた : SRM 648, div2-3 d.hatena.ne.jp/torus711/20150…

えびま @evima0

先週のSRM648の公式解説の公開が遅れてしまっていて申し訳ありません。Hard の簡単な説明をお願いされたので流します。 Div1Hard: Fragile(850) n頂点(区別あり)の単純無向グラフで橋をちょうどk本持つものの個数をmod10億7で求めよ。 0≦K<N≦50

えびま @evima0

@evima0: Hard 解説1: n≦N, k≦Kのすべてのn,kについてn頂点k橋の「連結な」グラフの数が求められたら、それを何個か並べてN頂点K橋にしたものが問題のグラフなので、普通のn^4のDPをやるだけで答えが求まります（二項係数を使う）。（つづく）

えびま @evima0

Hard 解説2: というわけでn頂点k橋の連結なグラフの数をnが小さい順に求めていきます。とりあえずk≧1のときを考えます。突然ですが頂点0と1の間に辺があってそれが橋であるようなグラフを考えると、その辺を取り除くことでグラフが2つに分裂するので、（つづく）

えびま @evima0

Hard 解説3: 0側の頂点数と橋の数を全部試すことで再帰的に数が求められます。これの何が嬉しいかというと、連結なn頂点k橋のグラフを1つuniformly at randomにとってきたとき、頂点0と頂点1の間に橋がある確率はk/(n choose 2)なので、（つづく）

えびま @evima0

Hard 解説4: 今求めた数を (n choose 2)/k 倍することで、n頂点k橋の連結な無向グラフ全体の個数が求まります。k=0だとこの方法が使えませんが、n頂点の連結な無向グラフの総数（Google可能）からk≧1のときを全部引けばOK。全体O(n^4)時間。（完）

えびま @evima0

週刊Petr(petr-mitrichev.blogspot.com/2015/02/this-w…) の648Hardに対するコメント "requiring some serious combinatorics and.."(参考:rng_58> well, for me it's like standard 500)

えびま @evima0

Petr 様が"exceptionally tricky, requiring some serious combinatorics and dynamic programming mastery"っていう問題がstandard 500って…りんごさんの感覚はぶっとびすぎだなあ。

えびま @evima0

こういう問題が12問でたら今年のICPCの優勝は間違いなくUTだろうけど出ないんですよねこういうの。

えびま @evima0

UT優勝というか、りんごさん vs 残りの359人 でもりんごさんが勝ちそう。

タッパーをオーブンで焼かない @DEGwer3456

@evima0 tourist「典型」という可能性は

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

スピード勝負ですらtouristとsemiexpで互角なレベルだから、ITMOにICPCで勝つにはtourist以外の人が嵌るかりんごさんしか解けないような数学ゲーが出るしかないんじゃないかな

えびま @evima0

@DEGwer3456 ああ旅人さん + ほか358人だったらさすがに勝てそう。

えびま @evima0

@1_000_000_007 2013 の B はまさにその数学ゲーでしたが結局ITMOにも最後に解かれた上、もしそれが解かれなくても他で圧倒的な差をつけられ完全敗北という感じでしたね。

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

@evima0 ただ、あのBの時間とかを見るにやっぱり高度な数学ゲーは圧倒的にUT有利な気がします。(まああのセットで圧倒的な差をつけられるのは仕方がないと思う)

えびま @evima0

@DEGwer3456 でもSRM599（僕が初めてwriterした回）のPetrが Petr vs tourist含む他739人 でもおそらく勝ってたほどの壮絶な圧勝で（otinn.com/topcoder/al/su…）、これくらいのパフォーマンスをだせばいけそう。

えびま @evima0

@1_000_000_007 ああいうのが2つ出れば一気に有利になるかもですが、まあ2つは出ませんね…

タッパーをオーブンで焼かない @DEGwer3456

@evima0 毎回思うけどPetrのmedの速度はおかしい

えびま @evima0

@DEGwer3456 Petrさんはこういう「落とし穴に気を付けて全列挙」系は世界中の誰も寄せ付けないほど強いですね。

hogloid @hogloid

SRM648(evimaさん回)のmed，そんなにバグりやすいかなあ．まあハマるかどうかは運のことが多いからナントモいえないけど

hogloid @hogloid

こういうのnamonakiくん強いのか，まあ印象通り（？）

nico_shindannin（診断人） @nico_shindannin

まだ、KitayutaMartやってます。方針はできてるつもりだけど、なかなか立式ができない…。こういうのは非常に苦手…

えびま @evima0

あ…しまった「先週」月曜のSRM 648のEditorialをまだ書いてなくて新たに650Hardも加わったのに音ゲーを24曲もやってしまっていた…