Codeforces #15 C Industrial Nim

題目就是跟一般Nim沒甚麼分別，不過本題可以有龐大數量的石子堆。
設有N個大堆，第i個大堆有M[i]個石子堆，每石子堆的石子數量是X[i], X[i]+1, ... X[i]+M[i]-1。
現在兩個大在這N個大堆取石子，問誰會勝出。

不難發現的是答案取決於XOR{XOR{X[i]+j: 0 <= j < M[i]} : 1 <= i <= N}。但X[i]和M[i]都可以是10^16，因此不能直接用枚舉的方法。定義P(N) = XOR{i: 0 <= i <= N}，XOR{X[i]+j: 0 <= j < M[i]}則等價於P[X[i]+M[i]-1] XOR P[X[i]-1]。則每大堆可以O(1)算出Nim-sum。而P[N]則是容易算出的﹕

P[N] = 0 if N = 0 or N%4 = 3
     = N if N % 4 = 0
     = N | 3 if N % 4 = 2
     = 1 otherwise

算法複雜度是O(N)。

Codeforces #13 C Sequence

問題是﹕給了一個長度為N的整數數列A，1 <= N <= 5000，每次操作可以把數列內任意一個數+1或-1，求最少操作使得該數列是單調遞增的。

試了一次貪心的方法，結果不行。後來轉為動態規劃。

Observation 1: 目標數列只會取值原本數列內的數。即數列A內含{1, 3, 5, 7, 8}，那麼經最少操作後的數列都只包含{1, 3, 5, 7, 8}的子集。

有了這樣的想法之後，簡單的動態規劃轉移方程可以這樣寫﹕
定義﹕
F(i, j): 把數列內首i個數用最少操作，成為單調遞增序列的操作數量，且第i位數取值B[j]。
B: 把數列A按遞增排序。

F(0, j) = |A[0] - B[j]|
F(i, j) = min{F(i-1, k) + |A[i]-B[j]| | 1 <= k < j} = min{F(i-1, k): 1<=k < j} + |A[i]-B[j]|

由於計算F(i, j)時順道update min{F(i-1, k): 1<=k < j}，因此整個算法是O(N^2)。留意N最多5000而Memory只有64MB，需要用到滾動數組。

SRM 497 Div 1 Easy Permutation Signature

今次打開題目，從看懂到想出算法都很快，五分鐘內搞定。

題意﹕給了一個長度為N的字串S，而S只包含字元「I」或者「D」。請構造出一個1..N+1的排列P，使得如下條件成立。

1) S[i] = 'D': P[i] > P[i+1]
2) S[i] = 'I': P[i] < P[i+1]

P需要是lexicographically smallest。
若不存在則返回一個空的數組。

首先，大膽假設答案必然存在。快速瞄了一下example，好的，沒有No solution，猜想應該是對的。怎樣構建？
在紙筆寫了題目描述的樣例﹕

1 2 3 4 5 6 7
 D I I D I D

一開始的P必然滿足S[i] = 'I'。不滿足S[i] = 'D'的可以通過交換達成，即﹕

2 1 3 5 4 7 6
 D I I D I D

即是樣例答案。交換後仍無損S[i]='I'的特性，因為與通過交通的群組必然少於因為S[i]='I'而需要比對的數。亦因此推斷這樣的P是lexicographically smallest的。但，慢著，連續幾個的S[i]='D'怎辦？即時寫了另一組例子﹕

1 2 3 4 5 6
 D D I D D

答案明顯不過了–對於連續的'D'所涉及的數字，反轉就行。這也是因為需要符合DD..D的特性，亦根據之前的推論，這個答案仍是lexicographically smallest的。因此上述例子的答案如下﹕

3 2 1 6 5 4
 D D I D D

算法也是極其簡單的，只需先構建P[i] = i+1, 0<=i<=N，然後對於每一連續的'D'把其範圍內的數字反轉次序即成。

Codeforces #10 C Digital Roots

題意﹕定義d(x)為不斷把x的數位取和直至變成個位數為止，例d(199) = d(19) = d(10) = d(1) = 1。給了N，問有多少組(A, B, C)使得1 <= A,B,C <= N，d(d(A)d(B)) = d(C) 但 AB != C。1 <= N <= 10^6。

想了一整天終於AC，方法沒有Petr他們簡單，在這裡說說我的方法。

Observation 1: 若x, y也沒有限制數值，d(d(x)d(y)) = d(xy)。

Observation 2: 對於固定的d(x)，d(d(x)d(y))的值是循環的。因為d(x) = (x-1)%9 + 1，d(x)d(y)即把d(x)向前移d(y)步。又，因為函數d取值在1~9之間，所以會出現循環。

設
A[k] = |{k: 1 <= k <= 9, there exists i, j such that i*j<10 and d(i*j)=k }|
B[k] = |{k: 1 <= k <= 9, there exists i, j such that 10 <= i*j <= N and d(i*j)=k }|
A, B均可以在O(N)內算出。

