2011年4月26日 星期二

Topcoder SRM 504 DIV 1 Easy + Medium

題目出得不錯,也挺容易,唯獨最後15分鐘伺服器又出問題,不算rating了。Topcoder應該考慮是否調低參賽者的註冊人數,免得同類事故再發生。

Easy: 大意是有一個 $01$ 字串 $S$ 重覆 $K$ 遍,即 $S' = \underbrace{S\cdots S}_{K\text{ times}}$ 。每一回合把 $S'$ 的首個字元拿出來,如果是 $0$ 的話,則把 $S'$ 餘下的元字順序倒換。如果是 $1$ 的話則把 $S'$ 的字元取逆,即 $S'_i := 1 - S'_i$ 。問通過這個過程裡你能抽到多少個 $1$ 的字元。保証 $S'$ 最多帶 $100000$ 個字元。

做法是保留兩個指針兩個變量。指針一指首一指尾,變量決定元素取前或後和數值需否取逆。然後…就是做。或者可以用STL的deque<T>。

Medium:對於一個 $N \times M$ 的 $01$ -板塊,它依如下程序段修改其內容。

For i = 0 to N-2:
For j = 0 to M-2:
//Get the current colors of cells (i,j) and (i,j+1)
A = Grid(i,j) , B = Grid(i,j+1)

If (A,B) == (0, 0) Then:
Do nothing.
EndIf
If (A,B) == (1, 0) Then:
Mark cells (i+1,j) and (i+1,j+1) as 1.
EndIf
If (A,B) == (0, 1) Then:
Mark cells (i+1,j) and (i+1,j+1) as 0.
EndIf
if (A,B) == (1, 1) Then:
Swap the content in cells (i+1,j) and (i+1,j+1).
EndIf
EndFor
EndFor


現在有一輸出 $O$ ,問有多少個輸入可以經以上程序段後得出它。答案取模 $1000000007$ 。

留意幾件事即可。

1. 根據程序段,首行是固定的。
2. 第 $1 \le i < N$ 行的結果 $O_i$ 由 $O_{i-1}$ 來決定的,因為本來的輸入已經被程序段毀掉了。
3. 實際是求對於 $0 \le i \le N-2$ 由 $O_i$ 決定 $O_{i+1}$ 的輸入有多少種。
4. 根據程序段,操作是自左向右處理的。只要把 $O_{i+1}$ 自右至左進行逆操作,理應是要求輸入行有哪些字元可以是任意字元。假設該行有 $K$ 個任意字元,那麼結答案則可以再乘上 $2^K$ 。
5. 哪些逆操作可以決定某元素是否任意字元?留意只有 $(0, 1)$ 和 $(1, 0)$ 才會硬把兩個字元改成一種顏色,其逆操作不能判斷原來的字元。 $(1, 1)$ 的逆操作則與本來操作一樣。 $(0, 0)$ 逆操也作就是甚麼都不幹。
6. 甚麼時候是沒有解?就是進行 $(0, 1)$ 和 $(1, 0)$ 的逆操作時對兩個應修改元素的值與進行其操作後不相符。此時大可以回傳0。

2011年4月17日 星期日

Topcoder Member SRM 503 Easy

沒參加,後來補做Easy。

題意﹕問兩個整數集合 $A, B$ ,能否各自劃分成 $k$ 個離散子集,使得 $A$ 和 $B$ 的第 $i$ 子集必然使得 $A$ 的數全部少於 $B$ 的數。 $k$ 最少是多少?保証 $A, B$ 的數沒重覆。首先想到可以這樣劃分…



但無論你怎樣做,都必然存在最多 $k = 2$ 。如下圖…



甚麼時候是 $k = 1$ ?就是當 $A$ 的最大值少於 $B$ 的最小值。
甚麼時候是 $k = -1$ ?就是當 $A$ 的最大值大於 $B$ 的最大值,或 $A$ 的最小值大於 $B$ 的最小值。

Codeforces #74

上次腦殘之後,人品突然挺好的…

A: 問每個參賽者的答題的分數,成功及失敗的挑戰,問比賽的贏家是誰。保証只有一個贏家。極點頹題。

