某島

… : "…アッカリ~ン . .. . " .. .
October 20, 2021

AtCoder Regular Contest 128

arc 好難。。。(雖然題面都很簡單)

A Gold and Silver

著名的套利系列問題,但是這個題應該是裡面最簡單的一類,可以貪心,
掃一遍就行了。

B Balls of Three Colors

討論一下最後保留哪個,然後就很容易了。

C Max Dot

先不考慮 𝑚 的限制。。。
考慮 n=2 的情況,如果 a1 < a2 的情況,顯然資源全部都給 a2,否則只能對半分。
考慮 n 個數的情況,一定是 0 0 x x x x 這種 pattern,均分給一個後綴。
題解用的是調整法,也不難用歸納法證明,我們可以把後面的後綴合併起來看成是一個數,權值用平均值代替,
然後沿用 n=2 的方法即可。

我們枚舉後綴,得到的 x 有可能不滿足 m 的限制。
這個時候我們只要先把這些後綴填上 m,然後就可以遞歸到更短且 s 更小的問題。
這樣直接做是 O(n2) 的,可以構造一個 a 遞增的序列就可以弄出最壞複雜度。。
不過已經足夠通過本題。。。然後題解最後還說仔細觀察這個過程可以用凸包優化到 O(n),
(。。我猜是斜率 DP?。。。沒能寫出來。。)

const int N = int(5e3) + 9;

int n,m,s;
int a[N];

DB gao(int n, DB m, DB s) {
    vector<pair<DB,int>> avg; DB ss = 0;
    DWN(i, n, 0) {
        ss += a[i];
        avg.PB({ss / (n-i), i});
    }
    int t = max_element(ALL(avg))->se;
    DB x = s / (n-t);
    if (x <= m) {
        DB z = 0;
        FOR(i, t, n) z += x * a[i];
        return z;
    } else {
        DB z = 0;
        FOR(i, t, n) z += m * a[i];
        return z + gao(t, m, s-(n-t)*m);
    }
}

int main(){

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

    RD(n,m,s); REP(i,n)RD(a[i]);
    OT(gao(n,m,s));
}

D Neq Neq

看起來有點像 spoj zuma 那個題。。。不過轉移感覺不是很好想。。
首先如果是 x,y,x,y,x … 這樣的交錯序列,答案就是斐波那契數列,一旦合併之後狀態就會被分割。
那麼用類似 上次那個題 的方法,可以用 x,x 將狀態分割成獨立的子問題,最後答案用乘法原理乘起來即可。

考慮不存在相鄰元素相等的子問題,考察某個區間能否把中間的元素全部合併掉,
判定的條件是,長度 <= 3 或者這個區間有 3 種不同的元素,因為相鄰的元素不同,總是可以用第三種元素作為支點反覆消,不難用歸納法證明。

設 f[i] 表示以 i 元素結尾的方案數,有了上面的結論,就可以得到轉移方程,大概就是斐波那契關係之上再加點東西,
f[i] = f[i-1] + f[i-2] + pre,其中 pre 是所有符合上述判定的前綴和,注意別和長度 <= 3 的算重複了。
用類似 小z的襪子 里的方法維護區間不同元素的數目即可。

實現的時候,可以設置哨兵 f[0] = f[1], f[n+1] = f[n] 以簡化代碼。

const int N = int(2e5) + 9;

Int f[N]; int a[N], c[N], cn;
int n;

void add(int x) {
    x = a[x];
    if (!c[x]) ++cn;
    c[x] += 1;
}

void dec(int x) {
    x = a[x];
    c[x] -= 1;
    if (!c[x]) --cn;
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

    RD(n); REP_1(i, n) RD(a[i]);

    f[0] = 1; f[1] = 1; a[0] = a[1]; a[n+1] = a[n]; ++n;
    Int z = 1, pre = 0;

    int l = 1; REP_1(i, n) {
        if (a[i] == a[i-1]) {
            z *= f[i-1]; f[i-1] = 0; f[i] = 1;
            while (l < i) dec(l++); add(i); pre = 0;
        } else {
            add(i); while (cn > 2 && l < i-2) pre += f[l], dec(l++);
            f[i] = f[i-1] + f[i-2] + pre;
        }
    }
    cout << z << endl;
}

E K Different Values

直接 dfs 顯然不行,考慮構造。。。
(1 hour later … )

呃。。。好吧,我覺得這個題還是挺難的。囧。。完全沒看懂 題解。。。
但是 標程 到是挺容易麗潔的。。。

我們先考慮 k|n 的情況,那麼可以分成 n/k 組,我們嘗試貪心構造,每次儘可能放最小的,但是放到後面有可能需要回溯。。。
看來我們需要想一種貪心構造,使得問題的規模不斷減小,並且最好不會出現回溯。。

設 n = dk + r,(r > 0),首先如果存在 Ai > (d+1) 或者有超過 r 組 == (d+1) 那麼顯然無解 (a),
否則,如果恰好有超過 r 組 == d+1,那麼從這 r 組裡選最小的 (1),否則選全局最小的 (2),添加到隊首,
當然選出的數要保證與上次出現的距離至少為 k,然後遞歸到 n-1 即可。

上面的過程顯然保證字典序最小,我們只要證明這個演算法一定能終止即可。。
考慮反證法 + 歸納法。。

首先如果第一輪沒有出現無解的情況,那麼後面的輪次也都不會出現。。否則前面輪次的 (1) 就已經取走了。
再考慮如果某個輪次沒有取到數,那麼前 k 輪次時也一定沒有取到數,但是 <= k 輪次時一定可以取到數,
因此取不到數的情況也不存在。

F Game against Robot

非常贊的組合計數題。有早年 SRM Div1 1000 的感覺了。。。。

首先考慮靜態的問題,然後類似 linearity of expectation,我們設法求出每個 Ai 在結果中出現的次數。
我們只關注排列中每個元素和 Ai 的大小關係,這樣只需要考察 01 序列,最後對貢獻乘以 i!(n-i)! 即可。

進一步考察靜態過程,我們可以計數得到所有大於等於 Ai 的數在答案中的出現次數,類似那個證明 Catalan 數等於 \binom{2n,n} – \binom{2n, n+1} 的過程,最後預處理二項式係數的和即可。

具體得看 lyric 的代碼