Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

LiveArchive 3272 - cNteSahruPfefrlefe (この記事を編集する[管理者用])

Source

World Finals - Shanghai - 2004/2005
LiveArchive 3272

問題概要

52枚のカードがあって,半分ずつ分けて,1枚ずつ交互に重ねていく形のシャッフルを10回以下行った.
ただし,毎回シャッフルの過程で,たかだか1か所隣り合う2枚のカードがスワップしている可能性がある.
最初は順番に並んでいたとして,シャッフル後のカードの位置が与えられるので,
 何回シャッフルしたか
 何回目のシャッフルで,どこのカードがスワップしたか
を求める問題.
複数あるなら,スワップ回数最小,それでも複数あるなら,スワップした位置が辞書順最小のものを求める.

解法

枝刈り探索.
1回スワップすることで,カードの場所が変わるのは2枚なので,それを利用して枝を刈る.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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