11月19日至20日,由學院1024工作室ACM俱樂部指導老師張自力指導的一支參賽隊伍參加了第47屆ICPC國際大學生程序設計競賽(合肥站),最終奪得銅牌。隊伍的三名成員分別是我院計科專業2019級種佳琪、2020級楊碩和楊沛霖。(隊伍名:錕斤拷燙燙燙)
這是ACM俱樂部自2020年成立以來第三次在國際頂級賽事中獲得獎牌。
本次比賽,共有來自清華大學、北京大學、華中科技大學、武漢大學等多所高校共451支隊伍參賽。此次比賽獲獎難度較大,區域賽獲獎隊伍原則上僅取前210名。由於疫情原因,比賽在線上進行,過程中設置有三個機位實時監控隊員的正面、側面以及比賽場地環境,並對所有畫面錄屏;待比賽結束後,舉辦方會對所有隊伍提交的代碼進行查重,並根據視頻對有作弊嫌疑的隊伍進一步排查。
國際大學生程序設計競賽(International Collegiate Programming Contest, ICPC)在教育部認可的56項全國大學生學科競賽中,排名第四位。ICPC競賽已經有40多年的歷史,該項賽事是世界公認全球最具影響力、有「程序設計的奧林匹克」之稱的賽事。該競賽所頒發的證書被世界各著名IT公司、各知名大學所認可。賽事由各大洲區域預賽和全球總決賽兩個階段組成。
ICPC競賽規則:隊員以團隊的形式代表學校參賽,每隊至多3名在校生組成,原則上每站區域賽一所學校最多只有3支隊伍參賽,每個隊員一年最多只能參加2站比賽;比賽時3名隊員只能共用一台電腦,時間為5個小時,題目有10題左右,試題描述為英文,採用C/C++、Java和Python編程語言,每支隊伍的成績在排行榜上實時顯示。
ICPC競賽題目的知識點大致可分為五類:第一類基礎算法,分別有(1)枚舉、貪心等基礎算法,(2)背包問題、樹形等動態規划算法,(3)深度優先、廣度優先等搜索算法;第二類數據結構,分別有(1)棧、隊列等簡單數據結構,(2)字典樹、線段樹等樹形結構,(3)KMP、後綴數組等字符串,還有並查集,散列表等;第三類圖論,分別有(1)Dijkstra、Floyd等最短路徑算法,(2)Prim等生成樹算法,(3)匈牙利算法等匹配問題,(4)最大流、最小割模型等網絡流算法,其他包括拓撲排序,無向圖,有向圖等。第四類數學,分別有(1)素數、同餘等數論問題,(2)加法原理、排列組合等組合數學問題,(3)高斯消元法、矩陣法等計算方法,其他還包括博弈論、線性規劃、多項式與快速傅里葉等問題;第五類計算幾何,分別有判斷線段相交、判斷直線相交等問題。