Entries

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

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

SRM300 DIV1 EASY/DIV2 MEDIUM - Dating (この記事を編集する[管理者用])

Source

TopCoder SRM300 DIV1 EASY (250pt)
TopCoder SRM300 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

円周上に$50$人以下の人が並んでいる状態が文字列で与えられる.
男性はアルファベット小文字,女性はアルファベット大文字で表される.
また,$100$以下の正整数${\rm K}$が与えられる.
以下の操作を繰り返した時,デートするカップルを選ばれた順番に出力する問題.

男性,女性のどちらかがいなくなっていれば終了.
最初の人を1番目と数えて,${\rm K}$番目の人を選ぶ.
また,その人の異性の中で,アルファベット順で最も早い人を選ぶ.
その2人をデートするカップルとして選び,円周上から除外する.
次回の最初の人は,${\rm K}$番目として選ばれた人の次の人.

解法

頑張ってシミュレーションする.

C++によるスパゲッティなソースコード

続きを読む

イロモネア ゴールドラッシュ (この記事を編集する[管理者用])

ルールは,審査員が10人程度いて,ランダムに選ばれた数人を全て笑わせればクリア.
ただし,選ばれる人数は,1回目が3人,2回目が4人,3回目は5人.

クリアする確率.
審査員が全員でn人いて,m人笑った場合は,C(m,x)/C(n,x).
ただし,1回目はx=3,2回目はx=4,3回目はx=5.

思ったよりも,ちゃんと後半になるほど辛くなるのがわかる.
3回目は2人笑わない人がいると辛いか.

m/n1回目2回目3回目
5/80.1785710.0714290.017857
6/80.3571430.2142860.107143
7/80.6250000.5000000.375000
8/81.0000001.0000001.000000
5/90.1190480.0396830.007937
6/90.2380950.1190480.047619
7/90.4166670.2777780.166667
8/90.6666670.5555560.444444
9/91.0000001.0000001.000000
5/100.0833330.0238100.003968
6/100.1666670.0714290.023810
7/100.2916670.1666670.083333
8/100.4666670.3333330.222222
9/100.7000000.6000000.500000
10/101.0000001.0000001.000000
5/110.0606060.0151520.002165
6/110.1212120.0454550.012987
7/110.2121210.1060610.045455
8/110.3393940.2121210.121212
9/110.5090910.3818180.272727
10/110.7272730.6363640.545455
11/111.0000001.0000001.000000
5/120.0454550.0101010.001263
6/120.0909090.0303030.007576
7/120.1590910.0707070.026515
8/120.2545450.1414140.070707
9/120.3818180.2545450.159091
10/120.5454550.4242420.318182
11/120.7500000.6666670.583333
12/121.0000001.0000001.000000

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

この記事は不定期に更新される可能性があります.

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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