SRM654ˋ

向來在台灣時間早上的場次或許因為參加的人偏少，題目有偏間單的趨勢，這場也不例外，我難得沒有重大失誤的破台了。不過我每一題都 debug 好久就是了。

這場第一名Endagorion寫的 Editorial

250 --- SquareScores

題意：給一個由小寫字母和問號構成的字串，並且給你問號代表每個字母的機率，並定意一個字串的分數為所有字母都相同的 substring 個數 (不同位置算不同)。求這個字串的分數期望值。

數據範圍：字串長度($n$)不超過 $1000$。

tag：[ 數學 ] [ 期望值 ]

關鍵字：簡單期望值

= = = = = = = = = = = = = = =
就直接運用期望值可以拆開的概念，全部也只有 $n*(n-1)/2$個子字串，若再多考慮每個字串相同的字母是哪個的至多 $26$ 種可能性去枚舉，最裸的做法時間複雜度是 $O(26n^3)$，但是$s[i...j]$ 全為同一個字母的機率可以由 $s[i...j-1]$ O(1) 轉移得知，所以立刻就壓到 $O(26n^2)$ 了。但實際上這題根本可以做到 $O(n)$，大家可以想想看～。這題算是期望值類的老掉牙的題目吧。

450 --- SuccessiveSubtraction2

題意： 給定一個數列 $a_1 \sim a_n$，考慮算式 $a_1 - a_2 - a_3 - ... - a_n$，我們可以至多家上兩組括號，求最大的可能計算結果是多少。

數據範圍：$1 \leq n \leq 2000$，有至多 $2000$個詢問(每個詢問是把上一筆詢問的其中一個數字改成另外一個數字)。

tag：[ dp ]

關鍵字：最大連續和

= = = = = = = = = = = = = = =
自己亂補上刮號就可以發現，補至多兩個括號，等價於把 $a_3 \sim a_n$ 中至多連續的兩段數字正負對調。

這題做法一堆吧，限制非長寬鬆，加上他每筆詢問實際上只有變動一個數字，那應該是可以做到 $O((q+n) log n)$ 的。

我的做法是 dp 做出每個 prefix 和 suffix 的最大連續和，然後枚舉prefix 和 suffix 切開的位置。

這題還有一個有趣的做法(參考此連結的)，先找一次最大連續和的一段正負反過來，然後再做一次相同的事就行了。

850 --- TwoEntrances

題意：給一個長的像 Tree 的家，由兩個 node 是家的入口，現在要搬家具進去每個 node，但是能般進去的條件是，由某個入口到該 node 的 path 上都還沒有放入家具，問般家具的順序有幾種？答案 mod $10^9+7$。

數據範圍：邊數不超過 $3000$。

tag ：[ dp ] [ 排列組合 ]

關鍵字：燈飾 dp

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

私認為這題難度只有 $500$，若入口只有一個，那他就只是一個非常經典的題目，我這個  BLOG 已經出現過了... 請看 CF290 pD

若是這樣的問題相信不少人都見過，但入口兩個要怎麼處理呢？

先畫意張示意圗 :)

黑點是入口，我們想像一下把代表入口的兩個點釘在牆上掛起來，大概就會變成上圖所示。

我們先想想退化的 case，例如說...掛起來後沒有任何點垂下來。我們會發現，這種 case 的話，任何時刻有擺家具的 node 都是連在一起的！於是就給了我一個靈感，我們可以 dp 狀太設成： $dp[l][r]$ 代表 $p_l \sim p_r$間及其垂下來的所有 node 都擺上家具，但其他 node 都沒有的方法數。

至於要怎麼轉移呢？我們可發現，代表 $dp[l][r]$ 的狀態，最後一個擺上家具的位置一定是 $p_l$ 或 $p_r$ 兩者之一，於是我們分別把 $p_l$ 和 $p_r$ 當作 root，然後想像你是怎麼解原始的經典題版本，那應該就會知道要怎麼轉移了 :)

VK Cup 2015 - Round 1

※ 本篇不含題解，只有簡單記錄一下比賽心得，方便以後搜尋及回憶

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

馬上就毀了不久前說的 V 字形目標 XD

這場比賽無疑是我寫解題報告至今最簡單的一場Div. 1比賽，可是我出太多包了就掛掉了 Orz 總覺得當我有明確目標的時候就一定會爆炸 ... (看看我至今為止進不了任何 online round)。

這場比賽有幾個特殊的地方：1. 難度沒有按照順序排 2. Codeforces 第一次採用以 250 分為間隔的動態分數。

Problem B --- Group Photo 2 (online version)

tag：[ 枚舉 ][ greedy ]

