BB's Blog - A blog by a happy programmer

寫於 TOI 2017 三年後

好懷念歐,三年前的資奧選訓營。 選訓營對當時的我來說還是個充滿未知的地方,二階、國手更是看似遙不可及。聽學長介紹各個不認識的大神,每個都是經驗滿滿,進過不只一次選訓的強者。 選訓營是個很嚴肅的地方,一有差錯影響的可能是長遠的未來。但這年的選訓看起來卻還是歡樂的,大家好像都會做點事讓自己不那麼緊張,也因為這樣,讓第一次進選訓的我過得很快樂。如果這年的選訓氛圍跟往後兩年一樣,那或許事情會有完全不一樣的發展。 高中三年裡我進了三次選訓,但高一這次是絕對是影響最重大的。選訓營的氛圍讓我能夠每天都用盡精神去想題目,解著從學長那邊拿到的高難度題目挑戰自我。我的能力在這段過程中有非常快速的成長,不單只是技術上的,更大部份是抽象的,對題目的觀點以及思考方式等。 這次的選訓,不敢說影響到人生,但不可否認的是它確實改變了往後的五年、十年或更多。 再過幾天就是今年的選訓,身為已經跟選訓無緣的競賽老人,我能給學弟妹的建議大概就是好好把握機會吧。不要把名次看的太重,在選訓中成長並學到點什麼才是最重要的。不要忘記初衷,想想當初為什麼會想打競賽。為了成績嗎?那好吧,就努力爭取成績吧。但我相信更多的是因為覺得有趣,覺得有成就感,熱愛程式才會想打競賽的吧,那就算是在選訓裡,是不是也應該要努力貫徹初衷呢? 這篇文寫於 TOI 2017 報到日的三年後,靠著這年的 TOI / IOI,現在的我才得以進入全台最好的資工系。現在的我,是否還有當年的衝勁,又是否還有貫徹著初衷呢? 希望我現在做的選擇不會讓未來的我後悔,就像過去的我沒讓現在的我後悔一樣。也祝福學弟妹選訓順利,一起為了夢想與未來努力。

IOI 2019 國手培訓日記 Day 21 - 完

今天是國手培訓的最後一天,唯一的行程是早上的說明會。我們一樣在師大的學生餐廳吃完早餐之後就到教室幫忙排桌椅。今天除了李教授跟吳校長沒有出席,其他團員都到了,我們四個人的家長也全數到場。等人到齊之後老師就簡單介紹了航班、當地的一些資訊跟文教參訪的行程。今年去的國家是亞塞拜然,是個一般台灣人不太會去的地方。由於一些政治因素,感覺我們的行程還有一些不確定性,希望我們能夠順利抵搭當地,順利比完比賽,再順利回到台灣ww 說明會之後有提供簡單的午餐,大家吃飯聊聊天就解散了。回家的路上順路去園區銀行領了一些美金,準備要去當地換錢用的。剩下這一個禮拜就好好維持手感,做好準備,還有希望比賽一切順利啦~

IOI 2019 國手培訓日記 Day 20

今天因為師大分部停電,所以是個在外流浪 (X) 的一天。早上搭捷運綠線的支線去小碧潭,吃「宜家家居新店店」的早餐。前陣子很常聽到 IKEA 新店店的名字,因為唸起來很有趣,這次終於親自造訪啦~ IKEA 的早餐一份 49 元,剛好在選訓的早餐額度內,不過我另外拿了一份生菜跟飲料,所以稍微再多花了一些錢。吃完之後大家想說進去看一下聽聞許久的「IKEA 鯊魚」,稍微逛了一下沒看到,一問店員才知道已經賣完了,超難過的 QQ 小碧潭的捷運班距超長的,我們等了十分鐘左右才等到車,搭回大坪林待在旅館附近的星巴克。早上花了點時間用 Top Tree 寫掉昨天的某題,一次 AC 超開心的~ 中午吃完午餐之後就回到旅館耍廢,睡了一小陣子,起床寫程式寫到吃飯前。晚餐在旅館附近吃完之後就一樣回房間耍廢啦~

IOI 2019 國手培訓日記 Day 19

