hotpepsiの練習帳

SRM 633

math | 16:57

Div1 Easy (250) PeriodicJumping

問題

• 二次元平面上に蛙がいる
• ジャンプできる距離の配列が与えられる
• {2,5}が与えられたときは距離2,距離5,距離2,...のようにジャンプできる
• ジャンプする方向はx軸またはy軸に平行でなくてよい
• (x,0)に到達するために必要なジャンプの回数を求める

方針

• 総和をsumとすると、sum < |x|のときは常に到達不可能
• 基本的にはsum >= |x|なら到達できる
• が、test case3のようにでかい値が含まれているときはだめ
• 最大値をMとして、M > (|x|+sum-M)のときはどういう行きかたでも到達できない(原点とxを頂点にした3角形が作れない)
• そうでないとき、すなわちM <= (|x|+sum-M)なら、方向を工夫すれば必ず到達できる(多角形が作れる)
• 2週以上するときは、Mが2回以上含まれていて、sum以下のどこにでも行けるので、総和の判定だけでよい
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_633/PeriodicJumping.cpp

結果

o-- +3 75.00 + 150 = 225.00pts 43rd/737 rating 1557 -> 1712 (+155)

他の総和を超えたらというのはよくある感じだが、正解できてよかった。

総和をintにしていると死ぬ100,{1,1<<29×8}というケースを用意したらはまって3撃墜。

highestの記念にスクリーンショット撮っておいた。

http://togetter.com/li/720547