2016-05-20
SRM 675
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という鬼のような制限だったらしい。
コメントを書く
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20160520