Second UVa regional warmup（20141101）
UVa 12846
$2$ 人でゲームを行う．行動できなくなったら負け．先手必勝かごて必勝かを判定する問題．
$N$ 枚の円形に並んでいる花びらのうち，$M$ 枚，ある場所を基準として $K_1,K_2,\ldots,K_M$ 番目の花びらをすでに取った．
各ターンでは，好きな花びら $1$ 枚か，もともと隣り合っていた花びら $2$ 枚を選び，それを取る．
花びらは $1$ 枚以上取られているので，適当に回転することで，最初と最後の花びらが隣り合ってない状態（円じゃなくて直線上で考える）にできる．
最初に全てのパターン $2^N$ 通りについて先手必勝かごて必勝かを判定しておけば，各テストケースに対して簡単に答えが出せる．
うまくビット演算使えば，時間計算量は $O(N 2^N + T N)$ 程度．
この部分を表示するには表示権限を持つユーザーでログインする必要があります．
Current time: 2024年04月25日09時42分20秒
Last modified: 2014年11月08日19時38分34秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20141101_1
トップページに戻る
Logged in as: unknown user (not login)