某島

… : "…アッカリ~ン . .. . " .. .
September 11, 2012

CodeChef September Challenge 2012

8.03 / 10 …

。。。似乎本月題目的整體質量有所下降?。。。。
不過 Knight Moving && Annual Parade 對我來說還是十分困難。。)
(某種程度上說 Knight Moving 對我來說更加困難。。。

Level 1:

Racing Horses:
簽到題,略。

Kisses & Hugs: 數列
開始錯推成 http://oeis.org/A002620
。。。後來發現題目讀的不對。。所以應該是這個。。http://oeis.org/A027383

Three is Crowd: 數列。。
http://oeis.org/A050231
取補集後得到 Tribonacci。。之後矩陣乘。。

Chef World:數列。。。。
先寫了個暴力。。。http://paste.ubuntu.com/1185570/
F[n] = 0, 5, 18, 44, 96, 195, 380, 719, 1332 ..
發現 OEIS 裡面沒有記載。。。。。。
手推後得到…一個四階線性遞推數列。。(常數注意。。
(常數優化兩處。。一個是矩陣乘法裡面。另一個是先預處理出所有 A 的 k 次冪。。

ChefTown Parade: 給定一個排列,問其中連續 k 項排序後恰好布滿一個長度為 k 的區間的區間數。。
。。注意 nlogn 的演算法會 TLE 。稍作整理後可以得到一個基於單調隊列的演算法。

Queries About Numbers: 數論。。
。第二問和第三問是對稱的。。因式分解即可。。

Lights:。。寫了一個暴力二分。。居然過了。(求更好演算法。。。

Level 2:

Annual Parade:
給定一副有向圖,每條邊有一個權值,要求用若干個路徑和環對圖進行覆蓋,每條邊可以使用任意多次。。
沒有覆蓋的點產生額外的 C 代價,如果是路徑則也要產生額外的 C 代價進行返回。。
現在共 T 組詢問,對每組詢問不同的 C 值。。返回最小代價。
——————
感到這裡的 C 很不自然,第一印象是最大權閉合子圖,於是開始嘗試網路流建模,不過似乎無法解決每條邊可以使用任意多次的問題。。
。。只要對原圖求傳遞閉包後,問題就轉換成了哈密頓圈覆蓋,對於不存在的邊,用 C 賦值上即可。

。對哈密頓圈覆蓋。使用 KM 的話。。至此就得到了 O(Tn3) 的演算法。。。
之後考慮不同 C 之間的冗餘。。。那麼如果對詢問進行排序,如果當前某對匹配的權值是 C,那麼對於更大的 C。。一定也是這組匹配。。
於是對詢問離線處理。。仍然得到了 O(Tn3)。。但是 n 的規模會逐漸減小。。。

但是仍然各種 TLE 。。。
賽後對 CLJ 的代碼 使用了初級鷹眼術。。。

發現我這一步誤區了。。(。。。我這裡似乎一直認為對於二分圖最有匹配問題。。用特定的 KM 演算法總是比費用流來的有效。
。但是這題里使用費用流可以逐步推流。。從而在不同的詢問之間得到很自然的優化。。。

Knight Moving:
給定兩組步長,(AX, AY), (BX, BY),問從 (0, 0) 開始出發到 (n, m) 結束。。
。有多少種不同的移動方案。。(無解或者無窮解或者有限解。。。
——————————————————
不同的移動方案定義為某一步所到達的格子不同。。。所以對於 AX == BX && AY == BY 的情況要單獨處理。。。
。。除此之外還有各種各樣的情況。。總之此題遠比其看起來要複雜。。> <。

附加題:

Simultaneous Nim:
。。給定一組亦或和為 0 的數。。要求分割出儘可能多的組。。
使得每組內的亦或和同樣為 0 .。。
——————————
寫個暴力判斷相同位置就能得到 0.03 分。。。
(。。ACRush 從第二天就開始狂刷這道題。。。而且我前面的題目沒做完 。完全沒動力做附加題啊。。。。
。。。後來最後幾個小時實在沒辦法。。又回到這個題。。想了一個演算法。。根據數字的最高為進行分組。。
然後從高組向下遞降。。列印最高位為 0 (也就是亦或和為 0 )的所有組合。。。不過最後當然是沒調出來啦。
。。。。。

External link:

http://www.codechef.com/SEP12/