博物館對於骨頭化石進行拼湊作業，每一個骨頭上用 A - Z 去標記。兩片骨頭可以連接則表示具有相同的英文字母。
現在有數組骨頭，上面會有數個街口。現在找一組骨頭集合，使得每一個接口都有其連接的對象，盡可能使集合越大越好。
|
|
|
|
題目相當於問找一個集合，使得每一個字母數量出現偶數次。
由於 N = 24，這個數量使用$O(2^{24})$ 相當消耗時間。使用中間相遇法 (在密碼學中可以見到，有點雙向 Bfs 的味道)，也就是分治算法的概念，將問題對切，從兩個統計結果中找交集。算法降至$O(2^{12} \times 12)$
考慮前 N/2 個骨頭 A、後 N/2 個骨頭 B，分別找到在字母集出現狀態為 S 的最佳解 A1, B1，若將兩個相同狀態組合$S \text{ XOR } S = 0$ 符合出現偶數次的條件。
|
|
給一個網格狀的地圖，每一個地點都有其相對應的人數，現在要建造一個咖啡廳，而咖啡廳所在位置可以引來在曼哈頓距離為 m 以內的所有網格上的人數。
對於每一組詢問，回報咖啡廳應該建在哪裡可以引來最多的人。
|
|
|
|
由於單一組詢問數量不到 20，想必可以使用 O(n^2) 去應付每一組詢問。
窮舉每一個可能的位置，並且去計算該位置能引來多少的人。為了加速統計人數，曼哈頓距離內，是一個 45 度的正方形，紀錄上非常不方便。利用旋轉矩陣，將整個平面紀錄轉 45 度，讓每一次的區域統計變成平行於兩軸的區域，如此一來就可以在 O(1) 時間內找到區域總和。
特別小心答案為人數 0 時，答案輸出的座標。
|
|
判斷訊息是否為垃圾訊息。
給數組垃圾訊息、非垃圾訊息，從中統計語言的出現頻率。例如 ABCDEFG 取 k-shingle 中 k = 3，那麼總共出現 ABC、BCD、CDE、DEF … 等。
接著按照題目給定的公式，計算輸入的訊息離垃圾訊息比較接近、還是非垃圾訊息。
n-gram 通常指的是以單詞 (word) 為切割單位，而 k-shingle 則是以字符 (char) 為切割單位。在巨量資料的開放課程中，以 shingle 去描述這樣的切割方式。
|
|
|
|
相當有趣的題目，終於把自然語言學習到的部分拿出來玩。但可惜題目沒有巨量資料那樣瘋狂，用 hash 去失真的操作，由於記憶體不夠，用 1-pass/2-pass 找 frequent items 之類的。
為了加速運算，改成 hash 會比較快，但只要一碰撞輸出機率時就會炸掉，所以還是別貿然嘗試。
特別用了 std::inner_product 來寫中間的數學運算，但仔細想想如果是兩個 std::map 要進行 std::inner_product() 仍然會因為元素不見得都會在兩個的 key set 而無法運作。std::inner_product 內建實作中只有單純的迭代，用在 vector 類型比較合適。
|
|
每個人對於每種食材都有其滿意度，目標滿意度總和不超過上限。
準備一人份食材時，每單位的食材都各自有不同的花費，盡可能花最多的錢。
請問總共要花多少錢。
|
|
|
|
每個人都花費相同的金額，因此把目標函數最大化後，乘上總人數即可。
現在要把問題轉換成線性規劃的模型，隨後套用 Simplex algorithm (單純形法)，可以參考 李宇骞《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》的簡報，概略說明模型的架構。資料網路上很多，不談論標準的處理程序。
接著閒聊自己的看法。
利用數形轉換的概念，從幾何概念下手，從三個變數來看，單純形法相當於在一個空間上，拿一個物體與平面找接觸，為了使目標函數最大化，會將物體表面的頂點帶入嘗試。
但是要將所有頂點找出來是相當消耗時間，因此爬行法可能會稍微好一點，也就是說，沿著物體表面，藉由一條邊爬行到更好位置上的頂點。由於線性約束，使得物體一定是凸多面體，在更高維度也是一樣的，不斷地爬升到更好的頂點後，最後一定會在最高點停止。
為了使爬行速度加快，每一次找爬升最多的鄰近點，相當於根據某一個約束，盡可能放大某一個維度上的變數 (有可能會將別的變數變小)，使得目標函數增加的值盡可能地多。根據原始的約束寫法，要找到計算仍然相當困難。
定義一個轉軸操作，讓整個問題的空間座標進行變換，方便撰寫。
|
|
\感謝諸神們替蒟蒻翻譯 GCJ 題目，巨人們/，看完第一題就過了一個小時。
windows format to linux format
|
|
［A. Mushroom Monster］O(N)
坑爹的蘑菇蘑菇，友人 A 會偷偷增加盤子上的蘑菇，系統每十秒會記錄盤子上蘑菇數量，也就是說給定的序列是系統紀錄盤子上蘑菇的情況，而不是友人 A 放入的蘑菇。接著少兩策略的最少吃掉數量
吃蘑菇策略一，可以在任何時刻吃掉任何數量，策略二，在任何時刻都以某個速度吃蘑菇每秒 f 個，當盤子空的時候，停止餵食。貪心策略，策略一考慮友人 A 盡可能不加蘑菇，策略二考慮友人 A 盡可能讓盤子空，在最後一個時刻 (系統紀錄前) 才放入蘑菇。
［B. Haircut］O(N log N)
理髮師 i 剪一個人需要 Mi 秒，客人 j 呈現 queue 的訪問方式，當有理髮師閒置時，將客人 j 會排入理髮程序。在同一時刻，若存在多名理髮師閒置，編號小的客人優先選擇編號小的理髮師進行流程。請問當所在位置為 N 時，會被指派給哪位理髮師。
二分自己剪髮時間，利算 sum += floor(time / Mi) + 1，存在 sum >= N 時，表示理髮廳已經解決 sum 個人，並且已經理超過自己。找到最小的時間後，循序找一下適合的理髮師。presum += floor(time / Mi) + (time % Mi != 0)，找到前一個時刻 time - 1 結束瞬間完成的人數，隨後貪心找 time % Mi = 0 分配給 presum + 1 ~ N。
［C. Logging］O(2^N * N log N) -> O(N^2 log N)
松鼠在樹 i 上，請問要砍掉幾棵樹，才能讓自己的樹 i 位於森林邊緣。
最簡單的思路，使用的點集，做一次凸包，查找位於邊上的可能情況，需要凸包算法、線段上判定、bitmask，應付小測資專用。O(2^N * N log N)
接著考慮要砍點使得點 i 在凸包邊緣，那麼必然找到一條線通過點 i，其中一側具有最少的點數。因此對於每一個點 i 當作中心，對其他 N - 1 個點進行極角排序，掃描線算法找半平面 (180 度) 內最少的點數。O(N^2 log N)。
|
|
|
|
|
|
2015/05/15 修正極角排序誤差
|
|
|
|
盡可能地少用 atan2()，使用外積的方式進行極角排序。
|
|
根據連通管原理，給定要灌入水的容積，請問最後水位的位置為何？
給定每個水槽的長寬高、以及離地面的高度。
|
|
|
|
講到連通管原理，很容易想起帕斯卡原理 … 喵帕斯。
二分水位高度，計算容積與目標容積的差異。
|
|
限定修改後綴，請問至少需要幾次轉換能從起始字串轉換到目標字串。
|
|
|
|
一開始用 Bfs 下去搜索，發現狀態會是 O(2^len)，這麼轉換就不太行。
將語法中單詞、起始字串、目標字串的後綴按照長度分層，將從長度為 1 的轉換開始，依序完成到 len。將後綴建成一張圖，套用 floyd algorithm 找最少轉換次數。
|
|
考慮長度 i 的轉換時，有可能存在給定的語法可以直接進行轉換，或者存在在長度 (i - 1) 時的最少轉換次數。
|
|
給 N 個點，用圍籬將這 N 個點包裹起來，並且每一個點距離圍籬距離至少為 M。
求圍籬總長最少為何。
|
|
|
|
可以將點拆分成好幾個元件，分開進行圍籬。利用高速求出子集的方式，窮舉所有的拆分方式。
dp[s] 表示點 s 所需要的最少圍籬長度，dp[s] = min(dp[u] + cost(s-u))。
圍籬長度為凸包總長加上一個圓的周長 (多邊形外角總和為 360 度)。
|
|
給一個電路圖，有四種閘 AND, OR, XOR, NOT，接著給定閘的輸入端、輸出端，以及預期的輸入和輸出。
請問是否存在電路故障。若只有一個電路故障，輸出故障的情況，否則輸出無法判斷。
故障情況有反向、全為 1、全為 0。
|
|
|
|
如何橋接電路會比較難寫，這裡用 OO 的方式去撰寫，為了方便起見，設計輸入端口只會在 div ~ 512，剩餘在 0 ~ div。
接著窮舉損壞情況，對於每次窮舉，跑一次電路架構。
|
|
駕駛蒸氣機在道路上，啟動蒸汽機通過道路需要時間。當要進行轉彎時，必須在轉彎口前進行煞車、出了轉彎口後開始加速，煞車和加速會造成所需時間變成兩倍，在起點出發必須加速、抵達終點時必須減速。
請問最少花費時間需要多少。
|
|
|
|
定義狀態 dist[i][j][dir][k] 在轉彎口 (i, j)，前一次進入轉彎口的方向為 dir，在此之前是否有煞車 k。
隨後進行最短路徑。
|
|