Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2138-b3d7ecd7
この記事にトラックバックする(FC2ブログユーザー)

UVa 12350 - Queen Game (この記事を編集する[管理者用])

Source

ACM-ICPC Asia Phuket Regional Semilive (2011-11-06)
UVa 12350

問題概要

R*C (25*10^15以下) のチェス盤に,n個のクイーンが置かれている.1セルにおけるクイーンの数は無限.
2人でゲームを行う.打つ手がなくなったら負け.先手必勝かどうかを判定する問題.
各ターン,1つのクイーンを選び,上,左,左上の方向にに1マス以上動かす.

解法

各セルのgrundy numberが求めれば良い.
とりあえず,Cが小さい範囲で計算すると,周期性が見える.
Rが25以下なら,正確に言うと,十分大きな行番号について,行番号が自分より768小さいセルのgrundy numberは768小さい.
それを用いて計算した.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2138-b3d7ecd7
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。