yukicoder : No.262 面白くないビットすごろく

問題名の通りです。
http://yukicoder.me/problems/402

問題

初期値をX=1とする。
1手ごとに、Xは(Xを２進数表記したときの1の数)分進む。

整数Nが与えられる。
上記手段でXの値を増やして行ったとき、XはNを経由するか判定し、経由するならNに到達するまでの手数を求めよ。

解法

Nが10^12。
1手ではせいぜい40しか進まないので、愚直にシミュレートすると間に合わない。

想定解は埋め込み。
手元で時間を掛けて最大値までシミュレートし、10^8手ごとの途中経過を埋め込めばよい。

また別解法もあるので以下ではそちらを紹介。
2進数表記において2^20の位が変わるまで何手かかるかを前計算しておき、約2^20毎に処理を進める。。
その際、開始時の状態は[現在値を2^20で割った値の２進数表記の1の数][現在値を2^20で割った余り]として2^20の位が変わるまでの手数を求めればよい。
１手では39しか増えないので、[現在値を2^20で割った余り]は39まで列挙しておけばよい。

ll add[51][64];
ll step[51][64];
ll N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,30) FOR(j,63) if(i+j) {
		int cur=j;
		int st=0;
		while(cur<1<<20) {
			st++;
			cur += i+__builtin_popcount(cur);
		}
		step[i][j]=st;
		add[i][j]=cur-j;
	}
	
	cin>>N;
	ll cur=1;
	ll st=1;
	while(cur+add[__builtin_popcountll(cur>>20)][cur%64]<N) {
		st += step[__builtin_popcountll(cur>>20)][cur%64];
		cur+=add[__builtin_popcountll(cur>>20)][cur%64];
	}
	while(cur<N) {
		st++;
		cur+=__builtin_popcountll(cur);
	}
	if(cur==N) cout<<st<<endl;
	else cout<<-1<<endl;
}

まとめ

少し面白くなったか。これ★３でいいかもね。