某島

… : "…アッカリ~ン . .. . " .. .
August 12, 2013

CodeChef August Challenge 2013

Level 2. Sereja and Ballons

首先。。。用鏈表維護每個格子
當某個格子減到0的時候,查詢它的 prev[x],和 succ[x]
記作 a, b。。那麼這一輪被刪除的區間 (l, r) 滿足
l 屬於 (a, x]
r 屬於 [x, b)

於是就變成了詢問一個子矩形點的個數的問題。
。。。這裡我們用函數式線段樹
查詢一個子矩形就是。。。
T[x].Query(b-1, x) - T[a].Query(b-1, x)

Level 2. Music & Lyrics

裸 AC 自動機爆過去了。。。求更好做法。。。

Level 2. Prime Distance On Tree

點分治 + FFT

Level 2. Deleting numbers

主策略。。。

Stage 1. Naive

1. 從後往前逐個刪除。
2. 保留出現次數最多的那個。。其他從後往前逐個個刪除。。

Stage 2. 樹狀數組

從後往前逐個刪除。但是嘗試枚舉步長。_L1。取刪除個數最多的。。。。
這個演算法需要維護刪除後的序列。。初期使用的是 STL::vector 。。
但是 erase 畢竟是暴力的。。。所以要想更進一步。。。必須設計數據結構。。。

http://www.codechef.com/viewplaintext/2479887

為了控制常數。。我們排除一些較為複雜的樹形結構。。比如各種平衡樹。。
果然還是要樹狀數組。!。。。這樣當我們引用元素 i 的時候。。那麼它當前真實的位置就是 i – Sum(i)。。
。。這個數據結構。。可以幫助我們確定元素的位置(Rank)。。。但是無法直接告訴我們當前位置為 i 的元素是多少(Pos)

http://www.codechef.com/viewsolution/2520960

Stage 3. 緩存

上述演算法的瓶頸在於就在於多次樹狀數組的查詢的操作。。。
。。我們發現在處理與末尾數字相同的時候。。。很多 Rank 的結果是可以重複利用的。。我們對這個結果做 Cache。。
。。。這樣一定程度上也可以 O(1) 時間得到 Pos。。。

。。針對這個特性。。。於是我們重新設計演算法的框架。。添加兩個邏輯層。。。使得我們不是每次都必須要要刪除最後一個數字。。

中間一層。。。刪除的最後一個數字。。可以是與最後一個數字相同的步長 _M1 以內的任何一個數字。。
最外xxxx。。。xxxxxxxxxxxxxxxxxx。。xxxxxxxxxxxxxxxxxxxx不同xxxxxx _D0 以內的任何一個數字。
最外層的策略使用次數不能太多。。。還得設置一個參數 _C0。。。

http://www.codechef.com/viewsolution/2521453

。。用到的其他優化。。

  1. 開始就把孤立元素刪除。。。(這個優化在 vector 時期效果有限。。但是後期效果越來越明顯。。。。
  2. 在演算法的任意時刻。。若出現孤立元素。立即刪除。。。(。。這個優化的作用也很明顯。。
  3. . 。。開始和中間時刻。。某個元素只剩 2 個的時候。。也嘗試直接清除。。。(。。效果並不明顯。。有時不增反減。。。

我們看到其實孤立點並不一定總是直接刪除更好。。有的時候保留一些孤立點。。可以令我們中間的過程更具有機動性。。。但是如何利用這種機動性。。卻沒有什麼好的方法。。
。。乾脆棄掉算了。。。。

External link:

http://www.codechef.com/AUG13/