UVa 12846 - A Daisy Puzzle Game

Source

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)$ 程度.

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年11月22日00時46分35秒
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)

ログイン: