SRM526.5 Div.2

結果

oo- (+0/-0) 478.37pts 105th(Div.2)
1190->1221(+31)

Div1復帰しました。

250　MagicStonesStore

ゴールドバッハ予想を使うとちょっと楽になるらしい。
sieveしてから全探索、引数nに対して2*n個というのを初め忘れていて提出が遅れた。

Passed System Test 239.06pts

500　MagicCandy

1...nまでで平方数を取り除いて、番号を1から振り直して平方数を取り除いて…を繰り替えして
どれが最後になくなるかという問題。
sampleを見ると割と後の方になるようである。なんとなく含まれる最後の平方数に近いのかなぁと思う
もののよく規則がわからず、手作業を始める。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

































































































-
















































1     4         9                   16
  2       6             12                      20
    3         8                  15
        5            11                      19
            7                 14
                  10                      18
                           13          17

というように書いてみる。初めは

1 - 4 - 9  - 16
2 - 6 - 12 - 20

3 - 8  - 15
5 - 11 - 19 

という規則かと思いいくつか考えてみるもよく解らず、むしろ
(1),(2),(3,4),(5,6),(7,8,9),(10,11,12),(13,14,15,16),(17,18,19,20)
という規則になっていることに気づく。
なので、nが含まれるグループの先頭の数字を返せばよい。
i-thのグループの末尾は
i*i(if i%2==0),(i/2)*((i/2)+1)で表せるものの実装ミスりそうなので
素直にループで調べていくことに。最大sqrt(10^9)回なので間に合うはず。

で、適当にテストして合ってそうなので提出。

• >Passed System Test 239.31

challenge

素数判定ミスってるのが1個あったけどNoのケースがみつからずに終了。

感想

Div.1復帰はまぁよかった。
Div.2-500もうまく規則を見つけられて通せたのでよかったのではないか。
あとはもう少し早く通せるようになりたい。

以下500のソース

class MagicCandy {
public:

    int whichOne(int n) {
        int i=2;
        if(n == 1) return 1;
        while(1){
            n -= i / 2;
            //dump(n);
            if(n <= (i+1)/2){
                if(i%2 == 0){
                    return (i/2)*(i/2)+1;
                }else{
                    return (i/2)*((i+1)/2) + 1;
                }
            }
            i++;
        }
    }
}