Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Timus 1994 - The Emperor's plan (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1994

問題概要

$n$ 人の議員の中に $k$ 人のスパイが紛れ込んでいる.
各ターン以下の行動を行った時,最終的に残るスパイではない議員の人数の期待値の最大値を求める問題.
 1. 各スパイが,スパイでない議員を $1$ 人ずつ殺す
 2. 好きな人数を選び,その人数だけ議員をランダムに選び,議員資格を剥奪する
スパイがいなくなるか,スパイしかいなくなると操作を終わる.
議員資格が無いスパイは活動できない.
$1 \leq n \leq 200$
$1 \leq k \leq \min(20, n)$

解法

$n,k$ を状態にしてDPする.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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