Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

Colombian Collegiate Programming League 2012 (2012-06-03)
UVa 12469

問題概要

2人でゲームをする.打つ手がなくなったら負け.先手必勝か後手必勝かを判定する問題.
最初N個の石がある.(Nは1000以下)
各ターン,1個以上,前回相手が取り除いた数*2個以下取り除く.
一番最初のターンでは,1個以上,N-1個以下取り除く.

解法

DP.状態は残りの石の数と,このターンで取り除ける数の最大値で,状態数はO(N^2).
状態遷移を全部試すと,O(N^3)になって間に合わないが,取り除ける数の最大数を取り除かないのであれば,取り除ける数の最大数を1減らした状態に帰着されるのでO(N^2)でできる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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