關鍵字：矩形橫擺直擺

賽前我並不知道題目沒有按照難度排，但尤於求攻心切就先開了 pB (自負能以差不多的時間寫完 A 和 B)，但是大概是太急躁了 ... 過了三分多鐘我都還沒看懂題目，在想要不要先回來讀 A 的題目時先看了一下 scoreboard，看了感到非常莫名， pA沒有人上傳，倒是 pE 有少數幾隻貓上傳 ... 這時心裡猜想或許 pE 是 well know 的難題才會發生這種事？於是決定繼續試圖理解 pB，終於理解意思後，立刻把這題連想到我曾經在 Topcoder SRM629 出的 Div1 250 都是橫擺或直擺的矩形問一些事情，馬上就會做了。

Problem E --- The Art of Dealing with ATM

tag： [搜索]

關鍵字：零錢

pB 過了 pretest 後看了 scoreboard，發現有大量的人傳了 pE，以及少數人傳 pB，但沒有人傳 p ，於是我開始相信這場難度沒有按照順序排，但看完 pE想了一下後並不知道怎麼做 ...，賽後看了別人 AC 的 code 才發現我看錯題目了。我沒有看到題目說的每次提領的錢至多只能提領兩種幣額的限制，賽中我不時回來思考這題，花了不少時間。

Problem D --- Social Network

tag：[貪心]

關鍵字：區間貪心

雖然 pE 卡住了，但是一直卡下去很不妙，所以就繼續開其他題，這題題目對我來說也是很難讀懂，但也是讀懂後就會做了，而且 code 很簡短，一個 for 迴圈掃過去就結束了。在我感覺上這題只有一般 Div. 1 B 以下的程度。

Problem A --- And Yet Another Bracket Sequence

tag：[字串比對][ 資料結構 ]

關鍵字：合法括弧

這題我也是看完題目後就會做了，但是覺得可能還會有比這題好寫的題目，在寫這題前先去看了 pC。

Problem C --- Rooks and Rectangules

tag：[ offline ] [ 資料結構 ]

關鍵字：矩形區域類資料結構

這題我倒是沒有讀完題就知道怎麼做 ...，應該說我第一個想到的做法有點困難，但看別人 AC這題的速度大概可以知道這題有更簡單的方法，但我覺得比起去思考更簡單的方法，還是去抄抄 codebook 寫 pA 會比較容易。賽後多想個幾分鐘就想到簡單的做法了。

我複製了 suffix array 和線段樹求 RMQ 的 codebook 迅速的寫完 pA， 但是之後一直 WA 在 pretest 第 12 組，直到賽末。賽中一直 de 不出 bug 時超心急的，我已經好久沒有卡 bug 卡那麼久了，我覺得 code 完全有按照我的思考寫啊！當下覺得要不是我想到的做法是錯的，要不然就是我的 codebook 有錯，可是無論重新檢視自己的做法證確性多少次，都還是覺得是對的，並且我那兩份 codebook 都用了好多次了。又重新看了幾次這份 code 我沒抄 codebook 的部分，都找不到錯誤，過程中索性先回去繼續想 pE 轉換情緒幾次，但也都處處碰壁。直到最後，沒有奇蹟。這場比賽我以兩題作收。

事後沉澱下繼續找 bug，當時心想，要是真的是 codebook 有 bug 的話那還蠻糟糕的，所以也幫抄 codebook 的部分 debug，然後就發現我的 bug 了...，原來我的 RMQ codebook 只當所有數是非負才會對 ...，把這部份修過後重上傳，在第 14 組 test TLE 了...，這也太崩潰 Orz 這代表就算我 RMQ 的 codebook 沒有 bug，我也一定無法 AC 這題 ...。難道我的方法太慢了嗎？我看了一下別人的 AC code，複雜度也和我一樣呀！也是一個 suffix array加一個 O(n log n) 的資料結構，我在測了一下我的 code，發現在 suffix array 的部分就 TLE 了 ...，這是怎樣，這已經是過去我把我自己寫的 suffix array code換成對友寫的快我幾倍的 code耶，結果還是不夠快 Orz，最後我去複製了一分別人 AC 的 code 裡的 suffix array 的部分蓋掉我用的 suffix array，終於 AC了。

雖然 rating 大降，不過這場收穫算是很多吧，把我的suffix array codebook 變得更快，以及除掉 codebook 裡的其中一個潛在 bug。不過上一篇 BLOG 裡寫的目標失敗了還是令人非常傷心 OAQ

Codeforces Round #296 (Div. 1)

