naoya_t@hatenablog

いわゆるチラシノウラであります

〈旧ABC埋め〉旧配点時代のABCで面白かった/手こずった問題メモ

旧配点時代のABCをぷちぷち埋める
(面白かった or 手こずった問題をメモ)

旧配点なのですべて100点*1

ABC 027

C - 倍々ゲーム (100)

なぜこの問題で最善手を考える余地があるのかというと

  • 1手目(高橋くんのムーブの後):[2,3]
  • 2手目(青木くんのムーブの後):[4,5,6,7]
  • 3手目(高橋くんのムーブの後):[8,9,10,11,12,13,14,15]
  • ...
  • k手目((k%2?高橋:青木)くんのムーブの後):[2^k, 2^{k+1})

の範囲に必ず来るという性質と、(高橋くん・青木くんともに)2xを選ぶことで小さい値に、2x+1を選ぶことで大きな値に着地できるという性質を利用できるから。

2^k \le N\le 2^{k+1}-1 になるkとは(Nの2進表記)-1であり

  • kが奇数のとき
    • 2^k \le x \le N なら青木くんがもう1手打ててしまうので高橋くんの勝ち
    • N \lt x \le 2^{k+1}-1 なら高橋くんの手がはみ出しているので青木くんの勝ち
  • kが偶数のとき
    • 2^k \le x \le N なら高橋くんがもう1手打ててしまうので青木くんの勝ち
    • N \lt x \le 2^{k+1}-1 なら青木くんの手がはみ出しているので高橋くんの勝ち

なので

  • kが奇数のとき
    • 高橋くんは小さく青木くんは大きくなるように打つ
    • 高橋くんの勝利条件はx\le N
  • kが偶数
    • 高橋くんは大きく青木くんは小さくなるように打つ
    • 高橋くんの勝利条件はN\lt x

最初問題を読み違えていて、その後勝利条件が間違っていて、サンプルケースで答えが合うまでに手間取った。

→AC
https://atcoder.jp/contests/abc027/submissions/3930675

*1:時々101点とかあるけど