SRM652

因為 250pt 的 Sample壞掉了而 unrated，已經連續兩場 unrated 了，總覺得最近 Topcoder 諸事不順。

這場我也是先開了 1000 pt 的題目看，試了一陣後發現比賽結束前大概無望弄出來，就回去看250 pt 和 500 pt 的題目，這時只剩 20 分鐘，迅速寫完 250 pt 後，500 pt 一看就知道大概怎麼做了，只是沒有時間把細節弄清楚和寫完 (這題很重邏輯推理，實際上大概還差個至少 20 分鐘的時間吧...) 看來要寫完 250 pt 和 500 pt，至少要保留 40 分鐘比較穩定。

250 --- ThePermutationGame

題意：Alice 和 Bob 玩一個遊戲如下，Bob 可以決定一個前 $N$ 個自然數的 permutation function $P$ (意即 $P$ 的 定義域即值域都是前 $N$ 個自然數，並且為一對一且映成的函數)。而 Alice 可以決定一個數 $x$，Alice 決定的數必須使得無論 Bob 決定的函數為何，把 $1$ 迭代這個函數 $x$ 次後仍是 $1$(意即 $P(P(...P(1)))=1$，共 $x$ 個 $P$)，給定 $N$ 請問 $x$ 最小是多少？(答案 mod $10^9 + 7$)

數據範圍：$1 \leq N \leq 100,000$。

tag：[ 數學 ]

= = = = = = = = = = = = = = =

我讀完題目後瞬間就把題目理解成是求前 $N$ 個自然數的最小公倍數了，因為對於同一個數 $i$ ，令 $i$ 迭代 $P$  $x$ 次的結果是 $a_x$，則 $a_x$ 一定是從頭開始循環的，而且循換節長度 $1 \sim N$ 都有可能，$a_x$ 要變回 $i$，$x$ 必須是循環節長度的倍數。

至於要怎麼求 $1 \sim N$ 的最小公倍數呢？我的方法是直接求出所有質數在 $1 \sim N$ 裡出現的最高次數，就可以推到答案了。

根據你的寫法，可能有些變數必須開 $64$-bit 整數，我成功的 challenge 一份該開 $64$-bit的地方只開 $32$-bit 的 code。我時常在想 ... 為什麼不要萬物都 $64$-bit？一直有人因為這種蠢 bug WA真令人感到難過。

500 --- MaliciousPath

題意：Alice 和 Bob 在有向圗 $G$ 上玩一個遊戲如下：最初 Alice 在編號為 $1$ 的點，每一輪，Alice 可以選定一個可走的邊，並走過去，目標是走到編號為 $N$ 的點，每個邊都有對應的 cost。而 Bob 有 $K$ 個 Token，每ㄧ輪 Alice 決定要走哪條邊後，Bob 都可以決定要不要使用 Token，使用的話就可以強制改變 Alice 這輪要走的邊。Alice的目標是希望到達點 $N$ 所需的 cost 總和盡量少，而 Bob 則希望盡量多。請回傳兩人都使用最佳策略時的 cost 總和值，若 Bob 有辦法讓 Alice 永遠走不到終點，則回傳 $-1$。

數據範圍：$2 \leq N \leq N$，邊數不超過 $2500$，每條邊 cost 介於 $0 \sim 1,000,000$，$0 \leq K \leq 1,000$。

tag：[ 最短路 ]

= = = = = = = = = = = = = = =

看完題目和數據範圍後，大概就知道是最短路的變形題了，但細節嘛... 我沒辦法馬上想清楚 OAQ第一名只花了 $10$ 分鐘 AC 了好厲害 0.0而且它 code 超短。

首先想想 $K$ 是 $0$ 時會發生什麼事，毫無疑問就是個單純的點 $1$ 到點 $N$ 的最短路吧？接下來若 $K$ 是 $1$ 呢？基本上我們可以相信，若會做 $K$ 是 $1$ 的情況，就幾乎等於解決這題了因為感覺起來從$K = i-1$ 推到 $K = i$ 的方法，無論 $i$ 是多少都是一樣的。

令 $dp[k][x]$ 代表 Bob 還剩 $k$ 個 Token 並且 Alice 在點 $x$ 時的答案，另外我們也可推論，當 Bob 要使用 Token時，一定會選擇所選的邊 $(x, y)$ ，使得此邊的 cost 加 $dp[k-1][y]$ 值最大，我們令這個值為 $g[k][x]$。

