五道題目依作題次序如下﹕
A﹕Word–給一字串s，如果小寫字母多於等於大寫字母，則把s所有字母寫成小寫，否則寫成大寫。秒殺題(2 mins)
B：Fortune Telling-給出N個整數﹐取一子集使得它們的和是奇數，問最大和是多少？若不能組成奇數和則輸出0。又一秒殺題，檢查有沒有奇數，沒有的話則輸出0。否則全部加起來，若奇數數量是偶數的話則減去最小的奇數。(8 mins)
C：Title-給出一字串s，內含字元包括首K個英文字母和'?'。現在必須把所有'?'填上首K個英文字母之一，使得s是迴文，K個不同的英文字母至少出現一次。可以無解。不太麻煩的case handling，先檢查s自身是否不符合迴文條件。否則對於對稱字對，其中一個不是'?'的話則必須把另一個帶'?'的填上該字元。統計有多少對稱'?'對(x)，和剩下有多少個未用的英文字母(y)，若y > x則無解。否則，從對稱軸心開始，把未用的字母按倒序填上'?'對，如果字母都已經用盡了，則填'a'。最初全考慮了這些case，也過了pretest(22 mins)。怎料最後發現試一組數據時發現vector的在空置的情況下仍使用pop_back()，因此導致了出錯。改回後已是失了大半分數，敗筆之一(110 mins)。順手抓到一個因為沒處理填上'a'的submission，hack掉了。
E：Shortest Path-毅然跳過D直接做E(事後也証明是對的)，因為看到沒人交D但有人提交了E。大意是給了一幅無向不帶權的圖，問從vertex 1 to vertex N的最短路是甚麼，但路徑P中不能包含連續三點使得該三點是K個黑名單中列舉的。直接做法應該是BFS的，但神差鬼推之下我竟然寫起了dijkstra。記d[x][y]為從vertex 1 到 vertex y的最短路，當中y之前要經過vertex x的。即d[x][y]記錄了1->...->x->y的最短路。轉移也是很明顯的﹕枚舉點z並從d[x][y]+W(y,z)更新d[y][z]，而且(x, y, z)不在黑名單中。檢查黑名單的方法我無恥地用了map
D：Team Arrangement-很tricky的題目。給了3N個人的分數排名（從最高到最低分）。然後每次選一個最高分而未組隊的人做隊長，然後他自己有一個preference list去選餘下未入隊的兩人組隊。現在給出的是組隊順序，但每隊的隊員分數並非順序的，求第K人的可能preference list並需要lexicographically最小。
第一個想法就是﹕K在第i隊中，那麼，設A包含1..i隊的人（不包括K自己），i+1..N隊則放到B內。那麼答案應該是Concat(sort(A), sort(B))。很有趣的過了sample但過不了pretest。然後發現另一件事﹕如果第K人不是隊長的話那麼他的preference list是毫無意義的，則輸出{1, 2, .. K-1, K+1, ... 3N}即可。發現的是原來第二組樣例很tricky地沒想到這個情況也能過…再提交，可惜再次過不了pretest（出題者還是挺好人的）。想了大概半小時，終於發現漏了處理這個情況﹕假設A = {a1, a2, ... x, ... y, ... aj} B = {b1, b2, ... bk}，當中x和y是和第K人組隊的隊友。那麼正確的案答應該是A = {a1, a2, ... x, ... y} B = {b1, b2, ... bk, ai, ai+1, ... aj}，然後輸出Concat(sort(A), sort(B))。若不明白的話請參考此例﹕
3
5 4 1 2 6 3 7 8 9
5 6 2
9 3 4
1 7 8
4
答案是
2 3 5 6 9 1 7 8
過了pretest都挺有信心Pass這題的(94 mins)。之後便去搞hack和重新提交C。
比賽結束後很後悔自己沒好好再檢查C的程序，分數之差足以讓我在system test之前由總排名第四掉至十六。但system testing過後卻是總排名第九，room排名第三，而且全部題都答對了。
排名真的不太重要，最重要的是自己想算法和查找bug的能力好像有點進步了。
保持練習。
沒有留言:
張貼留言