這場比賽題目也偏簡單 (個人覺得)，至少都算是常見的題型(個人覺得)，但是仍然沒有人破台。據個人觀察，近一年內很多上古英武有名的參賽者如 tourist 的參賽頻率都變少了，所以這場我才有機會拿到第三名 >_<，要不然你們想想看，如果 tourist、Petr、peter50216、rng_58、WJMZBMR、ACRush之類的高強度且高穩定性的人傾巢而出的話，我不知道要排到第幾名去了 Orz。

在打解題報告之前先附上一張我 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 來證明 ...

有了這個求三角形面積的方法後，我們就先把所有直線按照和 $L_0$ 的夾角排序，之後在枚舉任兩條直線，計算他們和 $L_0$ 所形成的三角形面積用 $O(1)$ 在計算中有幾次被當成正的，有幾次被當成負的(可參考 code)，這題就完成了！

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你就會崩潰了。

Problem A ---Glass Carving

題意：有 $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)。

SRM653 --- 由於題目太過簡單，一不小心比賽結束時也就把解題報告寫完了！

//不知道長標題對搜尋引擎是否會有影響 0.0

相較於前三場 SRM，這場確實簡單太多了！簡單到我都為出題者感到不好意思了 >_<
而且聽說出題者還出了兩個包，這場比賽的出題者也太廢了吧！

點我連到官方題解(必須登入Topcoder帳號)

Div.2 250 --- CountryGroup

題意：有 $N$ 個人坐一排，每個人都恰屬於一個國家(沒有人有雙重國籍唷 >_<)，你對這群人有個猜想：同一個國家的人會坐在一起。你想要驗證這個猜想，於是你對每個人都問了這個問題："包括你，總共有多少人和你來自同一個國家？"。如果能從大家的回答推論出你的猜想是錯誤的，或是你能確定有人的回答是錯誤的，請回傳 -1，否則回傳根據你的猜想，這群人的國家個數。

數據範圍：小小的。

tag：[ adhoc ]

= = = = = = = = = = = = = = =
不管難度，只看題意的話，這題還算有趣吧？解法很單純，先考慮最左邊的人，令他的回答為 $x$，則從他往右算起連續的 $x$ 個人回答也得是 $x$ 才會滿足你的猜想，並把國家數目加一。緊接著把這些人排除，繼續做一樣的事，直到不滿足你的猜想或全部人都排除。

這題以 Div.2 250 來說應該是偏難的，有很多潛在的 bug，但 Sample 非常和譪可親，應該可以幫忙抓出大家大多數的 bug 吧？

順便讓大家想想看這題的變化題：

1.若大家不是坐成一排，而是坐成一個圈，甚至是大家的座位是排列成二維的樣子呢？

2.若同國家不一定要坐在相鄰位置，要怎麼算國家數或判斷有沒有人回答錯誤？

這兩題頂多也只是個 Div.2 500 的題目吧。

Div.2 500 --- RockPaperScissorsMagicEasy

題意：Alice 和 Bob 玩一個紙牌遊戲，每張紙牌上有剪刀石頭布三種圖案中的一種，每種圖案的紙牌都是無限供應的。Bob 會先選一些紙牌排成一列且圖案那一面朝下不讓 Alice 看到，接著 Alice 也會選和 Bob 同樣張數的紙排排成一列，按照順序和 Bob 的紙牌比輸贏，贏的人可以得一分，輸或平手都不會得分。但 Alice 其實有在紙牌背面偷偷做記號，所以 Bob 擺完紙排後，Alice 其實是知道 Bob 擺了些什麼。Alice 想要裝神祕的向 Bob 宣告說：這場遊戲我將會得 $score$ 分！請問 Alice 有多少種不同的紙牌選法使他可以達成他的宣告呢？答案請 mod $10^9 + 7$。

數據範圍：Bob 排的紙牌總數($N$)不超過 $2000$。

tag：[ 數學 ]

= = = = = = = = = = = = = = =
首先，雖然題目會依序給你 Bob 每個位置放的圖案是什麼，但實際上我們只關心每個圖案 Bob 共選了幾張。於是我們可以枚舉對於 Bob 的每個圖案，Alice 各贏了幾張去算排列組合，並且只要枚舉其中兩個圖案贏的張數(令其為 $x$ 和 $y$)，就可以推出第三個圖案贏的張數必須是 $score - x - y$。於是我們就有了 O(N^2) 的做法！

看了我以上列的解法應該會覺得我是笨蛋吧 XD 一個有 O(N) 做法的題目竟然被我說的那麼複雜。但說來慚愧，我第一眼見到這個題目後直覺得做法就是這樣 ...，之後看了別人的作法只能直呼小月是笨蛋 >_<

