結果

問題 No.3 ビットすごろく
コンテスト
ユーザー w10y26
提出日時 2017-04-29 17:41:50
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 1,456 bytes
コンパイル時間 651 ms
コンパイル使用メモリ 78,408 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-01 08:40:39
合計ジャッジ時間 1,683 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#define ll long long
#define ffor(i,a,b) for (int i=(a);i<(b);i++)
#define rfor(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define rep(i,n) for (int i=0;i<(n);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#define SIZE 100001
#define MOD 1000000007
#define INF 100000000
using namespace std;
bool flag[SIZE];
int kaisuu[SIZE];


//bitcount
int bitcount(int n){
	int s=0;
	while(n>0){
			s+=n%2;
			n/=2;
	}
	return s;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	rep(i,SIZE) flag[i] = false;//falseで初期化
	rep(i,SIZE) kaisuu[i] = INF;//kaisuuを最大値で初期化->最小値でどんどん更新
	kaisuu[1] = 1;
	int n;
	cin >> n;
	queue<int> q;
	q.push(1);//startの1を入れる

	while(!q.empty()){
		int now = q.front();//現在地
		q.pop();//値を抜く
		if(flag[now]) continue;//すでに訪れた場所
		flag[now] = true;
		int d = bitcount(now);//1の数を調べる

	//まだ訪れたことがない場所であれば回数を入れて位置をqueueに入れる
	if(1 <= now - d && now - d <=n && flag[now - d] == false){
		kaisuu[now - d] = min(kaisuu[now]+1,kaisuu[now - d]);
		q.push(now - d);
	}
	if(1 <= now + d && now + d <= n && flag[now + d] == false){
		kaisuu[now + d] = min(kaisuu[now]+1,kaisuu[now + d]);
		q.push(now + d);
	}
}
	cout << ((flag[n])? kaisuu[n]:-1)<< endl;



	return 0;
}
0