B: 捉迷藏遊戲。查票員會從火車的頭卡至尾卡不斷的來回檢查,每個時刻只會移動一個車廂。逃票人則在火車移動的時候選擇留守同一車廂,或向附近一車廂移動。如果火車停站了,他可以先行離開車廂,並能進入任意一個車廂,假設這個步驟是不看耗時的。現在給了查票員和逃票人的最初位置,和查票員的行走方向,並保証最後一個時刻是終點站,問給定每個時刻火車是到站還是行走中,逃票人能否不被查票員逮著?即使一定被逮到,最遲必定在甚麼時候被逮著?其實處理上有點麻煩的,對於火車移動的時刻,逃票人的移動有最多3個選擇,並且對查票員的前後移動跟逃票人的距離進行排序,然後往最遠距離的一點移動。如果該距離只能是0的話則會被抓。對於火車停站的時刻,逃票人永遠可以躲在查票員背對的盡頭的車廂,當然,若查票員已站在頭卡或尾卡,則必須站在該對面盡頭即可。寫的時候人品超好,一次就寫對了…

C: 問一個 $N \times M$ 的板,問有多少條不同的桌球的彈道。球的移動遵從45度的斜線運動,碰壁的話會改變方向。卡了很久沒能找到 $O(1)$ 算式…至放棄時想想不如直接寫程序計算一些數值再想想,但之前已經想到一件事﹕彈道必先會經過第一行的其中一個格子。寫的時候想到不用逐步移動,直接可以算出碰在那了。然後在第一行的起點經過剛好3次就能保証遍歷一條完整的彈道。跑的時候跟手算答案一致,無聊試試最大的情況 $N = M = 10^6$ ,竟然不消半晌就跑出答案了﹗後來猛然醒起寫的時候那個直接算出碰撞點可以讓算法變得很高效的…直接提交並通過了。早知一早放棄手寫,然後寫程序找答案還來得有效。後來看tourist的答案… $\text{gcd}(N-1, M-1)+1$ …徹底輸了。

D, E: 待補

Codeforces Round #67

本人極其腦殘的一次比賽,幸好不算rating,否則糟榚。

A: 問兩整數 $A,B$ 把零除去後,其和是否等於 $A+B$ 把零除去的值。頹。

B: 有一社交網站(名字…你懂的),有三項動作﹕(1)X在Y的留言板上留言 (+15分) (2)X在Y的貼文內留言 (+10分) (3)X讚Y的post。你知道你名字和一系列的動作,每項動作將會替X和Y添加括號內所述的分數。問對於你來說,跟你互動而分數最多至最少的的人的排序是怎樣。即使沒跟你互動都要顯示出來。我錯了幾次是因為沒看到分數是相對於自己…

C: $Q$ 次詢問,每次問區間 $[a, b]$ 內 $\text{gcd}(X, Y)$ 最大的因數。腦殘的爆發點,明明 $O(Q\sqrt{\text{gcd}(X, Y)})$ 可以搞定,我卻寫了質素因數分解,二分找答案…當然是趕急的寫,最後也過不了…

D: 有 $N$ 個小數組,現有 $M$ 個標號,把各標號對應的數組接了起來,問其最大連續子序列和最大是多少。又一腦殘點,漏了個很容易考慮到的情況。首先對每個小數組,求出其左連接最大和,數組和,及右連接最大和。那麼對每標號則考當前和加上數組和是否單調上升。若是則加上數組和並繼續,否則應先更近答案,皆因當前數值可至少加上該標號的左連接最大和使得更大但沒法再向右繼續;之後應從甚麼數開始再繼續?答案就是數組和或右連接最大和之間的最大值。但是注意,每次輸入一個新標號之後,其小數組的最大連續子序列和可能就是唯一答案,必須同時預先比對答案和其數值。我漏了處理這個,連pretest都過不了。

E: 待補。

Codeforces #73 D FreeDiv

題意﹕給了 $N$ 個點,現在接了 $M$ 條藍色邊,一個由藍色邊接成的連通塊稱作藍色領域。現在你可以添加紅色邊使得所有藍色領域都連通起來,但是有限制﹕(1)每點只能接上最多一條紅色邊。(2)每個藍色領域不能接上超過 $k$ 條紅色邊。
根據這個限制,有可能沒法添加紅色邊使得所有藍色領域都連通起來。現問至少需添加多少條藍色邊使得能達成要求?

