TCO 2019 2B

Beijing Onsite 的熱身,不過居然晉級了,下一場還是好好打(受虐)一下吧。。。

250 MedianFaking

Brief Description

給定 n 個人,每個人有 m 個測量結果。取所有人所有測量結果的中位數(偶數時下去整)為最終結果。
已知測量結果應該是 goal,問至少修改幾個測量結果可以使得結果恰好為 goal,在這種情況下最少需要參與修改的人數又是多少。

Analysis

如果要讓結果恰好為 goal,那麼比 goal 小的數和比 goal 大的數都不能超過一半,顯然這兩邊只會有一邊不符合。
於是我們只要關心這一邊需要修改幾個數就好了,並且現在只需要考慮一邊,第二問只要統計出每個人可以帶來的貢獻,排序貪心即可。

500 DivisorSequences

Brief Description

給定 n,我們將 n 拆分成若干個整數相加的形式:n = a1 + a2 + … + am。
要求 a 序列嚴格遞增且 a_i 整除 a_{i+1},問 m 最大可以是多少。

Analysis

觀察 15 = 1 + 2 + 4 + 8…
我們發現如果把 1 去掉的話,有 14 = 2(1 + 2 + 4)…
這樣我們就發現了一個子問題!
定義 f(n) 表示將 n 分解,並且第一個數是 1 的方案數,每次減去 1 後枚舉約數遞歸即可。那麼實際的答案可能第一個數不為 1,所以開始再額外枚舉一次約數就好。
複雜度雖然不太容易估計,但貌似不記憶化也能過。

1000 SlightlyBigger

Brief Description

Alice 和 Bob 報數,從 1 到 oo,目標是比對方報的數只大一點。
– 如果恰好差小於等於 maxDiff,那麼大的一方獲勝,並得到 ifNear 分。
– 否則,小的一方獲勝,並得到 ifFar 分。

雙方都採取最優策略時,問 Alice 報的數恰好為 query 的概率。
(ifNear < ifFar <= 2×ifNear)

Analysis

第一眼感覺這個題很神,看了一下大家後來都是高斯消元做的。但是不知道怎麼列方程。後來請教了一下畢克老師,畢老師說其實這個問題跟剪刀石頭布是一樣的,就你想像一個剪刀石頭布遊戲,然後給你一個收益矩陣。
對方把自己的策略的概率分布向量已經告訴你了,在最優情況下,你發現你即便知道這個向量也並不能讓你取得任何優勢。
這就是傳說中的 納什均衡,於是只要設表示報 x_i 的概率,根據上面這些關係,列出線性方程組,高斯消元即可。

納什均衡雖然提供了 n 組方程,但是 rank 似乎是 n-1 的,最後別忘了加上所有概率分布之和等於 1。
可以預計答案不會很大,可以帶極限數據跑一下看看邊界。