Re: [請益] 請問國中生程式設計競賽入門

[Y78 (Y78)]

※ 引述《peanut97 (丁丁)》之銘言：
: 遇到一個國三生，有輕微亞斯伯格症，對電腦、程式非常有興趣。
: 應該說，只讓電腦進入他的世界。
: 家人已經放棄讓他以課業升學。
: 他想要做一個瀏覽器、想要修改Android作業系統，喜歡Linux環境、
: 喜歡MAC。唯獨程式語言不太會。
: 我正在教他PHP網頁。
: 未來想幫助他往「程式設計競賽」方向走，但是程式設計競賽好像比較硬。
: 請問「程式設計競賽」，有沒有比較好入門的方向呢？
: 對未來要走軟體的國三生來說。

版上有許多大大與一些我十分敬佩的學長也有在逛這個版
如果有哪裡講錯麻煩站內信或推文指正一下 <(_ _)>

先從「程式設計競賽」這件事情開始談起好了
先來了解一下有哪些程式競賽、贏了程式設計競賽可以幹嘛

因為國中生可以比的實在是很少，所以以下我所提到的都是國高中生
大部分都是高中生才能夠參加

1. NPSC
http://contest.cc.ntu.edu.tw/npsc2015/schedule.asp

台大舉辦的比賽，每年一次，有分國中組跟高中組
分初賽跟決賽，初賽是線上賽，在家裡或是任何有電腦的地方都可以比
初賽過關之後比決賽，要去台大計算機中心比賽，有好吃的點心跟餐盒
題目的話可以自己上這個網站找一下歷屆題目

國中組的題目一般來說不會太難，有一些字串處理或是模擬題
難題大概是DFS（深度優先搜索）BFS（廣度優先搜索）跟最短路徑
（參加的年代有點久遠，所以我不太確定）

高中組的題目難度就高了許多，DFS, BFS, DP（動態規劃） 都是基本
可能會出現一些比較特別的演算法，或是網路流(flow)、計算幾何之類的題目

我參加 NPSC 是從國二到高二
我高二是大概五年前的事情，所以算是有一點遠了
但 NPSC 我覺得滿不錯的，而且是少數國中生也能參加的比賽


2. 北市賽（地區賽）
http://contest.tp.edu.tw/?id=1412135239
升上高中以後，多一個地區賽可以比，我比的是台北市資訊能力競賽
我們都簡稱北市賽，其他的我記得有中區跟南區，東部跟新北我就不是很確定了
北市賽有名額限制，如果同高中有太多人想參加，會先比個校內賽（學校自己辦）
獎項分成四種：一等獎*5、二等獎*5、三等獎*10跟入選獎
前十名（也就是一二等）可以參加全國賽

這我高一有比過，有分成筆試跟上機
比重好像是30%跟70%，這我不太確定

3. 全國賽
各區的前十名來比
這我沒參加過所以沒什麼可以講XD
全國賽的前十名可以保送TOI（等等會講）

4. 台北市軟體競賽
http://tpc.taivs.tp.edu.tw/
高中高職都可以比，組別也不同
高中組題目跟其他比賽大同小異
我高二有參加過，那時候是在松山工農比

5. TOI
TOI就是臺灣資訊奧林匹亞研習營Taiwan Olympiad in Informatics
http://toi.csie.ntnu.edu.tw/

聽到奧林匹亞就覺得很厲害，因為這真的很厲害
上面講過，全國賽前十名可以保送這個研習營
另外20個名額會再舉辦一個入營考招生
進去以後一共30人，我們稱之為第一階段，簡稱1!

1!會到師大住兩個禮拜培訓，每天都上一些資結/演算法的課
每個禮拜都會有一個小考試，會決定你能不能到第二階段（俗稱2!）
我高一的時候有進1!
在裡面生活滿愉快的，因為吃住都不用錢，而且學校那邊可以請公假
請兩個禮拜公假XDDD