實際上，我們根本不在乎 Bob 選的圖案是什麼，我們只要在當中選 $score$ 張卡讓 Alice 能贏，剩下的卡讓 Alice 不能贏，所以答案是 $C_{score}^n * 2^{n-score}$

Div.2 1000 --- SingingEasy

題意： Alice 和 Bob 要合唱一首歌，方便起見，我們把所有音符的音高用 $1 \sim 1,000,000$ 間的數字表示，並依序給你這首歌每個音的音高。他們合唱的時候，每個音都恰由 Alice 或 Bob 其中一人唱。不難想像，若同一人要唱的兩個音差愈大難度愈高，所以他們想要安排一種唱法，使得兩個人個別唱的所有音依序排列後，相鄰兩個音音高差的絕對值和愈小愈好。例如說有一首歌只有四個音，音高依序為 $1,4,2,5$ ，那我們可以讓 Alice 唱音高為 $1,2$ 的兩個音，Bob 唱剩下的音，這樣的話所有相鄰兩個音絕對值和為 $abs(1-2) + abs(4-5) = 2$ 將是最佳解。

數據範圍：至多 $2000$ 個音符(以 $N$ 表示)。

tag： [ dp ]

= = = = = = = = = = = = = = =
這題應該讀完題就會讓人想要用 dp 去解他吧？我在想這題的時候，瞬間就覺得自己會做了，可是實際上要寫的時候，狀態轉移的部分稍微卡了一下下，離開筆電走路繞圈圈讓自己靜下來後才把轉移搞出來。連兩題 Div. 2 都出了點糗 >_<，大概是因為我對 Div.2 太輕忽了吧...

(註：以下過程我並沒有仔細處理邊界的情況，會發生你完全按照 dp 是寫下去卻可能 WA 掉的情況... 請自行腦補不足的部分 >_<)
這題我 dp 的狀態採用如右：dp[$L$][$R$] 純的最佳解代表只考慮到第 $1$ 到第 $R$ 個音，且唱第 $R$ 個的那個人是從 第 $L$ 個音連續唱到第 $R$ 個音，第 $L-1$ 個音是由另一個人唱。

當然你若要把他想成唱完 $R$ 個音以後，兩個人最後唱的音各是 第 $L - 1$ 個音和第 $R$ 個音也是可以的。

選一個好的狀態去 dp 大概是這題的第一個困難點，下一個困難點就是怎麼轉移了。

轉移分兩種 case:

1. 當 $L = R$ 時：$dp[L][R] = min_{1 \leq i \leq L-1}(dp[i][L-1] + abs(pitch[L] - pitch[i-1]))$
2. 當 $L < R$ 時： $dp[L][R] = dp[L][R-1] + abs(pitch[R] - pitch[R-1])$

雖然第一種 case 的時間複雜度是 O(R)，可是這種 case 的狀態數至多只有 $N$。第二種的轉移時間複雜度是 $O(1)$，有 $O(N^2)$ 個狀態。故總時間複雜度是 $O(N^2)$。

至於這題能不能做到比 $O(N^2)$ 更快呢...咦？似乎可以做到 $O(N)$ 唷！難道說 $N$ 變更大就是 Singing 的題目嗎！？讓我們拭目以待 ^ ^

Div.1 250 --- CountryGroupHard

題意：有 $N$ 個人坐一排，每個人都恰屬於一個國家(沒有人有雙重國籍唷 >_<)，已知同個國家的人都坐在一起。有一個記著想要問每個人這個問題："包括你，總共有多少人和你來自同一個國家？"。這個記者已經問過一些人了(問過的人可以是任意子集)，他想知道他到底有沒有必要在繼續問下去，還是說其實已經可以推論剩下的所有人的答案呢？

數據範圍：小小的。

tag：[ dp ]

= = = = = = = = = = = = = = =
看到 tag 的話這題就直接被雷爆了吧？看到這意題的第一眼，我大概想了一分鐘要怎麼去 greedy 判斷，一直想不出來，後來轉念一想，我們根本可以 dp 出所有人的回答的可能性的方法數吧...(諸如這樣，根本可以算出個數，但只問你Yes/No的題目還蠻常出現的)，於是就沒多想地隨便寫了個 $O(N^3)$ 的 dp 了。

可是我設的 dp 狀態頗蠢的，我竟然開了三維陣列 $dp[x][y][z]$，代表只考慮前面 $x$ 個人時，第 $x$ 個人是某群共 $y$ 個人的國家的第 $z$ 個人的方法數。總時間複雜度是 $O(n^3)$。

更多人 dp 狀態應該只會開一維 $dp[x]$ 代表只考慮前面 $x$ 個人時，第 $x$ 人恰好是同國家的某群人的最後一個人的方法數。可以輕鬆做到 $O(n^2)$。

