0w1

Probability

CFR 662 A. Gambling Nim ( Linear Basis, Math, Probability )

Problem - A - Codeforces題意: 有 N 張卡牌,正面和反面各有一個非負整數。現在兩個人玩遊戲,每場開局每張牌會均勻隨機呈正面向上或背面向上。把 N 個呈現在上的數字當做 N 堆的石頭,進行 Nim 的遊戲。雙方絕頂聰明的前提下,先手贏的機率為何。制約: T…

Yuki 162 8020運動 ( DP )

No.162 8020運動 - yukicoder題意: 你上下各有一排 14 個連續的牙齒。 你現在 A 歲,你想知道你在 80 歲時,期望會有多少顆牙齒剩下。 牙齒掉落的機率是 P[ 左邊的牙齒是否剩下 + 右邊的牙齒是否剩下 ]。解法: 考慮動態規劃: dp[ i ][ j ][ k ] : 經過 i …

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人的情況下,自己是第一…