AOJ 0289 - Infinite Express

むひゃー．

解法

非負整数nの最右ビットをrms(n)で表す．ただし，rms(0) = 2^30とする．
例. rms(5) = 1 (5 = 0b101)，rms(6) = 2 (6 = 0b110)
(n>0ならば，このrms(n)はn & -nと書ける．BITでおなじみ．)
位置sにいるとき，i級快速(iは1<=2^i<=rms(|s|)を満たす整数)に乗ることができる．
このとき，位置dを越さない最大のiを選ぶ．これを位置dにたどり着くまで行なったときの回数が最小回数である．

コード

#include <iostream>
 
int main(){
    int N, s, d, t, s_, mx, i;
    std::cin >> N;
     
    while(N--){
        std::cin >> s >> d;
 
        t = 0;
        while(s != d){
            s_ = std::abs(s);
            mx = s_ & -s_;
            if(!s){mx = 1 << 30;}
            for(i=mx;;i/=2){
                if(s + i <= d){s += i; break;}
            }
            t++;
        }
         
        printf("%d\n", t);
    }
}

ショートコード

短くしてみた．Nいらんやろと思ったが，そうするとREが出たので入れた．
PCK公式の解説にはより短そうなの(しかも，ショートコーディングは意図していない)があったので，Ω＼ζ°)ﾁｰﾝ．

main(N, s, d, t, i){
    for(scanf("%d",&N);N--;){
        for(t=!scanf("%d%d",&s,&d);s-d;t++){
            for(i=(i=abs(s))?i&-i:1<<30;;i/=2){
                if(s + i <= d){s += i; break;}
            }
        }
        printf("%d\n", t);
    }
}