2021 ICPC Asia Taiwan Online Programming Contest

某種程度上來看,如果說 NCPC 決賽像是大學版的能力競賽決賽而 ICPC 台北站像是 TOI 選訓營,那麼 TOPC 倒可以做為 \(1!\) 入營考。NCPC 決賽的前幾名可以直接晉級台北站,其他隊伍則需要參加 TOPC 以獲得資格。

本來以往清大的隊伍似乎會一起聚在電腦教室,然後外頭備有零食點心可以享受。但是由於疫情的緣故,今年就不能如常比照辦理。不過我們這隊還是決定到資電館 323, 也有看到其他隊伍在 325.

A - Olympic Ranking

就是給定一些國家的金牌、銀牌及銅牌數量,輸出依照金、銀及銅多寡排名最大者。賽中我寫一個 \(O(N\log N)\) 的排序,後來學長才說我中毒惹 – 求第 \(k\) 大只要 \(O(N)\) 啊!!

1 try, 17 min

J - JavaScript

這題就是簽到水題,如果兩字串都是數字則輸出其和,否則輸出 NaN.

1 try, 20 min

B - Aliquot Sum

看起來是判斷一個數是盈數、完美數或合數,實際上就是如此。但是我們看到有 \(T\leq10^6\) 個 \(\leq10^6\) 的數的輸入就很擔心直接實作會不會 TLE, 然而看看這題很多隊伍通過,而且發現這題時限是八秒。WA 一次好像是因為 \(1\) 的 special case.

2 tries, 38 min

D - Drunk Passenger

這是一題數學機率題,張學長好電推一下就 AC ><

2 tries, 75 min

C - A Sorting Problem

對於一個陣列,每次可以交換其值相差為一的元素,問最少交換次數使得陣列被排序。我們花惹一點時間才證明通靈出這題與求逆序對 (inversion pair) 數量是等價的,理由是把 index, value 互換之後原問題即轉化為交換相鄰元素使得陣列被排序。我那陣子剛好有教人 merge sort, 但合併還是寫爛惹一下子 QQ.

1 try, 98 min

E - Eatcoin

這是一個奇怪而且偏複雜的大數題,楊學長用 Python AC 掉 ><

1 try, 141 min


最終我們總共作出六題,以第 \(29\) 名(清大第二)獲得參加 ICPC 台北站的資格。

這場比賽我自評表現算是差強人意喇。

Copyright

Comments

comments powered by Disqus