TopCoder member SRM 474 (Div 1) - simezi

授業なんてなかった。

165.86 / 247.50 / Unopened
0チャレンジ

178位 1517->1574

なにこの250.遅すぎるorz

N次元空間をn回移動する。各移動は座標軸のいずれかに平行な向きで、移動量は1である。
それぞれの移動が平行な座標軸の番号、および座標軸の正の向きに移動することを+,負の向きに移動することを-であらわした文字列が与えられるとき、同じ点を二度通ったかどうかを判定せよ。

N≦10^9, n≦50を満たす。

Nでかっ。nは小さいので座標軸は50個考えればいいのか。
map<int,int>にnon-zeroな座標軸と座標の値を入れておいて、それをsetに入れていけばいいのかな。

set<map<int,int> >なんて使えるのだろうか。
書いた。

あれ！？サンプル通らないぞ。。。
non-zeroな座標の個数をステップごとに出力してみる。
ちゃんとmap自体は作れてるっぽいなあ。
コンパイルは通ったけどやっぱりset<map<int,int> >はダメなのかなあ。

うーん時間やべえ。
座標圧縮で書き直すか。書いた。
サンプルあわねえ！！何でだよ！！

あーsetにinsertしてないだけだった！！！
訂正。submit.もうだめぽ。

頂点がn個の無向な連結グラフが与えられる。このグラフの0番目とi番目(0<i<n)の最短距離を、全て変えないように辺を取り除き、辺がn-1本の木を作る。
このようにしてできる木の総数を求めよ。

うおーTopCoderぽい問題だなあ。。。考えるが方針たたない。
とりあえずワーシャルフロイドは使いそう。

まずはサンプルとかグラフを紙に書いてみる。

あれー各点間最小距離が変わらない木なんて作れない場合結構あるんじゃないの？
長さが2-2-3の三角形のグラフとか無理じゃん……
なんか誤解してるような。問題文読み直そう。

あ、各点間じゃなくて0との距離か……
枝を取っていくんじゃなくて、逆に0番から枝を追加していくことを考えたらいいんじゃないか。
0番からi番まで木が出来てるとき、i+1番の枝を追加するのは0からiが連結ならそれまでのグラフに拠らないから、i+1番をつなげる枝の本数を掛け算していけばいい。

これでかつる！！
ワーシャルフロイドして、ソートして、近い順に枝の本数を数える、と。書いた。送信。

やっぱ遅いなー。。。

10分じゃ解けるわけないのでUnopened.
毎回e,mに時間取られすぎだよ……

撃墜ケースを考える。
500でlonglong使わずに桁溢れさせてる人とか居るかもしれないが、そんなのどうやってケース作ればいいんだ……？？なぞい。

250から落とせそうなのを探す。N次元のベクトル作ってる人とか……さすがにいねーか。
サンプル親切だし落とせそうなのはないなあ。。。
g:topcoder:id:n4_tさんのmapに最初に全部0を入れるという解法が頭良かった。

500を見る。みんな大体自分と方針一緒っぽい。落とせそうなのは……これもない。
コーナーケースもサンプルにあるし……

15分間みんなのソースをじっくり眺め続けて終了。

Easy,Medium落ちてる人あんまり居ない！自分のも通れ！

通った。