SRM 587 Div1 Easy JumpFurther

問題

無限に続く階段があり、あなたはその0段目にいる。あなたはN回行動を起こし、i回目(1-indexed)の行動では+i段上に進むか動かないかを選べる。しかしbadStep段目が壊れていて、この段に立つことはできない。到達できる最上段を求めよ。

やりかた

毎回上に上がっていっても壊れた段には踏み込まないとすると、N回目でN*(N+1)/2までは行ける。しかし踏み込んでしまう場合には、1回目の行動のみなにもしないことで、踏み込まないようにすることが出来、なるべく上まで行くことができる。

以下ソース。

class JumpFurther {
public:
  int furthest(int N, int badStep) {
    bool bad = false;
    for(int i = 0; i <= N; i++) if(badStep * 2 == i * (i + 1)) bad |= true;
    return N * (N + 1) / 2 - bad;
  }
};