GCJ 2019 Round3 B

Problem B. Pancake Pyramid

Brief Description

給定長度為 n 的序列 h[i]。
每次你可以選擇一段連續子序列 [l, r],你可以給其中某些項執行 +1 操作,使得操作後形成一個金字塔形狀(先遞增再遞減)。
問遍歷所有的子序列,總操作次數最少是多少。

Analysis

相同元素可能會帶來重複計數,我們統一先認為相同的元素出現時,左邊的更大。

考慮暴力做法。注意到我們這裡 只有 +1 操作,所以可以直接貪心。
每次枚舉區間,設:
- M[l][r] 表示 [l, r] 區間最大的數的位置。
- L[l][r] 表示把 [l, r] 這個區間處理成遞增序列的最小代價。
- R[l][r] 表示把 [l, r] 這個區間處理成遞減序列的最小代價。

那麼我們枚舉所有的區間,統計所有 L[l][m] + R[m][r] 就是答案,可以預處理這些數組,複雜度 O(n2),可以過小數據。

考慮大數據,其實題目里已經瘋狂暗示你了要用單調棧(stack)。。。
回憶 POJ 2559. Largest Rectangle in a Histogram

我們發現之前是要處理出,以 h[i] 為最低點,左右兩邊分別可以延伸多遠。
這裡恰好是求,以 h[i] 為最高點,左右兩邊分別可以延伸多遠,假設就是 Dl[i] 和 Dr[i]。
這樣唯一不同的是,我們還需要一個累計代價數組 Sl[i] 和 Sr[i],分別表示以 h[i] 為最高點,往左和往右累計的代價。
因為最後答案就是:

我們可以在維護單調棧的過程中,順路求 Sl 出 Sr。不放考察從左往右掃描求 Dl 的過程。
設當前掃描到位置 i,將要被彈出的棧頂元素為 sp,這個位置右邊一直到 i 這個區間現在都至少需要是 h[sp] 的高度才符合要求。
記這個代價為小寫的 sl,我們預處理部分和後可以 O(1) 的求出 sl。記新的棧頂元素的位置與剛才被我們彈出的棧頂元素的位置之間的距離為 sp - s.top(),
sl 需要被統計 sp - s.top() 次。最後加上這個區間本身的代價 Sl[sp]。

stack<int> s; s.push(0); REP_1(i, n) {
    Sl[i] = 0;
    while (h[i] > h[s.top()]) {
        int sp = s.top(); s.pop();
        Int sl = Int(h[sp]) * (i-sp-1) - (hh[i-1]-hh[sp]);
        Sl[i] += sl * (sp - s.top()) + Sl[sp];
    }
    Dl[i] = i - s.top();
    s.push(i);
}

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。
可以預計答案不會很大,可以帶極限數據跑一下看看邊界。

JAG Spring Contest 2015

提交地址

Overview:

做 ASC 42 的 B 題的時候遇到的問題。。。ASC 42 的題目是:
初始有 m 元錢,目標是恰好擁有 n 元錢
每輪你可以壓至多當前你所擁有的錢數進行賭博,p 的概率翻倍,q 的概率失去賭注。
至多進行 t 個回合,問最優策略下達到目標的概率。
(t <= 300, p < 50。)

YY 了一下結論,假設當前有 m 元錢,每次壓 min(m, n-m) 就可以了。
加之題目限制很強,模擬 DP 一下就出來了。在 camp 群里遂問了一下 p >= 50 的情況下結論還成立嗎。。
果然有完整版的題目。

ゆっくり読んでください ...