某島

… : "…アッカリ~ン . .. . " .. .
June 6, 2013

Google Code Jam 2013 Round 2

Problem A. Ticket Swapping

Brief description:

… 給定一個直線形的地鐵站,一共 n 站,只能向一個方向移動。。每一站單站價格是從 n 開始每次減 1。
。。bug 是這個系統可以通過在站內交換車票來達到 cheat 的效果。。
。。給定 m 個請求 l, r, p 表示從 l 發出 p 個客流倒 r。
。。問整個系統最多會損失多少¥。。。
( n <= 1e9, m <= 1e3 .. )

Analysis:

。。直接把每個請求拆成一個入事件一個出事件混在一起排序 O(mlogm)。。之後接一個棧掃一遍就行了。。O(m)。。

...
        stack<event> S; REP(i, 2*m){
            if (E[i].p > 0) S.push(E[i]);
            else {
                while (E[i].p){
                    int d = min(S.top().p, -E[i].p);
                    res -= f(E[i].x - S.top().x) * d;
                    E[i].p += d, S.top().p -= d;
                    if (!S.top().p) S.pop();
                }
            }
        }

參考代碼。。
。。比賽時候的話。。最好像 Tourist 一樣直接爆 O(m^2) 的。。。

Problem B. Many Prizes

Brief description:

… 2^n 個人進行 n 輪淘汰賽。問:
。。一定進前 p 名的人有多少個。。。。
。。可以進前 p 名的人有多少個。。

Analysis:

。f1(n, p) n 個人里有多少人一定排前 p 名。
。f2(n, p) n 個人里有多少人可能排前 p 名。

。。似乎沒有二分答案以外的方法,設
。ff1(n, p) n 個人里排名為 p 的人,的 最壞 排名。
。ff2(n, p) n 個人里排名為 p 的人,的 最好 排名。
考慮 ff1 情況。。這個顯然可以遞歸。。
。。每一次都要儘可能進入敗者組。。
。。同時。。要儘可能多的讓高名次的玩家也進入敗者組。
。。方法是配對。。同時預留出一個可以擊敗當前玩家的。
ff2 的情況類似,不過是讓名次低的進行配對以儘可能多的進入勝者組。

...
LL ff1(LL n, LL x){
    if (!x) return 0; // 無法進入敗者組
    return n/2 + ff1(n/2, (x-1)/2);
}
..
LL ff2(LL n, LL x){
    if (x == n-1) return x; // 無法進入勝者組
    return ff2(n/2, n/2-((n-x))/2);
}

Note:
看了題解後。。發現其實兩個問題是緊密聯繫的。。

Let’s begin by an observation that will make our life a bit easier: if we reverse all the team numbers (that is, team 0 becomes team 2^N-1, team 1 becomes team 2^N-2, etc.), without changing the tournament list. This will result in the final ranks of the teams also being reversed, since it’s relatively easy to see that all the records will be reversed (wins becoming losses and vice versa). This means that the problem of having a team rank as low as possible to get into the first P is equivalent to the problem of a team ranked as high as possible to get into the bottom P (or, in other words, not get into the top 2^N – P). Thus, if we are able to answer the question what is the lowest rank that can possibly get into the top P, we can run the same code to see what’s the lowest rank that can possibly be in the top 2^N – P, subtract one, and reverse, and this will be the lowest rank that will always get a prize. This means we only have to solve one problem — lowest ranked team guaranteed to be in the top P .. .

。。。通過這個關係。。。解出任意一個就行了(主要此時需要加額外的一組邊界條件)。。Orz。。。
。。。並且。。明顯問題2 其實更容易些。。。

參考代碼。。

Problem C. Erdős–Szekeres

Brief description:

Analysis:

… 差分約束後不能保證沒有重複數字。。因此還要執行一遍 dfs()。。。
。。。但實際上直接 dfs() 就行了。。)

D. Multiplayer Pong

External link:

Google Codejam Round 2 && POJ Challange Beta 1 by lyp .. .