Codeforces Round #290 (Div. 1)

Codeforces 的比賽其實幾乎都有詳細的題解了，不足的部分通常也都會在 comment 裡由其他人補充，只可惜目前的Codeforces comment裡的雜訊時在太多了...，有礙於大家尋找演算法相關的東西。應該要建議Codeforces對每則訊息除了正評或負評的選項外，多一個"你覺得這則訊息是否和演算法或解題相關"的選項，然後再加個 filter 讓想知道演算法相關的 comment 的人能只看到這些訊息。

恩...我講這些是要說... 我不放棄寫那麼多和 Editorial 重複的內容了，除非我能寫的比 Editorial 還早，不然我就只大略的講一下我的心得(?)，否則這個網誌根本意圖使大家英文變差 XD

CF 290 Editorial 連結

Problem --- A Fox and Name

題意：給 $n$ 個字串請決定小寫字母的大小關係使得所有字串會恰好是由小到大

數據範圍：小小的

tag：[ 拓樸排序 ]

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

一模一樣的題目我一定在其他地方看過...，雖然如此但我還是寫炸了 XD。

介紹一下 scoreboard debug 法 XD --- 偶爾看看 score board 是否有哪題有些人大量challenge成功，如果有的話代表那題有個潛在的你很可能犯的bug。 雖然我曾經覺得這種 debug 法很顯而易見，不過很多人不知道。

我寫完 pB 後看了看 scoreboard，發現有些人 pA challenge 成功很多份 code。我就先回來重新想想 pA 我是否漏掉什麼 ...，結果就發現如下測資我會壞掉！

2

hacked

hack

於是我就趕緊加個幾行若遇到這樣的測資直接輸出Impossible，並重 submit 且 lock 住。這時我犯了一個錯誤...，我沒有重新 compile 並測這樣的測資，要不然就會發現我輸出Impossible後並沒有return...。而且我們這個 room 犯這個 bug 的人比我想像中的還要少好多 0.0，我只靠了 challenge 拿到 150 而已，浪費好多時間，就結論來說是賠的...。

介紹一個亂來的拓墣排序方法：

先用 floyed warshall 找出所有元素的大小關係，之後按照比該元素大的元素個數由小到大排序。這是我在這場比賽內寫的高複雜度的拓墣排序法 XD

Problem B --- Fox And Jump

題意：在某個遊戲，若你希望你往後能跳長度為 $l_i$ 的距離(向左或右皆可)，就必須花費 $c_i$ 元，請問至少要花多少錢在能跳到所有距離為整數的位置。( $0 \le i \lt n$)

數據範圍： $1 \le l_i \le 10^9$， $ 1 \le c_i \le 10^5$，$1 \le n \le 300$

tag：[數學][數論]

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

對數論熟悉的人應該能立刻知道為了滿足題目條件就是選一些 $l_i$ 使得最大公因數是 $1$ 。然後解題經驗豐富的人應該都會知道有不少題目都會利用因數個數其實並不多這個性質。實際上不超過 $10^9$ 的數因數個數最多的數是931170240，只有1344個因數。有了這兩個適時合就可以得到一個計算量至多約 300*300*1344的 dp 方法了。

雖然我看完題目就知道怎麼做，可是不知道怎麼搞的我寫了個比較複雜的求所有因數的方法...，可是實際上只要從 $1$ ~ $\sqrt{n}$ 去測試看看能否整除 $n$ 就行了@@，我因此花了比就久的時間寫它 ...

Problem C --- Fox And Dinner

題意：有 $n$ 之狐狸，每隻狐狸的年紀至少為 $2$，要讓分派它們坐在一些圓桌，每張圓桌至少坐三人，並且任相鄰的兩人年齡加起來必須是質數。若有解請輸出解。

數據範圍： $3 \le n \le 200$

tag：[ flow ][二分圗匹配]

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

看完題目立刻就知道它是某種經典 flow 題了，還記得六年前在台大培訓班時坐過某個題目如下：

給一個有向圗，請找出所有一些沒有共點的 cycle 使得每個點都恰在一個 cycle裡。

但若是第一次看到這類的題目應該會覺得很巧妙 ~

Problem D --- Fox And Travelling

題意：有個 $n$ 個點的 graph，每次可以移除一個當前 degree 不超過 $1$ 的點，請問若要移除 $k$ 個點，有多少種不同順序？$k$ 從 $0$ 至 $n$ 都要回答。

數據範圍： $1 \le n \le 100$

tag：[ 數學 ][ dp ][ tree dp ]

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

這題是以下某個常見題型的強化版：

給一個 rooted tree，每次可以拔當前的某個葉子，請問把所有點都拔光有多少種拔法？

若是這個問題其實是可以做到 O($n$) 的，但這題 $n$ 只有 $100。

我大概想了五分鐘吧，這兩個問題的差別有二：1. 這題不一定要把全部點拔完。 2. 這題也要考慮無根樹。

1.比較好解決，就dp時狀態多一點就好了，是典型的O($n^2$) tree dp結構。

2.我不久就連想到幾個小時前的 SRM D1 Hard 的其中一個概念：同一個無根樹的拔法我們可以算很多次！(把各個點分別當成root去考慮)但所有拔 $k$ 個點的拔法會算到一樣多次！哈哈在連續兩場比賽看到了一樣概念的題目。

只可惜我在寫產生 tree 的部分寫爛了...，有好多 bug，所以沒能在賽中AC。

Editorial 裡 好像還給了另一種方法。

Problem E --- Fox And Polygon

題意：任意凸多邊形都可以切成很多三角形，給兩種切法，請藉由以下操作，把第一種切法轉換成第二種切法：每次可把兩共用邊的三角形，考慮它們所形成的四邊形，改成用另外一種切成兩個三角形的方法(切線變成另一個對角線)

數據範圍：邊長至多 $1000$，給出的操作數不超過$20000$

tag：[ 平衡數rotated ] [ 數量分析 ]

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

我比賽中也有瞄了這題，可是我覺得比起 E 我更擅長 D，但其實這題存在某個好寫多的解法...

官方解是把每種切法對應到一個 rooted tree，並把每個操作想像成平衡數的 rotated，於是就可以使用各種平衡數的做法去解這題。

但這不是我所謂的好寫好想的做法。

請參考以下連結：Egor's comment or TooSimple's code

我不想翻譯了 >_<，我自己看了code大概三分鐘內就了解做法了。