YukicoderContest289 E問題P3 「Archaea」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
$ N ,K \leq 2 \times 10^5
解法・お気持ち
グラフの問題に帰結して考えることができます．
まず，数を増やしていくのではなく$ N個の状態から減らしていくという逆から考えるをします． $ Nが2の倍数であれば，$ N / 2にできます．
また，必ず$ N - 3の演算を行うことができます．
すると，$ Nから$ 1の頂点へ向かうDAGとして捉えることができます．
https://gyazo.com/2bde94ae635233b8783071bfb461b49c
よって，頂点$ NからBFSをすればよいです．
再帰DPとかでも計算できると思います．
計算量
$ O(N)
新たな学び
反省点
コード
code: cpp
constexpr int INF = 1e7;
int main() {
int N, K;
cin >> N >> K;
vector<int> dp(N + 1, INF);
queue<int> Q;
Q.push(N);
while (!Q.empty()) {
auto v = Q.front();
Q.pop();
if (v - 3 > 0 && dpv - 3 == INF) { Q.push(v - 3);
}
if (v % 2 == 0 and dpv / 2 == INF) { Q.push(v / 2);
}
}
else
NO();
}