Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12525 - Boxes and Stones (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12525

問題概要

2人でゲームを行う.
B個の箱と,S個の石を使う.(Bは100以下,Sは200以下)
箱は一直線上に並んでおり,1~Bまでの番号が付けられている.
最初に,プレイヤー2が,S個の石を,好きなように箱に割りふる.
この時,プレイヤー2が勝てるような割り振り方は何通りあるかをmod 1000000007で求める問題.
各ターンは以下のように進む.
 箱Bに石が入っていたらプレイヤー1の勝ち.石が1個もなくなっていたらプレイヤー2の勝ち.
 プレイヤー1は,石を2つの集合に分ける.
 プレイヤー2は,その集合のうち,どちらか片方の石を全部捨てる.他の石は次の箱に移動させる,(箱kに入っていたものは箱k+1に移動させる)

解法

Bに近い箱から順番に見ていく.
箱B-1には,1個までしか石を入れてはいけない.
箱B-2には,箱B-1に石を入れたら,1個までしか入れれないし,入れてなかったら3個までいれれる.
という感じに考えて,
 残り箱の数,残り石の数,この箱には最大で何個石を入れても大丈夫か
を状態としてDPする.
色々試すと,x個まで入れても大丈夫な箱に,y個入れた場合は,次の箱には2(x-y)+1個まで入れても大丈夫なことがわかる.
ナイーブにDPすると4乗オーダーだけど通る.和を適当に求めておくと3乗オーダーにできると思う.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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