1!的大約前12名可以進2!，然後再培訓兩個禮拜
最後取前4名，就是國手了，就可以參加 IOI 國際資訊奧林匹亞
http://toi.csie.ntnu.edu.tw/main_01.php?ID=17
每年舉辦的地方都不一樣，2014在台灣辦過


以上五個就是高中生基本上可以參加的競賽
其中最重要的當然就是TOI
為什麼呢？因為如果你夠強當上國手然後有拿牌，可以保送任一大學的資工系
你想去台清交成任何一間都可以

如果沒有前四名，但你進2!而且名次在滿前面，也可以靠推薦的方式去推資工系
這個推薦跟學測指考都沒什麼關係，是另外一個特別的管道

所以，如果你把資料結構/演算法練到超級猛但是國英數超級爛，還是可以進112資工
但這種人極少而且超極端XD

談完了資訊競賽有哪些，來談談這些比賽考什麼跟計分方式
每個比賽大概會有六題以上，基本上都用英文代號，也就是pA, pB, pC, pD, pE...
答對叫做AC(Accept)，答錯叫做WA(Wrong Answer)
超時叫做TLE(Time Limit Exceeded)，其他還有一些我就不再贅述

一般的比賽時間大概都三個小時起跳
每一題的得分是：答對時間 - WA次數*20，沒答對的話則這題不加分不扣分
比賽的時候會有即時計分版，選手也看的到；但比賽結束前一小時會封盤
現場比賽的話滿好玩的，只要答對一題就會送你一顆氣球
你看誰前面氣球多就知道誰最神XDD

考試類型的話就是大家所熟知的資料結構/演算法
http://www.csie.ntnu.edu.tw/~u91029/ 列出了許多有用的東西
通常會用一個很生活化的方式包裝題目，讓你覺得比較有趣

像是這一題：http://tioj.infor.org/problems/1026
其實就是考你二進位轉換，但把題目包裝過
有些題目很好玩包裝的很好，你拆一拆之後會恍然大悟：阿！原來是這個！
就是那個 moment，會讓你覺得超級有趣（至少我自己這樣覺得XD）

或是這一題，http://tioj.infor.org/problems/1143
說穿了就是 BFS

或這一題：http://zerojudge.tw/ShowProblem?problemid=b127
題目落落長，但看穿了其實就是費式數列


講了這麼多，終於可以回到正題
程式解題這件事情，你要引起他的興趣的話，我覺得可以從兩個方向
第一個就是從利誘下手，跟他說「你這個很強的話可以保送台大資工喔」
第二個就是讓他真的愛上這些解題的過程

怎麼做？先讓他解一題看看
你先去各個online judge看一些答對率比較高的題目
找一題自己覺得有趣的又不會太難的，然後叫他解解看
解完了就再找一題，盡量找一些有趣一點的，試著引起他的興趣

或是你可以直接拿一些經典題，一步一步引導他
例如說經典的背包問題：
你現在有一個容量是100公斤的背包
你有一堆物品，每一項都有一個價值V、重量W公斤
每一項物品都只有一個，也就是你只能選擇拿/不拿
你要怎麼選擇，才能讓你拿到的價值最高？

我有一個原則是：先求有，再求好
一個最簡單的想法是：我窮舉不就好了嗎？
如果有n個物品，一共有2^n種拿法，保證可以找到解答

這時候可以順便帶入時間複雜度的概念
問他說：那如果n是10000的話怎麼辦？2^10000電腦跑不動耶
那就要想有沒有更好的解法
一步步提示他，接著一起完成這一道題目

光是背包問題就有一堆可以繼續延伸
像是剛講的0/1背包、無限背包、二維背包等等
有興趣的可以參考背包問題九講：http://love-oriented.com/pack/

除了這個，也可以教他最短路徑
最短路徑就有幾種不同的演算法，每一種的思考方法都不太一樣

或若你覺得這些太難，就從排序法開始吧
泡沫排序、插入排序、快速排序、合併排序、桶子排序...
每一種都有各自的想法跟想解決的問題

