Subscribed unsubscribe Subscribe Subscribe

0w1

Hi everyone, please feel free to have discussions with me!

HR Colliding Circles ( Math, Expectation )

Programming Problems and Competitions :: HackerRank題意: 有 N 個線段,用長度描述。每一秒以均等機率有兩個線段合併 ( 長度變為總和 )。問期望上 K 秒後,每個線斷所成的圓面積總和為何。制約: 1 ≤ N ≤ 1e5 0 ≤ K ≤ N - 1 0 ≤ R[ i ] ≤ 1e4解法: 首先…

CFR 768 D. Jon and Orbs ( DP, Probability )

Problem - D - Codeforces題意: 有 K 種卡片,每天都可以抽一張,抽到的種類機率分佈是隨機均勻。Q 筆詢問,問第幾天開始可以確定,對於任意一種卡片,有 P / 2000 的機率有至少一張。資料規模: First line consists of two space separated integers k, q…

CFR 442 B. Andrey and Problem ( Math, Probability, Greedy )

Problem - B - Codeforces題意: 你有一件事情要完成,但你太懶所以想請你朋友做。你可以同時請很多朋友做,但是如果兩個以上個朋友同時做出來,他們會覺得你把他們當工具人,不特別看待他們。求最佳策略下,可以不讓朋友傷心而完成這項作業的機率是多少。資…

ARC 003 D - シャッフル席替え ( Monte Carlo, Hoeffdings Inequality )

D: シャッフル席替え - AtCoder Regular Contest 003 | AtCoder ARC#003D from nullmineral www.slideshare.net かなりわかりやすいスライドですが、覚えておきたいものをメモ: Hoeffdings Inequality ● X1, X2, …, Xn を独立な Bernoulli 確率変数とする ●…

CFR 148 D. Bag of mice ( Probability DP )

Problem - D - Codeforces 題意: 公主和龍玩一個遊戲,背包裡初始有若干個白老鼠和若干個黑老鼠。公主先開始,輪流取一個老鼠出來,先取出白老鼠的贏。取出後不放回,但龍取老鼠之後,會有一隻還在背包裡的老鼠,平等隨機地逃走消失不再回來。當背包裡沒有…

CFR 540 D. Bad Luck Island ( Probability DP )

Problem - 540D - Codeforces 題意: 在一座島上有三種人,只出剪刀,只出石頭,只出布的人。每一秒都有一對人會相見。每對人相見的機率都相同,如果相見的是同一種人,則什麼都不會發生,否則他們會決鬥,就跟一般猜拳規則一樣定勝負,輸的人會死掉。給三種…

CFR 476 B. Dreamoon and WiFi ( Probability )

Problem - B - Codeforces 題意: 給兩個序列,序列中的+表示向右走一個,-表示向左走一格,?表示一半機率向左,一半機率向右。求多少機率兩者終點相同。 解法: 求有多少 ? 以及有多少需要變成+,數學求機率。 string A, B; void init(){ cin >> A >> B; } …

SRM 687 Hard. Queueing ( Probability DP )

TopCoder Arena TOI 排隊約瑟夫問題 ( DP + 代數分析 ) - 0w1 和這題非常類似。 It is possible to brute force this problem until the EPS is reached, see pekempey.hatenablog.com dp[ i ][ j ] : i people in the first queue, j people in the second …

ABC 11 D - 大ジャンプ ( Probability )

D: 大ジャンプ - AtCoder Beginner Contest 011 | AtCoder Problem Statement: Given n: number of jumps, d: distance of each jump, find the probability to land in coordinate ( x, y ) when n jumps are made arbitrarily. We will first get rid of d…

ABC 8 C - コイン ( Expectation )

C: コイン - AtCoder Beginner Contest 008 | AtCoder Problem statement: Given some coins and their value, initially they are in any random permutation, all heads facing up. You will flip each coin from left to right, and every time a coin is…

TOI 排隊約瑟夫問題 ( DP + 代數分析 )

每次審判排頭有 d的機率死亡並被逐出隊伍,否則則返回隊尾。當排頭是最後一個人的時候審判不會再進行。 現在給你隊伍初始的人數 n,你的編號 k( 注意 0 ≤ k 你存活( 成為隊伍裡最後的人 )的機率為多少? 我們先令 P( i )為隊伍裡有 i人的情況下,自己是第一…