根據 Alice和 Bob 的策略，我們可以列出以下關係式：

$dp[k][x] = \min_y{ \max (g[k][x], cost[x][y]+dp[k][y])}$ (若 $x$ 沒有指向 $y$的邊，cost[x][y]視為無限大)

但麻煩的是這個關係式並沒有特定的順序可以好好 dp，但有沒有發現這個關係式其實和某個東西很像呢？嗯...基本上就只是最短路的關係式多包一個 $\max (g[k][x], *)$，於是我們何不試著用類似 dijkstra 的方法去解決它？根據這個關係式，我們要把邊反向，並且改成用點 $N$ 當做起點。若你有猜到這一步，那基本上就可以 AC 這題了(可參考我附的 code 連結)。但我們不要滿足於此 >_< 來繼續證明它是對的。

證明的方法其實也和 dijkstra 的證明差不多，重點在於，關係是裡 $\max (g[k][x], *)$ 這部分只會使最短路的值更大而不會更小，確認了這點後就可以完全套入 dijkstra 的證明了。請不要嫌棄我這樣的解釋太單薄 >_<

1000 --- NoRightTurn

題意：平面上有 $N$ 個點，並且任三點不共線，給定起點後，我們要走訪所有的點，兩點之間必須走直線，且過程中不能右轉，只能在有點的地方轉彎，以及所走出的 polyline 不能和自己嚴格相交，請回答每個點當做起點有多少種走法。答案要 mod $10^9 + 7$

數據範圍：1 \leq N \leq 100，座標的絕對值不超過 $1,000$。

tag：[ 計算幾何 ][ 凸包 ][ 構造 ]

= = = = = = = = = = = = = = =
這題在比賽間，我只猜到答案很小，於是我想要模擬以及判別當前還能不能繼續走下去來搜索答案數，只是我想了一些判別方法都想錯了 @@。後來看了  Codeforces 的討論串，發現我方向大至正確，但這題的結論比我想像的還要強，比起搜索這個字眼，用構造應該會比較貼切。而且考慮任意點當起點的 polyline 總數只與 $N$ 和凸包上的點數有關。又或者說，沒有想到凸包的話，這題根本很難想下去 (我在賽中我全沒有想到凸包這回事 @@)

先看看這張圖：

藍色的點是凸包上的點，紅點則是其餘的點，多畫幾張你就會發現，凸包上的點在 polyline 裡是連續的！再來你會發現第二件事：總是可以畫出ㄧ條直線把 polyline 上被把藍點隔開的兩群紅點，也用一條直線隔開且線會通過凸包開口 (如圖中的紫色直線)。最後，還有一件事：若決定好凸包上的開口以及裡面紅點分兩群的方法，那將只有唯一一種畫 polyline 的方法！

以上所述的證明就略過吧＠＠應該沒有很難？

把這些事實當做已知後，就會發現解題的重點要放在如何找到開口以及如何枚舉所有的紅點分兩群。

先思考一個相對簡單的問題：平面上有 $N$ 個點，任三點不共線，要把這些點完整分成兩群，每群都至少一個點，使得可以用一條直線把這兩群分開，共有幾種分兩群的方法？

手動畫一些 $N$ 比較小的case後，應該就會猜到答案是 $C^N_2$ 了。雖然容易猜得到答案，但如果要你把所有分法都列出來呢？那只好來好好的構造答案了。

對於每種粉兩群的方法，我們種是能把分隔兩群的直線一直順時鐘旋轉，直到恰碰到兩群各一個點如上圖。考慮碰到的兩個點，應該不難看出碰到的兩點以及分群的方法的一對一對應的關係。

迴到原來的問題，現在我們已經知道如何把點分成兩群，那只要再枚舉開口判斷和不合法，再用類似凸包的方法，模擬出 polyline 的起點在哪就行了！這樣時間複雜度會是 O(n^4) 說是這樣說，可是 code 寫起來大蓋很痛苦吧XD 要如何判斷開口和不合法可能也令人要多思考一些時間。

不過參考 writer 的 code 後會發現，其實有一種枚舉兩個點的方法，可以把開口在哪也一並枚舉出來，相較前述方法好寫多了，大家可以想想看要怎麼樣做到這件事 ~

p.s. 由凸包上的頂點當做起點的 case 當做特例處理大概會比較方便