首先,我們若把所有藍色領域縮成一點,每點標號為 $\min(k, b_i)$ ,當中 $b_i$ 為第 $i$ 個藍色領域的點數。那麼其標號即為限制讓人藍色領域最多可外接多少條紅色邊。現在問題可看成兩種操作﹕
(1) 添加藍邊連接領域 $u$ 和 $v$ 。那麼新的點 $w$ 即可看作新的藍色領域,標號為 $\min(b_u+b_v, k)$ 。
(2) 添加紅邊連接領域 $u$ 和 $v$ 。那麼新的點 $w$ 即可看作新的藍色領域,標號為 $(b_u+b_v - 2)$ 。

假定不允許操作(1)(即添加藍色邊),甚麼時候會不能滿足問題條件?明顯是存在兩個點 $u, v$ 使得 $b_u=b_v=1$ 並只能為這兩點進行操作(2)。甚麼時候可以盡量防止這情況發生?留意當 $b_u, b_v \ge 2$ 操作(2)只會製造一個新點 $w$ 使得 $b_w \ge \max(b_u, b_v)$ ,故不會導致失敗。那麼可以先為標號從大到小排序,順著標號進行操作(2)即可,只要當中有標號少於零的即當作失敗。

如果允許操作(1),怎樣可以把操作(1)的數量最少又使得條件滿足?可用二分搜索答案。假設你只允許進行操作(1) $p$ 次,你會怎樣進行操作(1)使得用上段的方法添加紅邊後條件滿足?不難留意上段說明失敗的情況只有標號為1的點太多的時候才會發生。要避免這個情況,可以考慮每次把兩個標號為1的點用操作(1)連起來,成為一個標號為 $2$ 的點。再由上段可知,它和標號大於2的點添加紅邊,不會出現失敗情況;它杏標號為1的點添加紅邊,會變成只有一個標號為1的點。故把兩兩標號為1的點用藍邊連接最能防止失敗的情況。

我寫的時候用了STL的priority_queue,結果超時(5秒都超…)。改用STL的make_heap之後剛好4.5秒通過了…另,我認為可以不用二分,直接可以算出應最少用多少次操作(1)。

2011年4月7日 星期四

Codeforces #62 D Wormhouse

題意﹕現有一個 $N$ 點的歐拉迴路的遍歷,這遍歷包含 $M$ 條邊。詢問字典序的下一個大的遍歷。可以不存在,圖亦可以不連通。 $3 \le N \le 100, 3 \le M \le 2000$ 。

做法是比較直接的。枚舉迴路的前綴,假設前綴的末點是 $u$ ,本來的下一遍歷點是 $v$ ,則在此刻嘗試找迴路的時候,嘗試的點應至少由 $v+1$ 開始。其餘時候則保持從最小標號點開始。然後直接比較路徑(如有)即可。

2011年4月6日 星期三

Codeforces #12 D Ball

問題非常簡短﹕給了 $N$ 個三維空間的點,問有多少個點 $i$ 使得存在點 $j$ 令 $x_i < x_j, y_i < y_j, z_i < z_j$ 。 $1 \le N \le 500000$ , $0 \le x_i, y_i, z_i \le 10^9$ 。

其實做法非常經典,屬練習題程度,可是我比較笨,老是想不出正確的方法。

為 $x_i$ 排序,然後把 $y_i$ 離散化。按 $x_i$ 從大至小遍歷,則問題等價於找出 $y_i < y_j$ 並且 $z_i < z_j$ 。再把問題重新看一下則是尋找 $\max_{j: y_i < y_j}\{z_j\}$ 。因 $y_i$ 已離散化則不妨把它看成位置,現求在點 $i$ 的情況下,範圍 $j \in [y_i+1, M]$ 內 $z_j$ 的最大值,當中 $M$ 是指 $y_i$ 有多少個不同的數值(即離散化後的最大值)。如此一來即是求範圍內最大值,線段樹秒殺之。

注意題目要求的是 $x_i < x_j$ 。遍歷 $x_i$ 值從大至小的時候要把相同的 $x_i$ 值暫緩更新,否則會出錯。附一樣例作例子。

3
0 0 0
0 0 1
0 0 1