yukicoder : No.1742 Binary Indexed Train

題名は割と好き。
https://yukicoder.me/problems/no/1742

問題

整数Nに対し、0～(2^N-1)の番号を持つ駅が順に並んでいる。
個々には0～N番の(N+1)通りの列車が走っている。
i番の列車は、0番から初めて2^i個毎の駅に停車する。また、駅番号が大きくなる方向にしか移動しない。

以下のクエリに答えよ。
S番の駅からT番の駅に移動するとき、最適な列車を選ぶと、最小何個の停車駅を通ることになるか。
なお、S＜Tとする。

解法

現在いる駅で停車する列車のうち、Tを超えない範囲で1回で最も遠くまで進む列車をどん欲に選べばよい。

int N,Q;
ll S,T;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	while(Q--) {
		cin>>S>>T;
		int ret=0;
		while(S<T) {
			for(i=60;i>=0;i--) {
				if((S&((1LL<<i)-1))==0 && S+(1LL<<i)<=T) {
					S+=(1LL<<i);
					ret++;
					break;
				}
			}
		}
		cout<<ret<<endl;
	}
}

まとめ

これも★2.5でもいいかもね。