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

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

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

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

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

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

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

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

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

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…

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…

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