而事實上，這題可以做到 $O(n)$！並不難，大家可以想想看～

Div.1 450 --- Singing

題意： Alice 和 Bob 要合唱一首歌，方便起見，我們把所有音符的音高用 $1 \sim N$ 間的數字表示，其中 Bob 的音域在 $[1,high]$，Alice 的音域在 $[low,N]$。依序給你這首歌每個音的音高。他們合唱的時候，每個音都恰由 Alice 或 Bob 其中一人唱(當然要符合唱的人的音域)。且相同音高的音符必須同一個人唱。為了使合唱的難度變低，他們希望唱的過程中，"換手"的次數最少，一次"換手"是指相鄰兩個音由不同人唱。

數據範圍：至多 $1000$ 個音符。

tag： [ min-cut ]

= = = = = = = = = = = = = = =
咦，這題不是 SingingEasy 的範圍加強版啊...難道說 $O(N)$ 的做法是我想錯了嗎 >_< 這兩題還差蠻多的 Orz

SRM 偶爾會有像這樣子相當裸的 flow 類的題目，由其這題的 input 處理相當簡單，有經驗的選手讀題加寫題不需要 5 分鐘。但是對 flow 若不熟悉，這題或許會想歪吧？可是我身為一個曾經花時間研究過各類 flow 題的人，無法想像這題能想歪成什麼東西。(後來聽別人說有想歪到 dp 去。)

總之這題就是把每個音高都當成一個點，任兩個點會建一條 cost 為 "這兩個音高相鄰的次數" 的邊。我們就能把此問題轉換為：要把所有點都 label 成 Alice 或 Bob，並且已經知道某些點的 label，使得連結相異 label 的邊的總 cost 最小。

超有 min-cut problem 的感覺對吧！就好像要我們找一個最小 cost 的 cut，使得此 cut 的一邊被 label 成 Alice，另一邊被 label 成 Bob。

確切的建圖方法為：除了有出現的 pitches 當做點以外，在另外建出一個代表 Alice 的 source 和代表 Bob 的 sink，並且把 source 建 cost 為無窮大的有向邊到確定是 Alice 唱的音高的點，也把所有確定是 Bob 唱的點連一條 cost 為無窮大的邊到 sink，最後再把上一段所提到的邊必須兩個方向都建一條相同 cost 的邊，於是就大功告成了。可以想想看為什麼這樣建出的圗是對的。

如果擁有 2014 ioicamp 的講議的人，可以翻到例題 7-8，是比這題還更裸的問題 XD

最後再給一個相同概念但稍為複雜些的題目：SPOJ839 Optimal Marks 做為練習。

Div.1 900 --- RockPaperScissorsMagic

題意：Alice 和 Bob 玩一個紙牌遊戲，每張紙牌上有剪刀石頭布三種圖案中的一種，每種圖案的紙牌都是無限供應的。Bob 會先選一些紙牌排成一列且圖案那一面朝下不讓 Alice 看到，接著 Alice 也會選和 Bob 同樣張數的紙排排成一列，按照順序和 Bob 的紙牌比輸贏，贏的人可以得 $win$ 分，平手各得 $even$ 分，輸的人得 $lose$ 分。但 Alice 發現其實有人在 Bob 的紙牌背面偷偷做記號，相同圖案的紙牌都被標了相同的數字($0 \sim 2$)做為記號，但是 Alice 不知道哪個數字對應到哪個花色。Alice 想要根據這些記號來出牌，並向 Bob 如表演魔術般的宣告說，他知道最後自己會得幾分。請問 Alice 有多少種不同的表演方法？只要他宣告的分數不同或是出的牌的序列不同就算是不同表演方法。答案請 mod $10^9 + 7$。

數據範圍：Bob 排的紙牌總數($N$)不超過 $1000$。

tag：[ 數學 ]

= = = = = = = = = = = = = = =
這題好像也和 RockPaperScissorsMagicEasy 差很多...(以解法而言)

實際上這題頗簡單的，會覺得他難的話大概只是題目敘述複雜了點？首先同樣的我們不關心 Bob 排的那些牌的順序，只關心每種記號的牌各有幾張，並令 $n_i$ 為被標記為 $i$ 的張數。

接著我們先想想看裸的做要怎麼做。應該會想到此做法：對於每個記號，都枚舉出各 Alice 各種圖案各出多少數量。也就是說，枚舉 Alice 對於標號 $0$ 的牌出了 $a$ 張剪刀，$b$ 張石頭，$n_0-a-b$ 張布；對於標號 $1$ 的牌出了 $c$ 張剪刀，$d$ 張石頭，$n_1-c-d$ 張布；對於標號 $2$ 的牌出了 $e$ 張剪刀，$f$ 張石頭，$n_2-e-f$ 張布。最後在枚舉 $3!$ 種標號和簡刀石頭布的配對方法，看看得分是否一樣。這樣的暴力做法複雜度約是 $O(N^6)$。

