【CODEFORCES】Code For 1 - 競プロ日記

難しさ

・考え方***

・実装***

・面白さ*****

問題文（日本語訳）

コウタ君はある整数xを $\frac{x}{2}$ ,x mod 2, $\frac{x}{2}$ に分解するのが好きです.
コウタ君は整数nが与えられたので、nが0か1になるまで上記の分解をし1が何個あるか知りたいと思いました.
例えばn=10の場合は[10]->[5 0 5]->[2 1 2 0 2 1 2]->[1 0 1 1 1 0 1 0 1 0 1 1 1 0 1]となり、1の数は10です.
しかし昨夜徹夜でゲームをしていたコウタ君は眠いです.
そこであなたはコウタ君の代わりに[n]を0か1になるまで分解した時に左からlとrの間にある1の数を数えてください.

入力
$0≦n≦2^{50}$
$1≦l$
$1≦r$

ただし、[tex:r-l≦10⁵]

出力
lからrの間にある1の数
lとrにある1も含む

方針

・愚直に実装して全部の01求めようとしたら地球爆発するのでlとrの間だけ調べるように工夫する

・深さ優先全探索？再帰関数使う

コード

色々な方のコードを参考にしています.

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

//入力
ll int l, r;

//全部分解したら長さがどのくらいになるか
ll getLength(ll x){
    return (x <= 1) ? 1 : (getLength(x/2)) * 2 + 1 ;
}

//nを分解,Lはnが広がるであろう左端,Rは右端
int dfs(ll n, ll L, ll R){

    //範囲外ならこれ以上探索しない
    if(L > r || R < l) return 0;

    //おかしいのでreturn 0
    if(L>R) return 0;

    //0か1になったら出力
    if(n<=1){
        if(L>=l && R<=r) return n;
        else return 0;
    }

    //分解した時の中心
    ll m = (L + R) / 2;
    return dfs(n/2, L, m-1) + dfs(n%2, m, m) + dfs(n/2, m+1, R);
}

int main(){
    ll n;
    cin >> n >> l >> r;
    cout << dfs(n, 1, getLength(n)) << endl;
}