簡單地想，答案是這樣的﹕
枚舉所有i, j﹕
(1) 如果i*j < 10, 則(i, j, C)的解有B[d(i*j)]個。這是因為B的是d(x*y)的個數，而且x*y > 9，所以B[d(i*j)]的個數均不可能包含i*j。
(2) 如果i*j >= 10，就有點麻煩。首先，符合的解至少有A[d(i*j)]個，原因與(1)相同。但對於B[d(i*j)]，則再細分以下情況﹕
(i) 10 <= i*j <= N，B[d(i*j)]包含了i*j，則需要加上B[d(i*j)]-1，即此情況的(i, j, C)個數有A[d(i*j)]+B[d(i*j)]-1個;
(ii) i*j > N，B[d(i*j)]不包含了i*j，因此加上B[d(i*j)]就可以了，即(i, j, C)的個數有A[d(i*j)]+B[d(i*j)]個。

Observation 1保証了d(d(i)d(j))和d(i*j)相等，所以簡單地用d(i*j)表示就可以了。

這樣枚舉的話複雜度是O(N^2)的，保証過不了。但記得Observation 2說的是，對於固定的i，d(i*j)是一個循環序列。例﹕
i = 2， d(i*j) = {2, 4, 6, 8, 1, 3, 5, 7, 9, 2, 4, 6, 8, 1, 3, 5, 7, 9, ...}
i = 3， d(i*j) = {3, 6, 9, 3, 6, 9, 3, 6, 9, ...}

換角度想，如果對於固定的i，枚舉j的時候條件(1)始終成立，這樣會重覆計算B[d(i*j)]很多次。想避免重覆計算可以先預計算固定d(i)的Partial Sum, SumB[d(i)][0..9]， SumB[d(i)][0] = 0，SumB[d(i)][j] = SumB[d(i)][j-1] + B[d(i*j)]。這樣一來可以直接O(1)取(N/9)*SumB[d(i)][9] + SumB[d(i)][N%9]。同樣的分析可以應用到case (2)(ii)，即預計算SumA[d(i)][0..9]。
但你會發現兩個問題﹕
(a) case (2)(i) 不是很直接的算 SumB[d(i)] - 常數，因為某些B[d(i*j)]根本是0的，硬是減1會出現負數。
(b) 對於固定的i，可以存在[1..j]是case (1)，[j+1..k]是case (2)(i)，[k+1..N]是case (2)(ii)的情況。

對於(a)，只需另開SumC[d(i)][0..9]即可，唯與SumB一不同的是SumC[d(i)][0] = 0，SumC[d(i)][j] = SumC[d(i)][j-1] + max(0, B[d(i*j)]-1)。

對於(b)，顯然j = 9/i，k = N/i。然後用類似如下公式即可﹕ (例如取k+1...N的值)

(N/9)*SumA[d(i)][9] + SumA[d(i)][N%9] - (k/9)*SumA[d(i)][9] + SumA[d(i)][k%9]

然後應用到三段分切的情況。

預計算SumA, SumB和SumC都是O(1)的，對於固定的i計算(i, j, C)的個數均是O(1)的，因此整個算法是O(N)。

Codeforces #27 C Unordered Sequence

題意﹕給了N個數A1, A2... AN，一個有序數列是指數列是單調遞升或者遞降，求A之中最短的非有序子序列。可以無解。

看了也想了很久，誤解以為找了這個最短的非有序子序列之後剩下的序列必須是有序的…但其實不是，題目實實在在的只想你求一條最短的非有序子序列。

發現之後此題巨簡單﹕若有解，則該序列的長度永遠等於3。即找i, j, k使得 i < j < k 並且 Ai < Aj, Aj > Ak 或 Ai > Aj, Aj < Ak。

做法巨簡單﹕O(N)求 LeftMin[i], LeftMax[i], RightMin[i], RightMax[i]，分別是指A[1..(i-1)]和A[i+1..N]最小最大的位置。

又一次腦便秘，下次看題要看清。

Codeforces #19 B Checkout Assistant

題意﹕給了N個東西的價格ci及其抵銷值ti，其中抵銷值ti是指你可以買下物品i的同時讓ti件未付款的物品免費。問最少要付多少錢才能把所有東西都買下？

想了很久，也試了很多貪心的方法，都是錯的。然後猛然醒起…只需把所有ti+1，問題就是﹕取物件的抵銷值和>=N，而總價格最少。如此一來就是0-1背包問題了。

今次做這道題比較腦便秘…下次不可再大意。

Codeforces #30 C Shooting Gallery

問題是﹕給了所有物體的出現座標，時間，和能夠打中的概率，問最大打中物件的期望值是多少，每次1時間單位能移動距離剛好為1。

直觀的DP，應用線性期望值應不難發現就是找一個物件的序列使得相鄰物件的時間間隔少於等於其實際距離，然後把它們的概率和最大化。

錯了幾次，發現寫比較函數犯了一個低級錯誤﹕

bool operator<(const obj &A, const obj & B)const{
if (A.time != B.time) return A.time < B.time;
}

最初以為除了時間的比較外還要做second key ordering，後來發現只需比較時間即可，故留著沒改。
但對於時間相同的obj會胡亂回傳1或0的，因此對quick sort partition會有錯誤。
把if條件移去即可。