這做法能化簡嘛？還是要另闢出路呢？例如說根本就只有少數 special case 有可能使得 Alice 有宣告方法？不管怎樣，我們還是先列出對應的數學的式子如下：

等號左邊的變數意義都如同前面所述，而等號右邊 $A_{ij}$ 的意義為：在枚舉完後，若標為 $j$ 的卡片實際上是 $i$ ($i=0$：剪刀，$i=1$：石頭，$i=2$：布)，Alice 對抗所有此類卡片的總得分。

而所有 $3!$ 種可能標號配對方法都一樣意思就是矩陣 $A$ 中每行每列恰取一個數的和都要一樣。

列到這裡先停頓一下看看大家對做法是否有感覺了～

直覺敏銳的人應該就會注意到 "所有 $3!$ 種可能標號配對方法都一樣意思就是矩陣 $A$ 中每行每列恰取一個數的和都要一樣。" 這句話還有更和譪可親的形式！每行每列恰取一個數的和都一樣意即 "無論取哪個 column，相同的兩個 row 的值的差是固定的！"。也就是說對於任意 $i,j$，$A_{i0} - A_{j0} = A_{i1} - A_{j1} = A_{i2} - A_{j2}$。

提示到這裡應該有不少原本不會的人知道要怎麼做了吧？原本我們要同時枚舉 $a~f$，但我們也可以 $a,b$ 一組，$c,d$ 一組，$e,f$ 一組分開枚舉，每組個別枚舉完恰會對應到 $A$ 矩陣中的一個 column，我們的問題變成要求三組算出來的 row 的差值都一樣的組和有幾種，於是可以使用 hash 在 $O(N^2)$ 的時間做到。


= = = = = = = = = = = = = = =
這篇讀完應該能讓大家相信我說的這場 SRM 很簡單吧 XD 我覺得題目敘述本身會令人覺得還蠻有趣的啦，只是真的偏簡單就是了 0.0

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 當做特例處理大概會比較方便

Codeforces Round #295 (Div. 1)

這場比賽我覺得偏簡單，除了 E 以外，理解題目後不超過一分鐘就會做了，但 E 只是個標準的三連通問題 @@ 幾年前和別人組隊練習時看過好幾次，但都不是我負責，於是我隨便 google 一下搜不到 code就直接放棄了 @@ 之後看題解發現我根本理解錯 E 的題目意思了，所以實際上 E 應該沒太難 0.0


雖然我說這場偏簡單，但因為我英文太差加上我太輕視題目，把 D 的解的輸出方式搞錯，最後與第二名擦身而過 OAQ

點我連到官方 Editorial

Problem A --- DNA Alignments

題意：給一個由 ACGT 四個字母組成的字串 $s$，請問有多少同樣長度字串 $t$，使得 $p(s,t)$ 最大。令 $q(s,t,i)$ 為把 $t$ 的 前 $i$ 個字母移到最後面後，和 $s$ 同位置是相同字母的個數，則 $p(s,t) = \sum_{i=0}^{n-1}{q(s,t,i)}$。答案請 mod $10^9+7$

數據範圍：字串長度不超過 $10^5$

tag：[ 數學 ][ 貪心 ]

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

$p(s,t)$ 其實就是兩個字串的字母頻率向量的内積。何謂字母頻率向量？假設共有 $k$ 個字母，那字母頻率向量就有 $k$ 維，且第 $i$ 維的值就是第 $i$ 個字母出現的次數。何謂向量？請去翻高中課本 >_<

於是此問題就變成，給定一個四維向量 $v$，請找一個各維度和為 $n$ 的向量使得兩項量內積最大。這問題看起來很 greedy 對吧？只要把數字都加在 $v$ 中數值最大的那些維度就可以了(證明略)。所以值最大的維度若有 $r$ 個，答案就是 $r^n$。

Problem B --- Cube

題意：在平面上有 $n$ 個穩定的點。一個點 $(x, y)$ 若是穩定的，有兩種可能：(1) $y$ 座標為 $0$。 (2) $(x-1, y-1), (x, y-1), or (x+1, y-1)$ 也存在點。現在我們要把所有點拔掉，一次只能拔一個，並且拔的過程中，所有點仍是穩定的。為了把題目變難一點，我們把他變成兩人遊戲，把所有可能的操作對應到一個 $n$ 位數的 $n$ 進位數，由位數高到位數低依序代表點的編號先拔到後拔，先手會希望對應到的數字愈大愈好，後手則希望對應到的數字愈小愈好。他們都很聰明，請輸出答案 mod $10^9 + 9$。

