YukicoderContest289 B問題P1.5 「最弱WEAKER」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
$ 1 \leq N \leq 10^9
解法・お気持ち
石が0個のときに勝つプレイヤーを$ Lとします.
このとき,負けるプレイヤーを$ Rとします.
減らす石の量は$ 3^kであり,$ 3^k \% 2 = 1です.
よって,石が偶数個持っていれば勝ちになります.
これは以下のように0個のときから図をかいても計算できます.
https://gyazo.com/a796dca51ede3092161aae3dd4f00808
0個のときは必ず勝てるので○です.
1個のときは,遷移先がすべて○(0個のとき)なので,自身は負けます.よってバツです.
同様に3個のときは,遷移先の0個/2個は両方勝っているため,相手に負けを押し付けられず3個のときは負けます.
よって,このようにボトムアップに図をかいても偶奇であることがわかります.
計算量
$ O(1)
新たな学び
反省点
コード
code: cpp
int main() {
LL N;
cin >> N;
if (N % 2 == 0) YES();
else
NO();
}