二分搜也是一個很好的入門
你可以說：現在你有1000個數字，如果我要問你：500在不在裡面，你要怎麼做？
他可能會回答：就從第1個掃到第1000個阿
接著你問說：那如果我要問你很多次呢？500, 501.., 600, 700在不在裡面？
他可能會回答：跟剛才一樣，每次問都掃一次
你就問說：那有沒有更好的方法呢？假如我們排序以後，會變怎麼樣？

話說我覺得用終極密碼來講二分搜還不錯，兩個有異曲同工之妙XD

如果以上都太難，就從一些基本的字串處理之類的開始
可以參考acm的一星題：http://luckycat.kshs.kh.edu.tw/
或是一些online judge比較多人答對的題目
寫完之後切記，一定要上傳！
為什麼？因為答對會超有成就感！成就感也是很重要的一部分
藉由這種線上解題系統，就可以增加成就感，而且有些還有排名
讓你知道你這題時間第幾名、code的長度第幾名
有時候會為了縮code長度用一些奇淫技巧XD

一步步引導，從慢到快，從無限制到有限制
從這些過程試著引起他對程式解題的興趣
試圖讓他為「阿！原來可以這樣」的感覺感到興奮
一旦引起他的興趣，他應該會沉浸在這樣的世界裡面

像是有一題我就覺得超級有趣
http://tioj.infor.org/problems/1513
你有一個數列，除了一個數字以外兩兩成對，找出那個數字
數列長度<=100000，0<=數字<=2^31

例如說：1 2 3 2 1，答案就是3
0 0 0 777 0 0 0，答案就是777

這題就很適合先求有再求好
你可以 sort 之後比a[i]跟a[i+1]，但你發現這樣不夠快
你可以 map 存起來之後檢查，但你發現這樣記憶體耗太多
正解是什麼就留給大家思考，我自己是很愛這個簡單但神奇的解答

最後附上一篇強者我學長的文：Re: [討論] 所以練acm都底有啥好處？
https://www.ptt.cc/bbs/Programming/M.1411474900.A.746.html


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.216.67.187
※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1451998694.A.9BA.html
推 ccpz: 那些比賽飲食通常很豐盛，一不注意就是吃吃吃XD
推 ccpz: TOI的規則現在不知道如何, 當時有年級保障, 高一有努力過也
→ ccpz: 有機會進
→ Y78: 我那時候也有，高一保障四個，現在就不太確定了
推 ccpz: 能力夠的話，其實也可以直接去刷 google code jam
→ ccpz: 不過時差比較麻煩orz
推 Eric0605: 推 這篇文章可以m了
推 jinmin88: 最後那題感覺只是有沒有想到的問題 不過XOR的確很神奇
推 Bencrie: 新北有。我是還沒升格前有參加過，那時候完全無法跟北市
→ Bencrie: 比。
推 hsnuonly: 哭哭 有點後悔高中沒去打比賽
→ lNishan: map 是 O(log n)吧?
→ lNishan: 身邊好多例子是大學才開始的 現在也很強耶
→ lNishan: 心態跟態度才是最重要的
推 KJFC: 推
推 fenzang: 我們那年代TOI跟北市賽沒token, 一次定生死XD 現在有toke
→ fenzang: n之後互動題就多起來，然後greedy幾乎沒有活路了XDD 所以
→ fenzang: 我覺得方向還是有一點點改變啦~ 但是本質還是一樣就是了
※ 編輯: Y78 (61.216.67.187), 01/06/2016 19:59:07
→ jenny2921: 專業推 所以國中就只有NPSC嗎？我也只想得到NPSC耶～(
→ jenny2921: 還有google code jam應該也是不限年齡XD)
→ viper9709: 推~感謝分享
推 vgod: IOI國中其實就能參加，只是台灣沒管道讓國中生進選訓營...
推 devilangel: 也歡迎參加HP主辦的CodeWars