Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM445 DIV1 (この記事を編集する[管理者用])

2009年07月24日00時から.

Links
Match Overview
Match Editorial
Summary of Japanese (otinn.com)
参加記録 (blog)

2次元平面上に50個以下の家の座標が与えられる.座標は整数で絶対値は50以下.
新しく家を建てたいのだが,新しく家を建てる場所は,その場所からk番目に近い家までの距離を最小化するように家を建てる.
その最小値を求める問題.

新しく家を建てる場所を0.5刻みに全部調べる.

0と1からなるn文字の文字列で,毎回いくつか0を選んで1に変えるか,1をいくつか選んで0に変えることができる.
最初は全部0で,移動可能な中で,毎回まだ出現してない文字列で辞書順最小のものに変化する.
最初のk日の間に出てくる文字列の中で辞書順で最も遅いものを答える問題.
nは50以下,kは2^n以下.

実は上の桁から再帰的に求めることができる.

暗号で,アルファベット小文字大文字52文字をそれぞれアルファベット52文字に対応させる.
ただし,小文字大文字を無視して同じ文字に対応させることはできない(aをAに対応させることができない).
対応関係が一部与えられたとき,それを満たす対応関係の数をmod 1234567891で求める問題.

文字を自分とは対応しているか,自分の小文字大文字を反転したものと対応しているかなど適当に分類してDP.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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