結果

問題 No.3 ビットすごろく
ユーザー トミー
提出日時 2024-01-04 03:31:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 1,175 bytes
コンパイル時間 2,076 ms
コンパイル使用メモリ 204,440 KB
最終ジャッジ日時 2025-02-18 16:07:34
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define REPP(i,n,m) for(int i=n;i<=m;i++)
#define REPM(i,n,m) for(int i=n;i>=m;i--)
#define VI vector<int>
using namespace std;
void yn(bool f){if(f){cout<<"Yes\n";}else{cout<<"No\n";}}
bool isnum(char c){return ('0'<=c&&c<='9');}

int btcnt(int n){
	int cnt=0;
	while(n!=0){
		cnt+=(n&1);
		n>>=1;
	}
	return cnt;
}

int main(){
	int n;
	cin>>n;
	if(n==1){
		cout<<1;
	}
	else{
		
		vector<vector<int>> adj(n+1);
		vector<bool> flag(n+1,false);
		deque<int> queue;
		vector<int> depthArray(n+1);
		int queuelen=1;
		bool solved=false;
		
		flag[1]=true;
		depthArray[1]=1;
		queue.push_front(1);
		
		for(int i=0;i<=n;i++){
			if(n>=i+btcnt(i)&&i+btcnt(i)>0){
				adj[i].push_back(i+btcnt(i));
			}
			if(n>=i-btcnt(i)&&i-btcnt(i)>0){
				adj[i].push_back(i-btcnt(i));
			}
		}
		while(queuelen!=0&&!solved){
			int v=queue.front();
			queue.pop_front();
			queuelen--;
			for(auto& u:adj[v]){
				if(u==n){
					solved=true;
				}
				if(!flag[u]){
					flag[u]=true;
					queue.push_back(u);
					queuelen++;
					depthArray[u]=depthArray[v]+1;
				}
			}
			
		}
		if(solved){
			cout<<depthArray[n];
		}
		else{
			cout<<-1;
		}
		
		
		
	}
	
	
}
0