今天早上我們拿 CF 上的 CEOI 2019 Day 1 來打模擬賽,由於上次寫 CEOI 的時候剛好戳到特別水的場,所以這次就稍微抱持著對難度的懷疑。今天的三題題目剛看完時的感覺:第一題完全沒想法,第二題一看就有大膽的想法,第三題則是感覺特別水。比賽過程就懶得寫了,剛嘗試寫了一下結果發現國文不好真痛苦。最後三題的狀況大概是這樣:第一題只喇了點分數,不過沒有把想要的分數拿完,由於想法的正確性感覺很沒問題,所以懷疑我是第八百萬次寫爛割點了。第二題原本大膽操作分塊的作法不會寫,所以就改成想要重心剖分套線段樹的毒瘤作法。線段樹寫完的時候 debug 超久,花了一個多小時才發現原來 new 出來的陣列不會初始化為零,看來我該回去語法班了ww 最後因為時間不夠,所以就沒有寫重心剖分,另外賽中的時候也有想到 Top Tree 的作法,可是同樣基於時間問題就沒寫了。這題我們三個人分別用了樹鍊剖分(蔡旻諺 100 分)、重心分治(我,不過沒實際寫到)跟 Top Tree (師宇,不過寫爛了),感覺超酷的,我是最喜歡 Top Tree 的解啦,而且還不用線段樹,感覺輕鬆搞定。第三題就單純的在壓式子的計算複雜度,官解還有加上壓常數的部份,感覺有點不精湛。有趣的是,這題的 code 在我的電腦跑特別快,每次在 CF 上測,都需要花至少三倍的時間,讓我在壓時間的時候感到很困擾w 總之最後收在總分 179,還算可接受的數字,當然能更高的話更好啦ww 由於暑假期間我們選訓常用的那間教室平日有人上課要用,所以我們最近都在另一棟大樓。今天是最後一個培訓的平日,離開前拍了張照片紀念,順便當作今天的封面啦~ 由於昨天晚餐滿好吃的,所以我們今天又去吃了一次。晚上回到旅館一如往常的耍廢,還有發現選訓再兩天就要結束了,IOI 也倒數 8 天啦~

IOI 2019 國手培訓日記 Day 18

今天比前幾天更耍廢了ww 早上一樣去師大吃早餐,吃完回到教室就聽了一點題目跟寫了點 Code。快中午的時候開始弄申請我爸信用卡副卡的資料,主要就印申請文件下來簽名掃描而已。我把要印的東西傳上 ibon 的雲端列印,然後我就默默的走到全家了ww 到全家之後機器按一按才發現 「Duck,ibon 是 7-11 的」,只好再默默的走回 7-11。印完之後發現忘記帶筆,就只好走回教室寫完資料簽完名再回 7-11 掃描。 上面的事情弄完就大概吃午餐了,吃完睡了一下、想想題目跟聊天,然後就晚餐時間了呢www 晚上去吃旅館附近的滷肉飯,還滿好吃的,順便貢獻了今天的封面圖,不然沒圖可放阿 QQQ 回旅館之後大多時間都在看清大營隊的比賽,然後就沒做什麼其他事情了。總之今天真的是有夠耍廢,我也不知道有什麼好寫了ww

IOI 2019 國手培訓日記 Day 17

今天是愉快(?)的爬山日,早上起床之後先去旅館附近的永和豆漿店吃早餐,接著就搭捷運前往象山站跟教授們會合。這次帶我們去爬山的是王弘倫教授跟張經略教授,前者感覺有在運動,後者則是每週都去爬我們今天爬的山。在捷運站碰面之後先搭了一小段的計程車到登山口,上個廁所之後就開始今天的行程。今天走的是虎山生態步道、九五峯、四獸山步道跟象山步道,基本上都是有樓梯的步道(少部份地方除外),不過有些地方的樓梯比較陡,實在是有點喘。 然後雖然說是有帶著毛巾,不過因為流汗流很多,爬到大概一半的時候毛巾就已經幾乎全溼了。我們在上山後沒多久遇到一位阿姨(雖然說年紀感覺滿大的,不過就還是稱作阿姨好了),一開始打個招呼聽說我們是要念台大的學生之後,就開始出現奇怪的話題,例如問我們能不能用一句話解釋微分(恩對就是微積分那個微分)、問說數學為什麼漂亮、說她會讀心術、還有說她有得冠軍的必勝法則之類的。這位阿姨還跟我們走了全程,雖然說是不排斥啦,可是聽了快兩個小時還是有點小煩,這時候就感受到戴耳機的好處,直接把聲音濾掉了大概一半。我是覺得這位阿姨不是等閒之輩啦,畢竟她講的東西不像是路上隨意一個阿嬤講的出來的,可是她真的有點吵 QQ。今日全程 5.5 km,爬升高度 373 m,用時 2 小時 36 分鐘。 從象山步道下山之後我們先路過了一下全家,接著就到象山站搭捷運回公館。中午在台大附近吃吃,下午就回飯店洗澡睡覺。今天真的有夠累,一覺睡到吃飯前,晚點再來繼續睡,希望明天起床之後不會腳很酸ww

