NCPC 2020 初賽 心得

難得這次我有賽中把題目看完
筆者：SubaRya

---

以下題敘

PA : r=qx+py，給正整數r,p,q，求|x|+|y|最小 (r<pq & r<10^9 assume that 1<p,q<10^9)

PB : 奇數魔方陣。給定第一列數字，把整個大小n^2的魔方陣求出。(魔方陣：每行、列、主副對角線個別和相等) (n<=5 & n is odd)

PC : 給一棵帶邊權的樹，n個節點，修改q次邊權Wij，求出每次修改後最遠的兩點。(n<=1500 & q<=20 && <=10筆測資 && W<=10000)

PD : 有一個以大寫字母組成長度<10^4的字串，以星號(*)結尾。總共有兩次的變動，第一次為「將最後一個字母丟到第一個，重複n-1次」，第二次為「將原字串與n-1個字串以字典序排序」，然後依序取每個字串的最後一個字母。
現在給定一字串為「每個字串的最後一個字母」，請推出原字串為何。

PE : 給定一個大小為n^2陣列L，n<1000，L[i][j]表示i與j相鄰的距離(L[1][2]=1 L[1][3]=2 L[2][3]雖然可以間接走到，但沒有相鄰因此為無限大)，題序為全點對最短情況下modify一邊權後響多少點對被變更(變更使得維持全點對最短)(0<邊權<2^32)

PF : 給m,n表示1~m中任意數量數字和=n，有全部列出，無則輸出-1 (m<=n & 8<=n<=30 & 共10筆測資)

PG : 給定d[0][0]，用下面圖片那串建一個(N-1)*(M-1)的table，給A,B,L取max(左上d[A][B]與右下d[A+L-1][B+L-1]的矩形範圍內相鄰差)

今日總過程

江大衞 昨天半夜來我家吃宵夜、改Codebook，還有互相打氣(?
隔天10點快半跟原齊、文元會合吃早(午)餐，然後買了電瓶->(茶)
進考場後說甚麼不能動電腦跟鍵盤，欸欸，都已經12:43了，剩17分鐘就要考了，說好的30分鐘測機呢？其他組去問都沒有用，然後我就上前去跟考官抗議，嗆到他一句回不出時他就摸摸鼻子去跟隔壁間考官說上台宣布開始測機(只剩15分鐘)。
宣布時有說到有提供印表機，但途中印表機卡紙(問題真多啊= = )
我快速的把全部題目看過，PF文元跟原齊正在解，我發現PD是前年新北市賽那題(「外星人的訊息」，解法我記得是BWT(Burrows–Wheeler Transform))，但我當年沒好好研究這算法(抓到，當年我喇部份分。子權你再不好好訂正啊!)，只好憑印象跟隊友說解法(因為事先說好我這次不會上機(怕我毒瘤code))。
快2小時過去，PF WA了兩次AC了，「中間時段」原齊也有把PD刻好了，
「中間時段」為->討論PD跟PC的解法，PC這題我跟文元說是樹直徑，但他說這題帶權重，我不好好的證明就放棄了這個念頭(如果我的實力好一點而且會在場上細心證明的話這題就AC了)。然後文元覺得是樹鏈剖分套BIT拉出每一條，雖然聽起來合理，但後來看Scoreboard得知很多人AC，發覺這題應該沒那麼毒瘤。
原齊把PD上傳後吃了WA，後來手動列出很多比測資都還是不知道哪裡假解
而PE跟PG我覺得很勞動而且PG的多次查詢範圍相臨差最大想不到優質的解法，所以都skip
PB跟PA也想不到好的解法，於是整場大燒機!!~~

(比賽結束)

---

想法與心得

賽後我直接問 江文吉 PC怎麼AC的，他的隊友跟我說是樹直徑。
文元認為整個團隊還沒配合的很好，原齊跟我認為是實力不夠導致PA想不到是「擴展歐幾里得」(而且也不知道這是什麼)，還有PC沒法好好證明帶邊權樹直徑DFS兩次的正確性，後來文元很直白跟我說我都在吃老本、沒在動腦，看到題目就會翻以前解過哪些相似的並困在那思路中，更何況題目都會變化。
但我認為我還是得好好地刷題，刺激不同且新的思路還有把想法轉為code並穩定輸出，原齊則想往快速開題還有數論發展。

個人感想

由於高中時期我幾乎是一人獨來獨往，組隊是用湊人頭的，很少有多次合作並賽後檢討的機會，更何況我都不知道我的「團隊配合」與「解題思路」有這麼多需要改進(真的直到文元指出我才知道)，這次多人正式賽真的學到了不少，希望兩位能繼續收留我QAQ

---

• ← Previous Post

---

---