在打解題報告之前先附上一張我 dreamoon 這個 id rating 變紅後的走勢圗！
我現在正在企圖描繪一個嚴格遞降再嚴格遞升的Ｖ字型，而且希望右端點能比左端點高 XD 究竟下一場能不能做到呢 >_<，可是下一場是 Div.1 only 的 VK Cup - Round 1 的 online mirror，依經驗這樣的比賽參賽者會少，而且厲害的人會變多，這樣很可能會不僅沒有升高，反而使我的 rating 就此跌下去 ... 好想戰略性撤退 Orz，啊啊啊有這種想法的我好沒有骨氣喔 OAQ
順帶一題近年來的 rating 和台灣的物價一樣，上漲很嚴重，所以畫 V 字才沒那麼難，畫 V 字左端時，深紅色以上的人才 18 個人左右，全世界成為深紅色的人不過三十個，但現在當過深紅色的人已經滿街都是了 ...
這場比賽雖然簡單，但是很多題都有不只一種解法值得我一題，要不然原本比完時覺得題目太簡單不想寫這篇的說 XD
要看官方的 editorial 請點我
以下採用倒敘法從最後一題開始
Problem E --- Triangles 3000
題意：給平面上 $N$ 條直線，請問任取三條直線的所圍成的三角形面積期望值。
數據範圍：$e \leq N \leq 3000$，任兩條線不平行，且任兩條直線的交點座標絕對值在 $10^6$ 內。
tag：[ 計算幾何 ]
= = = = = = = = = = = = = = =由於題目敘述超短，我寫完前三題後是先看這題的，看來這題時限後，我想了一下下馬上想到一個 $O(N^2 log N)$ 的做法，可是覺得並不好寫所以就回去看 pD 了，pD 上傳並放棄掙扎後，只剩下二十出頭分鐘，覺得時間不夠用，所以就去 challenge 別人。
但是賽後發現，我的思考完全被題目時限限制住了 OAQ，因為我知道若這題官方有比 $O(N^2 log N)$ 更快的做法，就一定不會讓時限那麼長，就以為大概不會有複雜度更好甚至更好寫的做法...，而最後可以發現，官方給出的解答也只是 $O(N^2 log N)$，但若去大家上傳的 code，就可以發現至少存在兩個 $O(N^2)$ 十分鐘內可寫完的做法，我的 $O(N^2 log N)$ 方法也和官方的不一樣，所以這題或許千百人來想就會有千百種做法。
$O(N^2 log N)$ 的做法我就不題了，我來介紹一下官方解答理沒提到的兩種 $O(N^2)$ 做法。
要求期望值，其時就是要你求所有 $C_3^N$ 種取直線方法的三角形面積總合。故要給出一個 $O(N^3)$ 的做法應該不難，直接枚舉任三條直線，再用任意一種求三角形面積公式加起來。於是若要加速應該會去想看看加起來的過程是否有一些步驟可以一併處理。
三角形面積的求法對於解題來說是很重要的。若你訪問一個人要求三角形面積要怎麼算，國中小學生大概會回答你底乘以高，高中生可能會回答你海龍公式、$a \cdot b \cdot sin(theta)/2$、兩向量外積除以二等。而在競賽中的計算幾何，兩向量外積應該是最常用的，但也有一個大家也很常用甚至適用於求任意簡單多邊行面積的方法：
把多邊形每個點想像成一個由原點到該點的向量，其中一個逆時鐘的順序是 $v_1 \sim v_N$，則此多邊行面積將會是 $\sum_{i=1}^N v_i \times v_{i+1}$ (其中 $v_{N+1} = v_1$，$\times$是外積的意思)
這個做法絕大部分有關計算幾合的書都會提到。既然有一個這麼常用到的公式，從這裡下手也無可厚非吧？把這個公式和這題聯想在一起，我們會發現，所有有外積運算的點對都會同時在題目給定的某條直線上。每條直線上將有 $N-1$ 個我們關心的點，這些點共有 $O(N^2)$ 個外積運算，所以我們只要把這些外積運算做到 $O(N log N)$ 甚至是 $O(N)$ 就解決這題了！
要如何加速運算，常見的著眼點就是用一個好的順序處理這些點，使得每次加入一個新的點時，可以用數學或資料結構的方式快速求出和已存在的所有點的外積。我賽中想到的方法，就是使用所有點在該直線上按照此直線向量的方向來決定點的加入順序，再套一些資料結構來做。
但實際上，順序若採用產生交點的直線斜率來排序，將會有更好的性質！(所以在想這類問題時，要多想想各種排序方式，可能會發現更簡單的做法 0.0)
請參考此程式碼。(若有什麼不懂得 function 或運算操作，請務必搞懂他們 >_< 這份 code 超短 ！) (補上此奮程式碼賺寫者親自解釋做法的 comment)
我簡單描述這份程式碼在做啥。
1. 把所有直線按照斜率排序。此過程時間複雜度為 O(N log N)。
2. 枚舉直線 $L_i$，按照斜率考慮此直線和其他所有直線的交點，也就是說其他直線是由和他夾角最小的開始枚舉到最大的。
3. 接著重點來了，對於任意三條直線$L_i$、$L_j$、$L_k$，若 $L_j$ 和 $L_i$ 的夾角比$L_k$ 和 $L_i$ 的夾角小，那麼這三條直線所形成的三角形的三個頂點，按照逆時鐘排列，一定是 $L_k$ 緊接在 $L_j$ 之後。簡單來說就是任兩點外積的順序和點加入的順序都一樣。
於是我們要求的就是 $\sum_{i < j} \bf{p_i*p_j}$ ($\bf{p_i}$ 是第 $i$ 個加入的點所代表的向量)，要把這個加總做到 O(n) 應該不困難，可參考程式碼。
由角度的順序加點和按照交點在該直線上的順序加點最大的不同就是，不用在另外考慮兩點在外積時誰左誰右，所以做法就變簡單很多。
在附另外一個我覺得比較奇葩的做法，請參考此程式碼。
這份程式碼相對前一份來說並不好懂(因為很奇葩？)。
奇葩的部分就是他算三角形面積的方式是非常少見 (至少我沒有看過的印象)。
要求三條直線所產生出來的面積，他先另外取一條不和這三條線平形的直線 $L_0$ (你可以看到程式碼中他採用旋轉所有 $N$ 條線一個奇怪的角度，然後另外取的線就直接取 $x$ 軸)，然後把這三條線按照和 $L_0$ 的夾角排序，令其分別是 $L_1$、$L_2$、$L_3$，所求面積將等於 ($L_0$、$L_1$、$L_2$三角形面積) $+$ ($L_0$、$L_2$、$L_3$三角形面積) $-$ ($L_0$、$L_1$、$L_2$三角形面積)
用下圖來舉例的話，就是我們要求的黃色部分面積是 (黃+紫) + (粉) - (紫+粉)。
然後大家請不要以為看這張圗對了就覺得這樣算面積的方法一定是對的，實際上我至今還不知道怎樣簡單的證明這個面積算法的正確性，目前我只會使用枚舉高達十幾種 case 來證明 ...
problem D --- Fuzzy Search
題意：給兩個僅包含字母 ATCG 的字串 $S$ 和 $T$ 以及一個非負整數 $k$，$T$ 的長度不超過 $S$，問$t$有幾種和$s$的位置配對方式，使得 $T$ 中每個字母和 $S$ 中最近的相同字母位置差絕對值不超過 $k$。
數據範圍：$字串長度不超過 $200,000$，$0 \leq k \leq 200,000$
tag：[ 傅立業 ]
= = = = = = = = = = = = = = =//以下這段和做法沒關係
這題比賽中我有想了一陣子有沒有普通的字串匹配解 (我覺得這題若用傅立業太無趣了 ... 最近的一些題目都給你用傅立業就好了啊 = =)，但最後還是決定回歸傅立業硬爆，但我發現我沒有把 FFT 放在我的 codebook 資料夾裡 ...，只有一份 NTT 的 code，而且在我地記憶中我的 NTT codebook 超慢...，不過賽中我還是硬著頭皮上了， submit 了兩次，第一次 RE，就想說我陣列或許開太小了(咦我以為我有好好的計算過)，於是就在把陣列開兩倍大再上傳，結果得到 TLE OAQ，這題有三秒耶！而且 $n$ 只有 $20000$ 耶！連這樣也TLE...?，這時候我就在思索說，究竟要現場壓一下這份 NTT 的常數，還是回去挖以前 ICPC 組隊時對有用的 FFT 出來？而就在這個時候，Codeforces 公告說，這題的測試資料數據給的比題目所說的數據還大，晚點會 rejudge (難怪第一份會 RE...)。此時我賭性堅強，就決定放著不管啦，最後這題很幸運的以差 0.005 秒的時間獲得 AC，但真的能稱做很幸運嘛？這只能怪我沒有打裡好自己的codebook 吧？在這種人手一份 FFT codebook的時代，大家幾乎都不是親自寫 FFT，而你確 TLE 在不是親手寫的部分，那只能怪自己事先準備不充分了 ...
//以上這段和做法沒關係
只有ACTG四種字母，很容易讓人聯想到每種字母分開考慮，接著來想想看對於一種字母來說，會造成哪些位置不能擺？再問更明確些，如果 $T$ 的第 $i$ 個位置是 'A' 那 $T$ 的開頭不能擺在哪些位置呢？如給定 $i$，應該很容易想到一個 $O(|S|)$ 的做法解決這個問題吧？(應該只是個Div. 1 A難度的問題) 而且也不難發現，對於不同的 $i$ 值，不能擺的位置只是隨著 $\bf{i}$ 的增加，向反方向位移而已，若觀察到粗體字的部分，應該就會馬上聯想到 FFT 了吧？所以由這樣的思路看來，這題應不難，以 AC 數量來看他難度和 pC 差不多，他會被排在 pD 就只是因為他用了 FFT。
並且由於我們只關心 FFT 的結果是否非零，所以他的摺積運算可以使用位元運算加速，所以也有很多人是使用位元運算來加速的，一直以來，只關心是否非零的傅立業題都卡不掉位元運算...(例如 CF472G)，請看看別人怎麼用位元運算 AC本題，看了後你一定會感嘆說為什麼要去使用 FFT ...。
Problem C --- Data Center Drama
題意：給一個 $n$ 個點 $m$ 條邊圗(可以有重邊和自連邊)，請加盡量少的邊並把所有邊定向，使得每個點的 in degree 和 out degree 都是偶數。
數據範圍：$1 \leq n \leq 100,000$，$1 \leq m leq 200,000$
tag：[ 圗論 ] [ 尤拉路徑 ]
= = = = = = = = = = = = = = =我一讀完題目就連想到本年度台大 PK 賽的 pB --- 給一個圖把他定向，使得所有點的 in degree 和 out degree 的差的絕對值不超過 1。想必這題也是個類似做法(某種程度上把degeree變成偶數，然後在尤拉路徑上做一些構造) 構造題。於是我就立刻想到如果所有degree都是偶數，而且邊數也是偶數且連通時，只要按照任意尤拉路徑的順序，把邊定向為一正一反就能滿足條件了。
接下來就一個一個把粗體字的條件去掉看看要怎麼辦～。若 degree 不是偶數一定得變成偶數才有可能能滿足題目條件，那就兩個兩個奇點(奇數 degree 的點)來配對，但任意一種配對方式都可以嗎＠＠並不是，實際上必須讓配對後連通塊的數量變愈少愈好，畢竟若之後有某個連通塊若只有奇數個邊，那就還得再增加邊，而若一剛開始就先把很多個有可能變成奇數個邊的連通塊串起來，想必能減少要增加的邊的數量，至於要怎麼把所有含有積點的連通塊串起來呢～這裡就不說了 >_<。最後我們把每個仍含奇數個邊的連通塊隨便找一個點加一條自連邊，就能滿足所有粗體條件了！
上一段只是大略講一下我的思路，至於很多細節還是得好好的證明。
code 可以參考這裡。然後我看到這份 code 才發現題目有圗是連通的這個條件.... 所以這題更簡單了 Orz 都怪我只大略看了題目敘述以及看了所附的圗及 Input 就猜題意了... 但圗是連通的這個條件怎麼可以不寫在 Input 裡啦 Orz
另外還有一種不需要由拉路徑的有 tree dp 感的做法，請參考 this comment。
Problem B --- Clique Problem
題意：數線上有 $N$ 個點，每個點都有權重，且任兩個點若權重和不超過兩個點距離時，就有邊連接這兩個點，請求出最大的點團，使得此點團任兩點都有邊相連。
數據範圍：$N$ 不超過 $200,000$，座標介於 $0 \sim 10^9$且兩兩互不相同，權重介於 $1 \sim 10^9$。
tag : [ greedy ] [ dp ]
= = = = = = = = = = = = = = =
這題畫個圗應該就可以發現，此題等價於，在眾多 $[x_i - w_i, x_i + w_i]$ 的區間中，要選盡量多的區間使得讓兩區間交集長度不大於 $0$。想到這裡後就令我覺得，這隨便 dp 都能 AC 吧？於是就憑直覺寫了一個有點稍嫌複雜的 dp。
可是後來看到別人的 code 後整個崩潰 ...
若你也寫了個有點複雜的 dp，去看一下Editorial你就會崩潰了。
題意：有 $w*h$ 大小的蛋糕，有 $n$ 個操作，每個操作會從水平或垂直的某個位置切一刀，請問每個操作後最大的那塊單高面積。
數據範圍：$2 \leq w, h \leq 200,000$，$1 \leq n \leq 200,000$，不會有重複的操作。
tag : [ STL ] [倒著做 ]
= = = = = = = = = = = = = = =
這題以眼就令人覺得是經典的STL模擬聯習題，有些人會因為不熟悉 STL 的用法而沒AC，例如說 set $S$ 要取lower_bound，必須使用 Ｓ.lower_bound(x)，但有人卻因為使用 lower_bound(S.begin(),S.end(),x) 而獲得了TLE。大家若好好讀熟 STL的使用方式相信對比賽中有一定的幫助 0.0
這題比較值得一題的是，若想像成先一次做完所有操作，再把操作一個一個倒著取消回來，將可以做到 O(n)。
沒有留言:
張貼留言