hotpepsiの練習帳

SRM 675

22:11

https://competitiveprogramming.info/topcoder/srm/round/16625/div/1

Div1 Easy (300) TreeAndPathLength3

問題

• 頂点数500以下で長さ3のパスがS本の木を作成せよ

方針

• Sが497以下のとき、S+3個を横一列につなぐだけでいい
• Sが498以上のときは、ウニ状のノードを二つ連結して作る
• たとえばノード0にノード1,2,3,4,5、ノード1にノード6,7,8,9がつながっていて、ノード0と1を連結させると、長さ3のパスは4×4=16個のパスできる
• R=√Sとして、R+1個とR個のノードでウニを作って連結して、不足分は適当なノードの末尾に横一列で足す
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_675/TreeAndPathLength3.cpp

結果

o-- 114.79 245th/412 rating 1219 -> 1268 (+49)

超久しぶりに正の点数を得て良かった。なんとかDiv1に残留した。

ウニ状のノードといえばSRM 566のPenguinSleddingで、そっちもたまたま解けた。

Mediumはメモリ1MBという鬼のような制限だったらしい。

http://togetter.com/li/911082