cafelier@SRM

SRM 474

SRM | 17:43 |

SRM 474 の成績・ソース (要ログイン) : AC/AC/TLE : そろそろvolatilityの低さで争いたくなってきた

500開く

• 『連結な無向グラフが与えられます。頂点0からの最短経路木は何個ありますか。mod 1000000007で数えてね。』
  • サイズろくに見てないけど確か50頂点くらい

• えーと、普通にDijkstraを走らせると最短経路木１つなら作れる。
• で、Dijkstra やってる時に自由度がある部分、つまり
  • 既に最短経路が定まった集合から、次に近い頂点への最短路辺が複数出ている場合
• こういう状況がある場合に、この自由度をひたすら掛け算してれば求まる、よね。

• えーとpriority_queueを書いて
• popした先頭だけじゃなくて、同じ距離になる候補はpopしまくって、
• 自由度の分を掛け算しながらあとは普通にDijkstra。

• ううむけっこう時間かかってしまった。コーディング遅い。
• sampleあったし、瞬殺しないといけない問題っぽいから即submitしちゃえ

250開く

• すでにトップ10人くらいは250と500両方解いてる…250も瞬殺問題か。
• 『10億次元くらいの空間の中を、どっかの座標を±1変える、という操作を最大50回行ってふらついてる人がいます。同じ箇所を２回通ったかどうか判定してね』

• 10億次元のベクトルを本当にvectorで作る…わけにはいかないので
• どうせ50座標しか動かさないのだから、その座標の情報だけ覚えておけばいい
• map<int,int> でベクトルを表現
• 指示どおり動かす
• 50^2 で、同じ位置にきてないかmapを比較して判定
• おわり。できた。

1000開く

• 『N頂点のツリーをN頂点のグラフに埋め込みたい。やり方は何通り？mod 1000000007で。』
  • N≦14

• テストケース作り
  • 最小例はN=1
  • 最大は…とりあえずグラフの側は完全グラフの方が埋め込みパターン数多いからそうしておこう
  • ツリーの側は、えーとツリーをこの入力の書式で書くのめんどいな
  • とりあえず0-1-2-3-...-13 みたく直線的につながってる例を入れておく

• N=14ってすごく小さいな！
• 2^N が余裕でできるレベル

• ツリーはrootが頂点0であると見なすことにして
  • f(tv, gv, G)
  • を、「ツリーの頂点tvから始まるsubtreeを、tvをグラフの頂点gvに対応させつつ、グラフの頂点集合Gをぴったり使って埋め込むパターン数」とする
• 答えは Σ_{gv∈グラフの全頂点} f(0,gv,グラフの全頂点)

• これfの引数 N * N * 2^N 通りしかないのでメモ化再帰するだけじゃないですかね。
  • 14*14*16384。300万くらい。
• 書き書き

• ええと、tvの子供達にGを分割してあげなきゃいけないわけだよな。
• Gのsubsetを列挙して、それでまあ適当に。
• 子供のindexでもメモ化再帰するか。
  • g(tv,gv,G,i)
• みたいな表

• できた
• しかしスピード怪しいなー
• 表一個埋めるのにsubset列挙とかしてるから、
  • 14^3*(2^14)^2
• くらいになってないか最悪

• しかしとりあえずサンプルとさっき入れたデータは数百msで通った
• とりあえずsubmitしちゃえー！

• で、もっと酷い例は…
• ツリーを普通にツリーっぽくしてみよう
• 3分木っぽいのを入れてみた

• うわー30秒くらいかかる
• ダメだこれは

• 色々改善策を考えるも思いつかず

撃墜タイム

• 250も500もそんなに間違えるポイント無さそうだし
• 1000のTLE狙いかな

• お、自分と全く同じ方針っぽい人がいる
• さっきの三分木を投入！
• …あれ、間に合ってしまった。なぜだー -25

感想

• スピードで負けてるなあ。ぬぬぬ
• あと
  • for(subset=all; subset; subset=( (subset-1)&all ) )
• と書いている人がいて、なるほどなあと感心している。こんどから使おう