TopCoder SRM 526.5 Div1 Easy MagicCandy

問題

n個のキャンディが一列に並んでいる。
この中から食べるキャンディを一つ、次のような手順を繰り返して選ぶ。

• 残っているキャンディが1つ以上の間、平方数番目（1,4,9……番目）のキャンディを全て取り除く。
• 残ったキャンディに左から順に新しく1,2,3,…と番号をふる。

選ばれるのは何番目のキャンディか求めよ。

制約条件

n≦10^9

方針

小さい数で実験して法則をみてみる。
すると、答えは等差数列を二つくっつけたような数列になっているっぽい。

なんでこういう数列が答えになるのかは考えたけどよくわからなかった。

ソースコード

class MagicCandy {
  public:
  int whichOne(int n) {
    int ans=1;
    for(int m=1,i=1;m<=n;i++){
      rep(k,2){
        m+=i;
        if(m<=n)ans=m;
      }
    }
    return ans;
  }
};