IOI 2019 國手培訓日記 Day 16

今天依舊沒課,所以我們又找了一場 POI 來打模擬賽。這次王師宇有透過解題人數特別找難一點的場(跟昨天比),挑好場次 Bert 也印好題目之後就在一個奇怪的非整點時間開始比賽了。 開賽一樣先把三題題目都看完,把模板打完再開始思考。其中一題很簡單,只是一開始不小心多套了一個二分搜,浪費了點時間改,在大概開始 45 分鐘的時後拿到第一個 100 分。剩下兩題有一題連多項式解法都想不到,所以就先寫另一題。實際 Coding 時間大約 40 分鐘,加上找爛 Bug (輸入寫爛)的時間,在開始兩小時的時候拿到第二個 100 分。 稍微想一下最後那題依然沒有能拿分的寫法,索性把題目放到手機裡後就先走去買午餐。邊走邊在想到底要怎麼把那題壓到多項式作法,想著想著就在等餐的時候想到了。拿到餐之後就在走回去的路上想細節,還不小心忘記拿餐具多繞了一趟回餐廳拿,實在是有夠蠢。 回到教室之後就速速開始實做剛想到的東西,還很順利的沒出什麼大 Bug。不過在快要寫完的時候就看王師宇已經開始睡覺了,想說他應該也是 300 之後沒事做,我就繼續趕工我的最後一題。大概在比賽開始後 3 小時 20 分鐘解決掉第三個 100 分,剩下時間打算稍微耍耍廢,就把之前沒看完的《搖曳露營》解決掉,還有逛逛 FB。 比完之後很意外的發現師宇、Bert 跟蔡旻諺都是 200 多分,這好像是我這幾次模擬賽第一次打贏三個人吧,表示開心。 下午聽老師說這次出國可能要帶一些現金,主要是行程的變數有點多,不確定會不會有突發的事情需要出錢。所以就想說是不是要順便來辦張郵局的 Visa 卡,這樣就不用帶太多現金,國外消費也比較容易。不過似乎申辦有點小麻煩(需要家長雙方身份證正本的樣子),這幾天再確認一下有沒有什麼好辦法w 下午離開教室前 Bert 去買了一碗泡麵,很過份的在密閉的教室裡吃,蔡旻諺表示他看了也很想吃。 今天晚餐去景美捷運站附近吃甘泉魚麵,想到今天的日記好像也沒有圖片能用就又拍了晚餐來當圖。早上有人說這快要變成國手食物日記了,其實沒有好嗎,文字的部份通常沒什麼提到食物(就稍微提一下而已),照片也只有其中幾張是食物,畢竟生圖片超難的,有時沒梗就只好拍晚餐ww 晚上回到房間後蔡旻諺還真的泡了泡麵吃,整間房間都是泡麵的味道。真是有夠過份的,下午吃的也不是我,整天下來被攻擊了兩次,要吃也去隔壁房間熏 Bert 嘛 (X) 明天要被帶去爬山,希望不要累死w

IOI 2019 國手培訓日記 Day 15

