Codeforces #7 C Line

問題目超短，問的是﹕給了A, B, C (-2*10^9 <= A, B, C <= -2*10^9)，問有否存在一點P在線Ax+By+C=0並且P的x-y座標均是整數，且在-5*10^18至5*10^18以內。沒有的話則輸出-1。保証A^2+B^2 > 0。

先處理special case﹕ A=0 或 B=0的情況(因A^2+B^2 > 0 所以不會出現A=B=0的情況)。直接方法就是檢查B|-C或A|-C即可。

一般的情況，即Ax+By+C=0並且|A|, |B| > 0，可以直接看成找出如下問題﹕
x = (-C-By)/A，問有否存在整數y使得x為整數。

等價問題﹕
By = -C (mod A)，求y。

注意，如果A是負數的話，則把A, B, C替換成-A, -B, -C，再解決同一問題。

記得預先把B, C取模A。剩下的就是為如下式求解﹕
Py = Q (mod A)， P = B (mod A), Q = -C (mod A)

比較經典的問題。首先，求R = gcd(A, P)。如果R|Q則有解，否則無解。
有解的話，則把P, Q, A換成S = P/R, T = Q/R, U = A/R，再解如下式﹕
Sy = T (mod U)
因為S, U互質，則可以用擴展歐幾里特算法，找到S^-1。
y = TS^-1 (mod U)

然後可以直接用y求x。問題是﹕x, y的值會否分別超出題目要求的上限？注意﹕求出的y是模U的，而U則是取值[-2*10^9, 2*10^9]，因此x = (-C-By)/A 取值[-4*10^18-2*10^9, 4*10^18+2*10^9]，不會超出上限。

Codeforces #37 C Old Berland Language

題意非常簡單﹕給了L1, L2, ... LN，1 <= Li <= 1000, 1 <= N <= 1000，問有沒有N個prefix-free binary code使得長度符合所有Li。

想了良久，沒有好的辦法，結果Google了一下，知道Huffman Coding保証給出所有符號都是Prefix-free的，但顯然對此題沒有幫助。但間接的想法是﹕建立一棵類似這樣的二叉樹，每個Li對應建立二叉樹中一個長度為Li的Leaf Node。有了這個想法之後就是順著這個方法建立二叉樹，萬一不能建立Leaf Node的話，則代表所有Prefix-free code用盡。注意的是必須按遞增長度插入Leaf Node。然後順輸入的次序輸出相對應的字串。

Codeforces #46 C Disposition

題意是﹕給出一個1..N的排列，設G = {i: 1 <= i <= N，令存在第j位(1<=j<=N)同時滿足i|j和i|A[j]}，把|G|最小化。

大約觀察所得﹕
1. |G| >= 1。
2. 第i位必不能放i的因子。

猜想﹕
1. 必然存在排列使得|G| = 1。

重要觀察﹕
1. i和i+1必然是互質，即gcd(i, i+1) = 1。
2. 把奇數置於偶數位，把偶數置於奇數位，G = {1}。

故我們可以考慮位置i放i+1，i+1放i，當中i為奇數，並使得只有G={1}。
但需注意若N是奇數的話，第N位只能放N，會使得G={1,N}。但不難發現同樣的方法也適用於i為偶數，因為若第一位放置一，無損G={1}的特質，但可以保証重要觀察的正確性。

故答案如下：

N是奇數：1 3 2 5 4 7 6 9 8 ... N N-1
N是偶數：2 1 4 3 6 5 8 7 ... N N-1

Codeforces #51 C Pie or Die

題意是﹕給出一個N x M的棋盤，現有K個黑色的棋子(位置可以重覆)。每一回合可以選一個棋子向四個方向移動，然後對方會把棋盤的一條邊封掉。當玩家可以推一個棋子越過一條未封掉的邊為勝。問雙方用最優策略下，玩家能否勝出。

最初有幾個想法﹕
1. 永遠只選同一個棋子去移動。
2. 可移動回合有限，為2N+2M。
3. 最終棋子的終點是棋盤的任意一個角(直觀想的是這些格子需要封兩次才能防止棋子勝出)
4. 3x3的棋盤任意棋子必勝，故推測存在棋子距離邊的步數最少者少於3為必勝。

但畫出5x5的棋盤想了想也覺得任意棋子也可以勝出，但沒法証明，又不知是否有更大的可能…
故看了題解，答案果然是以棋子最少距離步少於5為勝。証明的方法還是很巧妙的。

只要到達最近的邊的距離至少是5步的話，那麼首四步會把棋盤上屬於那條邊的兩個角落的邊都封掉(總共剛好四條邊)，那麼在第五步的話最快會扺達其中一條邊，那麼只需要封住該邊，之後無論那棋子怎樣移動都把那最近的邊封掉，結論是必然是輸局。

