某島

… : "…アッカリ~ン . .. . " .. .
April 11, 2013

Codeforces Round #178

Problem E. Shaass the Great

Brief description:

。。。給定一顆邊權樹。。你可以移動任意一條邊。。只要新圖仍然是一顆樹。。
。。。最小化。所有點對之間的距離的和。
(。。n = 5000。。。)

Analysis:

。。。枚舉每一條要移動的邊。。那麼顯然要接到這兩棵子樹的重心(所有結點到該點的距離和最小)上去。
http://codeforces.com/contest/294/submission/3501355

(。。。比賽時讀完題目就想到了重心。。然後一直試圖往並查集方面靠。。居然認為是不可做題我是多弱啊。。。
。。。雖然現在也沒搞出 O(nlogn) 演算法。。。sad。。。)

Problem D. Shaass and Painter Robot

Brief description:

..在一個 n*m 的格點上。。有一個在初始位置 (x, y)。。只會斜著走。。撞牆以後遵從反射定律的。。會把所有途徑的格子染成黑色的機器人。。。
。。。問是否能將格點染成棋盤圖案。。如果可以。問至少需要走多少步。。。
(..n,m = 10^5, 機器人初始位置一定是黑色格子。。且在邊界上。。)

Analysis:

… 因為出發點是在邊界上。(如果不是可以讓機器人先退幾步。。轉化成在邊界上的情況。。)。。容易想到一個結論。。。
。。只要所有邊界格子都被染色。。那麼所有格子就已經被染色。。。

http://codeforces.com/contest/294/submission/3500749
。。必要性顯然。。充分性可以對格子歸納得到。。有解的情況下。每個邊界格點至多進出兩次。。於是就可以當成 O(n+m) 的大模擬來寫了。。。

——————
當然和 DukeOnLargeChessBoard 相比這個實在是弱爆了。。(這題比賽時我能想出來??

Problem C. Shaass and Painter Robot

Brief description:

。。給定一個 0/1 串。。表示燈泡。。。如果一個燈泡的相鄰位置有一個亮著的那麼可以點亮它。。。
。。計數點亮所有燈的方案數。。。

Analysis:

。。。唯一在比賽時動手寫的題目。。很容易想到分解成。。0000/1111/000 … 0/1111/0000 。。。。 這樣的 0/1 段。。
。。。那麼除兩側以外 0000 每一步是要考慮從左邊進發還是從右邊進發的。。。此處的因子是 。。2^(s-1),s 表示長度。。。
。。除此之外還要乘以一個總的多項式係數。。。

。。比賽時寫了一個巨生的 Ocaml。。 而且天真的認為函數式語言會自動記憶 comb 這種遞歸函數。。。結果看了 Professor 的碼發現他是預處理二項式係數的。。。-.-。。(那我為什麼要用 Ocaml 啊。。。

http://codeforces.com/contest/294/submission/3485735
高下立判啊!。。

Postscript :

。。。blog 這個月一定要搬到 Linode 下去了。。。(。。其實上上個月就要搬了。。但是我各種不會。。。拖到現在。。每拖一個月我都要損失 9$ 要不要這樣。。。。。。
。。。解題報告部分一直想搬運到 Github 上去。。然後 markdone。。。。特別是 TC/CF/CC 這些常規賽。。。。但是一直還沒弄妥。。。。不知道要坑多久。。。
。。(。。所以現在找 TC/CF 解題報告請去看 AFAIK 吧。。。比我這邊現在要良心多了。。我這邊暫時就把 LYP 沒寫的幾篇給補上好了、、。。。

以上。。。