根據課表,從今天開始到這裡拜天培訓結束都沒課了,所以應該就是每天刷題目跟打練習賽,今天四個人挑了 POI (波蘭資奧)的題目來打。這場的題目比想像中簡單不少,開賽之後雖然不小心雷了一些小地方,還是很快就拿到兩百分。剩下的三個多小時就都在寫剩下一題感覺很 DP 的題目。花了快兩個小時寫加 Debug 才發現假解,一開始想說還簡單證明了一下,沒想到問題是出在自己以為顯然的部份 QQ 我就趁這個時候先去學生餐廳買午餐外帶回教室,邊走邊想有什麼好方法,結果剩下的時間還是一直想不到,只好先把複雜度調高一點拿一半的分數。最終結束的時候拿了 250 分,感覺跟沒做事一樣www 下午台北下了滿大的雨,讓我們都超不想出去吃晚餐。大概六點多的時候看雨也變小了就出發回旅館,晚餐投票一致通過去吃八方雲集。稍微算了一下,我們國手培訓在台北的晚上有一半是吃八方ㄟww 畢竟要找到大家都接受的店超難的 QQ 晚上回到旅館之後依舊耍廢,然後在猶豫到底要不要來寫 Top Tree 的教學,表示有點懶 QQ

IOI 2019 國手培訓日記 Day 14

今天早上也是王炳豐老師的課,由於老師給的三題裡面有兩題師宇已經寫掉了,所以我們就都在討論剩下那題噁心的幾何題。題目基本上就是問說給你兩個分別不自交的任意多邊形,你要找到一種讓兩個多邊形接觸但不重疊的方法,使得接觸的邊總長度最長。 王師宇跟 Bert 在房間的時候就有先稍微討論過了,所以我跟蔡旻諺就另開對話,最後兩邊都有得到一個感覺可行的解,只是沒有人想寫,因為真的太噁心了。是說 Bert 一直在講說「這就跟『蛋和飯』一樣,因為你把蛋放在飯上的時候蛋就會跟飯完全貼合,接觸面積會很大」,我是覺得這跟題目沒什麼關係啦,不過他好像也不是第一次講奇怪的比喻ww 下午的時候除了我以外的三個人在教室後面打桌球,他們把桌子併一併中間夾東西就變桌球桌了(之前選訓的時候也有做過)。我那時候好像在耍廢吧,也刷了一點 Codeforces 的題目。 吃飯前在寫之後薪傳營要給學弟妹的資訊競賽簡介,不過還沒寫多少,剩下的等晚上再繼續寫。 我們昨天晚餐本來想去吃鐵板燒,可是人真的太多了,就決定今天早點離開去吃。到那家店的時候人還是不少,等了大概 2-30 分鐘才吃到,不過還不錯吃就是了。 今天晚上有 AtCoder 的比賽,不過等這篇文發出去的時候就已經開始了,我還需要花點時間寫下午沒寫完的競賽簡介,就不打啦w

IOI 2019 國手培訓日記 Day 13

附圖為 top tree (一種分解樹的方式) 與 Tree Top (一種蘋果汁)的合照。 今天有點累,就不寫太多東西了 QQ 早上是王炳豐老師的課,一樣是把題目給我們之後先讓我們思考和彼此討論,之後再聽我們的作法跟給一些建議。不過雖然這次的題目一樣是來自 ICPC 的世界決賽,題目卻莫名的偏簡單,看完題目之後滿快就解決掉了。另外明天的題目王師宇已經寫掉兩題,剩下一題好像爆炸難。 今天下午沒課,剛好上次王炳豐老師教的 top tree 還沒有寫過,昨天又已經和蔡旻諺討論出了一些適合的題目,就運用今天下午來寫寫看。最後在 Tree Top 的加持下,終於把 top tree 寫出來啦~ 之後還花了點時間翻了 top tree 的論文,感覺是個很神奇的東西,或許得再花點時間研究w 晚上吃飯的時候聊到有些手機的鏡頭會凸出來(我們有兩個人的手機是這個狀況),加上手機殼之後就可以解決掉這個問題。然後就開始了今天的辯論主題「如果手機買的時候就附了手機殼,那這個手機殼是不是預設會被使用的」。總之我有點累,不想打吵架細節 (?),總之吵了快半個小時,最終結果就是我們對「預設」的界線不同,然後就吵不下去了XD 吵架好累ww 晚上就跟蔡旻諺聊聊天,用用電腦,以及趕在 12:00 前把沒寫什麼東西的日記寫出來。我好廢歐,連日記都要不知道寫什麼了QQ