hotpepsiの練習帳

SRM 587

17:03

Div1 Easy (250) JumpFurther

問題

• 階段の最下段にいる
• 全部でn回ジャンプできる
• i回目のジャンプの距離はiである
• 特定の段が壊れていて、そこには着地できない
• 到達できる最高位置を求める

方針

• iずつ足していく
• 壊れている段に遭遇しなければそのまま
• 壊れている場合は最初の1段をジャンプしないことにする
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_587/JumpFurther.cpp

Div1 Medium (550) TriangleXor

問題

• 高さ1、幅Wの長方形に三角形をXORで塗っていく
• 面積の整数部分を求める

方針

• kojingharangさんのを読む
• 大きいほうから三角形を塗っていく
• 最初のW+1個のは1回分だけ足す
• 次のW個の高さは1.0-(1/(W+1))で、ゼロにするために2倍の面積を引く
• k番目の高さは1.0-(k/(W+k))で、符号を反転していく
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_587/TriangleXor.cpp

結果

o-- +1 142.14pt 443rd/491 rating 1280 -> 1205

easyは、最終段のときはジャンプできないだけで到達できると読んでしまい、再提出。

落ち着けば最後に-1すればいいだけだが、2回計算してしまった。