下次一定要好好想想再拓展的情況…

Codeforces #28 B pSort

題意﹕給出一數組A[1..N]，並且A[i] = i，規定A[i]能和A[j]交換數值若且僅若|i-j| = d_i。問能否通過不限次數的交換使得最初的數組A變成目標的排列。

想了一會，其實方法也是挺簡單的﹕定義交換集G = {g_i} 使得A[g_i]能和A[g_j]交換數值。
關鍵是﹕交換集裡的元素可以組成任意排列。例如G = {1, 3, 5, 6}而數組是
1 ? 3 ? 5 6 ? ? ?
我們可以任意排列1, 3, 5, 6的位置，即可以排列成(舉例)
3 ? 5 ? 1 6 ? ? ?

因此，答案是顯然易見的﹕對於目標排列B, 該排列能夠達成若且僅若B[i]和i是屬於同一交換集G之中。

建立交換集的方法有很多，我的方法是用並查集。

Codeforces #24 C Sequence of Points

題意是﹕給出二維點M0, A0...A(N-1), 任意Mi (i > 0) 都使得A_((i-1)%N)為Mi及M(i-1)的中點。
問Mj是甚麼，N<=10^5保証是奇數，j <= 10^18。

驟看很複雜，但不妨先重溫中點公式﹕

定理（中點公式）﹕對於兩點A及B，C是兩點的中點若且僅若C=(A+B)/2，這公式皆把三點都看成向量計算。

因此，題意說的是知道(Mi+M(i-1))/2=A((i-1)%N)，問Mj是甚麼。
把公式重寫，得出 Mi = 2A((i-1)%N) - M(i-1) 這道遞迴式。
因為取模使式子變得難分析，故先取i < N的情況。依推導，可得﹕
M0 = M0
M1 = 2A0 - M0
M2 = 2A1 - M1 = 2A1 - 2A0 + M0
M3 = 2A2 - M2 = 2A2 - 2A1 + 2A0 - M0
.
.
M(N-1) = 2A(N-2) - M0 = 2A(N-2) - 2A(N-1) + ... - 2A0 + M0
MN = 2A(N-1) - M(N-1) = 2A(N-1) - 2A(N-2) + ... + 2A0 - M0
好像沒有甚麼有用的資訊。但加入取模的情況下就有點頭緒了，且看M(N+1)﹕
M(N+1) = 2A(N%N) - MN = 2A0 - 2A(N-1) + 2A(N-2) - ... - 2A0 + M0 = - 2A(N-1) + 2A(N-2) - ... + M0

A0被抵銷了。同一道理，A0和A1也會在M(N+2)被抵銷。因此可以推導出A0, A1, ... A(N-1) 會在M(N+N)被抵銷。因此可知M(2N)數值上是和M0一樣，但會不會是-M0呢？留意上述推導的式子中，只有奇數項才會出現-M0，而2N是偶數，因此M(2N) = M0。

因此可以肯定M0...M(2N-1)是數列的循環部分，所以只需預計算M0...M(2N-1)，然後直接取M(K%2N)即可。

Codeforces #33 C Wonderful Randomized Sum

題目簡單，問的是給出一個整數陣列A，取任意一前綴各項乘-1，取任意一後綴各項乘一，問兩個操作後A的所有元素和最大是多少？前後綴長度可以為零。

我花了點時間還是做不到，故看了某blog的解題，其實方法也是用如前幾篇文章所述的Relax法去解題。

Relax﹕如果只允許取前綴的話，那麼最大和是多少？

答案是比較簡單的，只需計算 max{Sum[1..N] - 2 * Sum[1..i], Sum[1..N]}即可，注意第二個參數是代表不取任何前綴之和。留意該公式只有Sum[1..i]是有變化的，故可重寫成Sum[0..N] - min{Sum[0..i]}, 當中設A[0] = 0。故只需O(N)預計算Sum[0..i]，後取k令Sum[0..k]最小者即可。答案即 Sum[0..N] - 2 * Sum[0..k]。

那麼對於A的長度為N的答案我們可以用P[N]來紀錄，即P[N] = i。

Observation 1﹕ P[i] <= P[i+1]。
這是我們取P[N]的時候的by-product而已，同樣可以看作把Relax問題放到A[1..i]然後取P[i]。

Observation 2﹕ 把Relax問題放到A[1..i]，答案P[i]始終固定。

因此我們可以直接計算max{Sum[0..i] - 2 * Sum[0..P[i]] - Sum[i+1..N+1]}，當中設A[N+1] = 0，即可。