Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM460 DIV1 参加記録 (この記事を編集する[管理者用])

2010年02月07日02時から.

Assignment

平和そうな部屋じゃないー.

EASY

k種類の質問の中からn回質問しました.
ただしどの質問も少なくても1回は質問してます.
同じ質問をしたら同じ答えが返ってきます.答えはYesかNoのどちらかです.
n回の質問の答えが得られたとき,考えうる質問のやり方は何通りあるか.
nは9以下.kはn以下.

???
問題読解に手こずる….
全質問の答えがYesかNoか決めて,どの順番でやったか全探索…は計算量怪しい,ちゃんと組み合わせ的に計算した方が良いかも.
….
…….
なんか,滅茶苦茶時間掛かった気がするけど,書けた.
これで大丈夫かな…?わからん.
もうサブミットしてしまえ.

MEDIUM

AとBの2人がいる.
Aがある都市cに行くと,AはランダムでminA[c]点以上maxA[c]点以下の整数点数がもらえる.
Bがある都市cに行くと,BはランダムでminB[c]点以上maxB[c]点以下の整数点数がもらえる.
AとBはそれぞれランダムにn個の都市の中からk個の都市を選んで行く.
AとBの点数が等しくなる確率は幾つか?
nは最大で40で,もらえるポイントの上限値も40.

確率だ….
DPなのか?
前からこの都市に行くかどうか場合分けしていって,残りr個の都市の中からm個の都市を訪れるなら,次の都市を訪れる確率はm/rとすれば良いのでは…?
本当か?これが本当ならDPでいけるけど….
わからんけど,書いてみる,サンプル通れば大丈夫だろう.
サンプル通った!
サブミット.

HARD

枝を付け加えて,全ての都市間の同じ年を共有しない行き方が1通り以上2通り以下となるようにしたい.
何通り方法があるか,mod ほげほげで求めよ.
ノード数は20以下.

グラフきたー,全然わからん.
うーん?
これって,閉路が高々1個しかなくて,連結なものの数を数え上げれば良い?
全域木の数はn^(n-2)だから簡単で,枝を1個付け加えれば良い!
いやいや…,最初から繋がってるからn^(n-2)じゃないし….
2^nの状態数でDPすれば求まる…か?→そんなこともない
いやいやいやいやいや,そもそも,全域木作ってから枝付け加えると同じのできるし!
えーと,どうやるんだ,同じの数えない方法って….
ここで行き詰って,残り20分ぐらいあったけど,わからなかった.

Challenge

勘違いして1ミス….結構痛い.
だからチャレンジする前にはちゃんと確認しようよーorz

System tests

EASYとMEDIUM通る.良かったー.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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