hotpepsiの練習帳

SRM 622

22:43

Div1 Easy (250) BuildingRoutes

問題

• N個の都市があり、それぞれの都市間経路の距離が与えられる
• ある日、それぞれの都市から、別の全てのそれぞれの都市へ一斉にバスが走る
• バスは最短経路のどれかを通る
• バスが最大T台以上通る可能性がある経路は危険
• 危険な経路の合計の長さを求める

方針

• Warshall-Floydで最短経路を求めておく
• ある経路iからjへの移動について、p->i->j->qという移動に使われる可能性があるかどうかpとqを全列挙する
• p->iへの最短 + i->jの長さ + j->pへの最短 == p->qへの最短ならば使われる可能性がある
• Failed System Test
• (書き直し)
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_622/BuildingRoutes.cpp

結果

x-- -2 -50pts 513rd/516 rating 1633 -> 1472 (-161)

添え字を書き間違っていた。

WFの初期値がよくわかっていないが、この問題の場合は同じ地点を0のまま扱うとシンプルになった。

http://togetter.com/li/673231

SRM 621

01:52

Div1 Easy (250) RadioRange

問題

• 座標(0,0)に放送局がある
• いくつかの街の中心座標と半径が与えられる
• それぞれの街について、放送局の電波が完全に届かないか、または、街の中全てがカバーされていればgood
• 放送局の半径を0以上Z以下の乱数で選ぶとき、全ての街がgoodとなる確率を求める

方針

• 街が存在する範囲をbad rangeとして、0以上Z以下で、bad rangeでない部分を数える
• 開始位置でソートする
• 現在地を0からはじめて、前のbad rangeの終点から、次のbad rangeの始点までをgoodとして足していく
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_621/RadioRange.cpp

結果

o-- +1 152.62 + 50 = 202.62pts 254th/763 rating 1585 -> 1633 (+48)

範囲外のをきちんとはじくのが意外と面倒。最初に0からZまでの範囲にしておくと少し楽。

写経撃墜でhighest更新。瞬間的にcountry rankの100位に入った。感激。

http://togetter.com/li/669609

TCO 2014 Round 2A

全探索 | 23:38

Easy (250) SixteenBricks

問題

• 16個の積み木がある
• それぞれの大きさは1×1×Hである
• 4×4のグリッド状かつ縦に並べたとき、最大の表面積を求める

方針

• 低いものと高いものを交互に並べるのが良さそう
• 高いもの8個と低いもの8個を市松模様に並べる
• それぞれの配置をnext_permutationで全部調べればいけそう
• 高いものの配置は2つ試したら変化がなかったのでとりあえず固定する
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/tco_2014/SixteenBricks.cpp
• 高いものについては、低いもののうち一番高いものよりも必ず飛び出しているので、どういう配置でも同じだった

結果

o-- 152.30pts 381st/1338 rating 1504 -> 1585 (+81)

TCOボーナスではあるけど、割と好調。

http://togetter.com/li/668654

Google Code Jam 2014 Round 1C

02:24

Problem A. Part Elf (8pts/12pts)

問題

• 40代前のご先祖様は100%の人間またはエルフのどちらかである
• 混血度合いが分数で与えられる
• 100%のエルフが何世代目なのかを求める

方針

• どのように足しても分母は2の倍数になる
• 分子をビットで見るとき、血が濃いほうが上のビットに残る
• すなわち最上位ビットの位置が最短世代数に等しい
• が、最初に約分する必要がある
• https://github.com/firewood/topcoder/blob/master/gcj_2014/R1C_A.cpp

Problem B. Reordering Train Cars (10pts/25pts)

問題

• いくつかの文字列があり、一つの文字列に連結する
• 同じ文字は連続している必要がある
• 連結のしかたが何通りあるか求める

方針

• smallはnext_permutationで全て試す
• https://github.com/firewood/topcoder/blob/master/gcj_2014/R1C_B_s.cpp
• 文字が途切れている場合、それらは一体に連結する必要があるので、それらをunion findで連結して、グループの数Gを求める
• グループ単位の並べ方は自由なので、G!通りに並べることができる
• 同じ文字だけでできた文字列がN個あるときは、それらの連結のしかたはN!通り
• それらの積が答え
• あとはどうつなげても同じ文字が連続できないパターンをはじく
• 実際に書いたコードでは連結済みかどうかの判定を簡略化するため、先に同じ文字だけでできたものを別カウントした
• もっと簡単に書ける
• https://github.com/firewood/topcoder/blob/master/gcj_2014/R1C_B.cpp

結果

oooo-- 55pts 349th/4309

ひどいソースだけど通過した。別の方法でsmallが解けるとlargeの検証に使えるので助かった。

SRM 620

着想 | 23:15

Div1 Easy (250) PairGame

問題

• 1以上の二つの整数のペア(x,y)がある
• 次のターンで(x+y,y)か(x,x+y)のどちらかにできる
• (x,y)からはじめて(a,b)と(c,d)のどちらにでも到達できる数のうちx+yの最大値を求める

方針

• (x,y)からはじめて(a,b)までの間の各地点で(c,d)に到達可能か探索
• stack overflowで死ぬ
• 書き直し
• 値(p,q)に到達するには、片方の値はx+yなので、小さいほうを引いたものからしか到達できない
• つまり逆方向の探索だと、値は一意になる
• (a,b)と(c,d)について、a>cかb>dのときは、a,bを一手戻し、そうでなければc,dを一手戻し、一致するまで繰り返す
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_620/PairGame.cpp

結果

GCJに備えて仮眠したら寝過ごした。連続出場記録が87で途切れてしまった。

SRMをベースに生活スケジュールが組まれているということを再認識したのであった。

とはいえ出ていてもたぶん0点だったと思う。

http://togetter.com/li/665676