結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2022-05-09 19:52:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,376 bytes |
コンパイル時間 | 841 ms |
コンパイル使用メモリ | 77,844 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-16 17:43:12 |
合計ジャッジ時間 | 1,863 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <iostream> //cin, cout #include <vector> //vector #include <algorithm> //sort,min,max,count #include <string> //string,getline, to_string #include <cstdlib> //abs(int) #include <utility> //swap, pair #include <deque> //deque #include <climits> //INT_MAX #include <bitset> //bitset using namespace std; int main() { int N; cin >> N; vector<int> min_cost(N + 1, INT_MAX); deque<int> next_posi; deque<int> next_cost; next_posi.push_back(1); next_cost.push_back(1); while (!next_posi.empty()) { //現在値情報の引き出し int now_posi = next_posi.front(); int now_cost = next_cost.front(); next_posi.pop_front(); next_cost.pop_front(); //終了2:過去ベストとの比較 if (now_cost >= min_cost[now_posi]) { continue; } else { min_cost[now_posi] = now_cost; } //終了3:ゴール到達 if (now_posi == N) { continue; } //移動量 bitset<16> bs(now_posi); int step = bs.count(); //前:次週位置の追加 if (now_posi - step >= 1) { next_posi.push_back(now_posi - step); next_cost.push_back(now_cost + 1); } //後:次週位置の追加 if (now_posi + step <= N) { next_posi.push_back(now_posi + step); next_cost.push_back(now_cost + 1); } } if (min_cost[N] == INT_MAX) { cout << -1 << endl; } else { cout << min_cost[N] << endl; } return 0; }