數據範圍：所點 $xy$ 座標絕對值不超過 $19^9$，且 $y$ 座標非負。 $1 \leq n \leq 10^5$。

tag： [ 圖論 ] [ 貪心 ]

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

這題一看完就覺得很greedy，算是資料結構模擬題吧，輪到先手是就拔所有可以拔的點中編號最大的，後手則拔可以拔的點中編號最小的，每次拔完只要檢查附近的點可不可以拔的狀態有沒有改變。

說是這樣說，可是寫起來其實挺麻煩的，並需儲存很多資訊，對 STL 地使用不熟悉的會感到很苦手吧。

是說最近拔點的題目也太多了...

Problem C --- Pluses everywhere

題意：給一個可以有很多 $0$ 開頭的 $n$ 位數，請把所有在當中插入 $k$ 個加號的運算式的結果加起來。

數據範圍：$0 \leq k \lt n$

tag：[ 數學 ]

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

就只是個數學題，切入點就是考慮原始數字的每個位數，在所有可能的運算式中，會被當作 $i$ 位數幾次。

要解這題，首先你一定要會經過 O(n) 預處理後，O(1) 算出 $C^i_j$ 的值($0 \leq i \leq n)。我這裡就不解釋怎麼做了 0.0。會做這個後，再考慮我前面所說的切入點，會發現可以 O(n^2) 算出答案，但這樣還不夠快。所以我們就要想辦法省略一些計算。幸運的是，在算每個數字貢獻的和的時候，我們會發現他們的公式很像！已知某個位數貢獻的值，就可以 O(1) 算出相鄰的位數貢獻的值。所以整題的複雜度是 O(n)。

這類的題目其實蠻多的，雖然樸素加總很花時間，但實際上有很多重複的運算可以省略。所以這題我也是一看到題目就知道解題方向了

Problem D --- Shop

題意：有 $k$ 個數 $a_1$ 至 $a_k$，你有 $n$ 種可能操作，每個操作都有兩個數字 $i$ 和 $b$。操作有三種類型，第一種：把第 $i$ 個數字改成 $b$。第二種：把第 $i$ 個數字加上 $b$。第三種：把第 $i$ 個數字乘以 $b$。請在當中選至多 $m$ 個操作，執行順序任意，使得所有操作結束後，所有數字的乘積最大。並構造出一組解。

數據範圍： $1 \leq a_i \leq 10^6$，$0 \leq m \leq n \leq 10^5$。

tag：[ 貪心 ]

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

首先你會發現，最好的操作方式一定是選了某些操作後，先執行第一種的所有選到的操作，在執行第二種的所有選到的操作，最後在執行第三種的所有選到的操作，證明略。

接下來我們就要比較選哪些操作比較好啦，是否能有個直接比較的基準呢？先想像若只有第三種操作，我們就不需要考慮 $i$，只要單純的比較 $b$ 的大小就好了，這是最簡單的。若只考慮第二種操作的話呢？首先可以發現，若 $i$ 相同，當然是 $b$ 愈大預先取。但 $i$ 若不同呢？我們就得把 $a_i$ 的值也考慮進去，於是會發現，若原本是 x，加上 $b$ 後會變成 $(x+b)/x$ 倍！而且我們已經知道對於同一個 $i$，若要使用某個操作，一定會把所有相同 $i$ 中 $b$ 比該操作大的操作先執行完。於是我們就能算出使用該操作之前的 $a_i$ 的值了。所以每個第二種操作，我們都可以把他等價於乘以某個值的操作，而且這樣就可以和第三種操作做比較了！

這題最困難的部分就是，要如何把第一種操作和第二種操作混合考慮。

其實若只有第一種和第三種，做法也和只有第二種和第三種類似，因為對於第一類操作中相同 $i$ 的操作，我們至多選一個，且一定是選 $b$ 值最大的那個，由於我們是在最初時就採用第一種操作，所以我們也可以把他等價於，乘以某個定值。

現在正式來把第一種和第二種操作一起考慮。我們會發現若第一種操作的 $b$ 值為 $b_1$，第二種操作的 $b$ 值為 $b_2$，若 $b1 - a_i > b_2$ 這第一種操作的優先度會比較高，否則就是第二種操作的優先度比較高！於是，我們實際上可以把第一種操作的一組 $(i, b)$，當成是第二種操作的 $(i, b - a_i)$ (請仔細體會這句話的涵義)，於是我們就把他轉換成只有第二種和第三種操作的 case 了。

