Back to Posts

學科能力競賽 - 全國賽心得

去年新北市有 5 個名額,我剛好第六名無法參賽
今年拿了第四名,終於能在我高中的最後一年,晉級全國賽啦~

中午先與板橋高中一夥人吃拉麵,與指導老師蝸牛一起搭火車前往新竹,路途上四人都在練習,就希望在大家高三這年,不留下遺憾

報到

坐交通車抵達交大後,上網查詢自己編號排隊領 badge、T-Shirt,沒想到我竟然有幸排到 最棒的編號 XD

The Answer of Life, the Universe, and Everything

筆試

雖然只佔 10% ,但還是考了 50 分鐘

7. 相同的 10,000 筆資料中,以何種樹儲存時最大高度最小

(A)  AVL Tree
(B)  Red-Black Tree
(C)  2-3-4 Tree
(D)  不一定

我對這三棵樹都不是很熟,只知道 2-3-4 TreeB-Tree 有點關係,但沒去猜他 * -5 分

8. 給定一顆 Pre-order traversal (前序走訪) 輸出為 A B C D E 的 Binary Tree,求何者不可能為該樹的 In-order traversal (中序走訪)

(A)  C E D B A
(B)  C B A E D
(C)  A D C E B
(D)  A E C B D

這題要是有檢查,該要拿到分的,一時把 Pre-orderIn-order 想反 * -5 分

12. 請問以下 C 程式碼中的 function pointer 該怎麼宣告才是正確的?

#include <stdio.h>
int ret;
int * plus(int a, int b) {
	ret = a + b;
	return &ret;
}
int main(void) {
	# 在此宣告 function pointer
	funcptr = plus;
	printf("2 + 5 = %d\n", (*funcptr)(2, 5));
}
(A)  int * &funcptr(int, int)
(B)  int * (*funcptr)(int, int)
(C)  int * funcptr(int, int)
(D)  int **funcptr(int, int)

這題大概是最有疑問的兩題之一了,提早離場後馬上有人發現只有 (B) 能成功編譯,不過由於輸出是 address 而非 2 + 5 = 7,主辦單位決定送分 * -10 分

住宿

覺得還不錯,晚上開 YouTube KTV 聽歌 XD

上機考

第二天一早剛吃飽早餐,放完背包、手機後,馬上就被帶到比賽場地,9:00 準時開始

果然和學長說得一樣,五小時解八題

由於這場比賽不算 penalty ,我第一件事就先花半小時仔細讀完各題,用三色原子筆畫出測試資料,寫下大略實作方式

除了第一題 觀光景點(Sights) 拿到滿分外,其他各題真的不太理想

第二題分為五種不同 level 的 test case,我只做出 85% 基礎分,最後 10^6 因為不熟 Dev-C++ 的 C++98 開發環境,改成了自己覺得會對的方法,反而出現 0 / 100 全錯的情況

三、平均變異次數(Average Alternations)

竟然是用到期望值的概念

當時手算了幾個狀況,該想出來的才對 QwQ

五、智慧果

前幾天才教過 凸包 問題,當時用看的覺得有吸收到概念,沒實際寫過 code,果然不夠熟悉就是當場完全刻不出來,只拿了安慰分 10 分

六、串連重複(Tandem Repeat)

基礎字串搜尋,去年板中主辦的新北資格賽就考過了,果然沒學起來報應就來了,得到暴力法 40 分

後記

以前高二每週練習,就漸漸覺得打競程這件事不夠吸引我;今年完全沒有想準備競技程式的心情,十一月初的新北市賽完全裸考,這兩個月才為了全國賽開始加緊腳步練習

自己知道許多算法不是兩三天就學得來的,這次在全國 49 名參賽者中,只排了 30 名 拿參賽證明

去年三月的海選只拿了 44 名 ,離前二十的選訓營門檻還有段差距,繼續練習的話,希望明年三月也許有機會擠進前 20 名單內

“Success is not final, failure is not fatal;
it’s the courage to continue that counts.”
— Winston Churchill, British Prime Minister.

本名韋詠祥,習慣用英文 Sean 暱稱。
自國中開始接觸程式,至今善於組合各種技巧,用來解決生活周遭的問題。
以資安競賽、網路治理、個人專案為興趣。

Read Next

AIS3 EoF 心得 & Write-up

Read Previous

AIS3 暑期資安課程 - Pre-exam