直接舉個例子，假設測資如下：

1 2 5

2

1 1 3        ---(1)

1 1 4        ---(2)

2 1 1        ---(3)

2 1 3        ---(4)

3 1 2        ---(5)

首先，第一種操作我們只需要考慮 $b$ 最大的那個，於是可以把 (1) 捨棄，現在剩下：

1 1 4        ---(2)

2 1 1        ---(3)

2 1 3        ---(4)

3 1 2        ---(5)

接著，我們把(2)當成第二種操作來用，原本的 $b$ 是 $4$，減掉 $a_i$ 後變為剩下 $2$，這群操作變成：

2 1 2        ---(2)

2 1 1        ---(3)

2 1 3        ---(4)

3 1 2        ---(5)

最後，若尚未執行任何操作，$a_1$ 是 $2$，若有執行第二類操作，會優先選 (4)，由 $2$ 變成 $5$ 是變成 $2.5$ 倍，於是 (4) 會等價於 $3 1 2.5$，現在操作群變成：

2 1 2        ---(2)

2 1 1        ---(3)

3 1 2.5     ---(4)

3 1 2        ---(5)

接著考慮 (2)，由於若選 (2)，一定有選 (4)，故執行 (2) 之前 $a_i$ 的值會是 $5$，執行完後變成 $7$，等價於乘以 $7/5$。最後把 (3) 也如法炮製，最後變成如下：

3 1 7/5     ---(2)

3 1 8/7     ---(3)

3 1 2.5     ---(4)

3 1 2        ---(5)

於是就可以簡單的 greedy 了！

這題時做上有蠻多地方可能寫錯的，例如說，在比較兩分數的大小，若直接分子乘對方分母去比較，會超過 long long，我的 AC code 是直接轉型成 long double 來比較。不過這不是我賽內錯的地方，我賽內錯的地方是，我操作編號直接由小到大輸出 = =，但應該要按照編號的種類輸出 ...因為我在看 output format 時讀入我腦內的是，請把用到的操作的編號由小到大輸出，因為我只去看 output format 的最後一行："in the order in which they appear in the input"，我每次讀題目都太隨便了 OAQ

Problem E --- Cycling City

題意：給一個 $n$個點 $m$條編的簡單無向圖，請給出 $3$ 條點起點和終點相同的簡單路徑，使得這三條簡單路徑，除了起點終點以外，沒有任何共用點。

數據範圍：$1 \leq n,m \leq 10^5$

tag：[ 圖論 ] [ 三連通 ]

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

若把找 $3$ 條簡單路徑改成找兩條的話，就是個普通 BCC 問題。但如果是三條呢？等著看 Editorial 吧＠＠

看完 Editorial 後，發現我原本根本理解錯題目了 ... 由於我英文很差，所以往往會自動把看讀到的東西去 match 到我比較熟悉的東西，所以就理解錯啦，理解成起點和終點有固定在 $1$ 和 $n$，其實若有仔細看 Sample 就知道絕對不是這樣嘛 = = (現在上面的題意已更正)

如果起點鐘點可以任意選定的話，要怎麼做呢？或許會有個直覺 --- 完全不存在這樣的三條 path 若且唯若此張圖是仙人掌(Cactus)！所謂的仙人掌就是每個雙連通元件都是單獨一條編或單獨一個 cycle 的圗。雖然我說是直覺，可是其實我直接被 Editorial 捏答案了，至少我看完解答後覺得很直覺啦！若是仙人掌，則一定沒有這樣的三條 path是容易證的，另外一個方向的證明稍為難一點，以下稍為題一下證明的輪廓 (同時也能找到一組答案)：

若對 BCC 熟悉的人就會知道，這三條 path 一定是在 BCC 的同一個連通元件裡。現在我們要試圖在一個不是單獨一條邊也不是單獨一個 cycle 的連通元件內找這樣的三條 path。

步驟一：在此連通元件中找到任意一個 cycle。
步驟二：在這個cycle上找到一個有連出不在 cycle 上的邊(記做 $e$)的點(記做 $x$)。(想想看為什麼一定找的到？)
步驟三：從該點延著 $e$ 找到一個簡單 path 又走回原本的 cycle 上非 $x$ 的點 $y$(此 path 只和 cycle交於 $x$ 和 $y$)。 (想想看為什麼一定走的回來？)

於是步驟三找到的 path，以及 $x$ 和 $y$ 把原本的 cycle 切出來的兩條 paths 合起來就是此題所要的一組答案了！我想證明應該不難吧？而且我怎麼印象這個問題在台大的張振華教授所開得圗論課裡面有提到 @@。