BB's Blog - A blog by a happy programmer

IOI 2019 國手培訓日記 Day 11

今天是蔡孟宗教授的課,由於之前選訓的時候就覺得這個教授很厲害,上的課也很有趣(我們會被電的很慘的那種),所以就一直還滿期待的。早上的主題是 Greedy 相關的演算法,提到了 weighted matroid、submodular function maximization 以及 local search 三個類型的簡介跟題目證明。下午則是講了排容跟「不用線性規劃的線性規劃」,也是搭配題目跟證明。這位教授的課雖然也有不少不在 IOI 大綱內的東西,可是教授都會給我們不少的時間思考跟討論,比較不是單純的把資訊丟給我們,而這些思考感覺也是很好的訓練,雖然我都不會就是了QQ 今天午餐是去交大女二舍餐廳吃燒臘,比想像中的好吃w 吃完之後還在交大校園逛逛才回去上課。晚餐則是我們回到旅館後拜託輔導員去幫忙外帶拉麵,雖然說還是內用比較好吃,不過上了一天課之後真的不怎麼想出門。 颱風的部份今天下午是有下一場不小的雨,不過沒有下太久,下課前就停了。其他時間都是艷陽高照,在外面的時候實在是有夠熱。再來就是希望明天不要下雨啦,颱風天真的超煩的w 然後是說明天就要回台北了呢,今天晚上再洗了一次衣服,理論上可以剛好撐到回家那天,就不用用到台北那間旅館有夠貴的洗衣機了~

IOI 2019 國手培訓日記 Day 10

今天早餐大家決議去吃小木屋鬆餅,久沒吃了覺得還滿好吃的~ 然後外帶的好處是可以在有冷氣的教室吃,不像前兩天的早餐店算是半開放的空間,而且還可以邊吃邊看電腦。 今天上課的是蔡錫鈞教授,一開始講了今年選訓營某題模擬考題的解答跟證明(基本上就是請你給出一個介於最小生成樹跟最短路徑樹之間的trade off),感覺還算輕鬆理解。接著進入到一些跟流有關的問題之後我就迷失了,總之就是一整個沒跟上,只記得好像有看到什麼跟 YP 有關的式子。 由於我們的課可以旁聽(也有一些交大的學生出現),所以崔浩堂就來跟著聽下午的課。下午的課比早上友善多,雖然又是一堆機率問題(已經連續三天了呢),不過至少都有些好玩的分析,只是教授有時會把重要的東西跳過,然後不重要的東西講超久ww 下午下課我們離開教室前在那邊又聊了一陣子的天,以下是一段有趣的內容:狀況是這樣的,有個某 A 因為會考畫錯卡,沒有檢查到,讓國文從 A++ 變成 B++,所以學校掉了不少;另一個某 B,在重要的程式比賽因為題目看錯,把輸入寫爛,結果沒有檢查到,讓之後有不太完美的結果。在這兩個案例中,同樣是「沒檢查到」,到底哪個比較令人同情或是說哪個自己的問題比較大呢?然後這個問題吵一吵,變成在討論下面三者的異同: 寫出的程式不如你希望的運作(也就是一般而言的程式寫出 Bug) 你為題目設計了一個演算法,也把程式寫的跟你設計的演算法一樣,只是你的演算法對那個題目而言是錯的 你為你看到的題目寫出了一個正確的演算法,程式也是完美的,可是其實你看錯題目,也就是這支程式能正確解出你看到的題目可是不能解決真正的題目 總之我到最後已經不知道到底在吵什麼了,不過真的很好玩ww 晚上回飯店簡單吃吃晚餐後就開始耍廢了,懶到連日記都不想寫,拖到快跨日了才在寫ww 明天是轟炸課,希望晚上睡飽明天有精神,不要上到沒力w

IOI 2019 國手培訓日記 Day 9

說真的,今天沒什麼東西好寫,我甚至什麼照片都沒拍,害我在寫這段話的時候還沒有任何能當封面的圖片,難過QQ 早上一樣去昨天那家早餐店吃早餐,吃飽之後到教室教授已經到了。今天上課的是清大的韓永楷教授,一開始上的是說「給你一堆文本,要你在線回答包含目標字串 $P$ 的文本有哪些」,還有一些這個問題的延伸。主要講了一些資料結構跟複雜度分析,不過由於是以做理論的方向去講,所以像 RMQ 就會直接當作是 $< O(N), O(1)>$ 的ww 接著跟昨天一樣繼續上了一些隨機演算法,有一些是昨天的優化,有一些則是把昨天快速帶過的東西補完,有些則是以前聽過的東西,不過都還滿有趣的,也都有好好證明,難度比昨天簡單了不少。 中午一樣去二餐吃,在餐廳捕獲野生的崔浩堂,吃飯的時候聊聊天,快吃完的時候他就先走了。 下午教授開始上一些機率跟期望值相關的公式,雖然感覺也有用,不過因為太數學了實在是有點想睡覺 QQ 晚上的時候把大家帶去清大對面吃甘泉魚麵,吃完再走光復路回旅館。這感覺真的超奇妙的,明明這幾天的活動範圍、吃的東西都是平常會去的地方跟會吃的東西,結果卻住在旅館XD 回到房間之後就繼續學了點日文還有耍廢,順便裝了日文的輸入法。來隨便打句剛學到的東西好了: はじめまして、私は Brian です。(很高興認識你,我是 Brian。) 希望沒有秀什麼下限,有什麼問題的話再拜託各位大大跟我說了w 最後由於沒有照片可以發,就來拍張外面的夜景吧~ 不過由於上傳的照片有自己先壓縮過,可能就沒原本那麼漂亮了w

IOI 2019 國手培訓日記 Day 8

今天早上吃的是交大校門對面的早餐店,吃完之後就慢慢走到上課地點(工程四館),這幾天的教室實在是有夠大,看起是大概可以容納六七十人以上,然後大家一進教室就開始往有插座的地方跑XD 早上上課的老師是張以潤博士,似乎是剛唸完回國,過陣子又要再出國念博士後。老師來的時候禮拜四要上課的蔡孟宗教授也同時出現了,後來還有幾位交大的學生進來,他們都一起聽了一整天的課,超酷的w 老師一開始先打聽了一下我們大概會哪些東西之後就開始今天的主題:「機率方法」,簡單來說就是被滿滿的數學跟證明轟炸,然後偶爾秀一下我的數學下限,還聽了超多遍的 “With High Probability”。 中午在交大二餐簡單吃吃,回到教室前繼續唸了一下日文,覺得日文有夠難,至少我覺得背五十音的部份是如此,記憶力不好好難過QQ 下午是同個老師的課,上完之後還沒想到晚餐要吃什麼就只好先走回飯店。輔導員表示他可以騎車去幫我們買晚餐,最後結論是實驗學生常吃的義大利麵店,點完餐就小睡了一下補充早上上課轟炸消失的體力。 晚餐吃飽之後其實就沒什麼事情要做,晚點看要不要來寫點題目,還有該去洗衣服了w

IOI 2019 國手培訓日記 Day 7

今天的凌晨打完 FB Hacker Cup 之後大概五點左右離開旅館的 Cafe 準備上樓回房間,這時發現原來已經要天亮了呢,就隨手拍了一張「睡覺前」的天色,回到房間設好鬧鐘就趕緊睡覺了。 早上 8:40 起床,吃完飯店早餐之後在房間稍微耍廢一下就出發去搭高鐵。中午 12:00 開始有一場 JOI Open 可以打,就在高鐵上把題目快速的看過一遍,利用回師大的時間把題目想一想。剛回到師大的時候就被另外三個人抓去吃午餐,不過因為早餐晚吃加上吃了不少,所以午餐就沒吃太多,剩的錢分給其他人用,師宇就點了「西西里雞腿堡加蛋加三片起司」,感覺超奢華的 (X) 吃完就把握時間繼續寫 JOI,經過數個小時的思考加努力,拿到了一題正確的 100 分跟一題似乎是假解的 27 分,如果把因為各種交通時間而來不及寫到的算進去大概是 166 分吧,不算太慘,不過也沒多好ww 接下來五天的課程是在交大,所以下午就出發前往新竹,一如往常的高鐵花的時間少於在新竹內花的交通時間。這次住的旅館是最近這兩年交大舉辦資訊全國賽時訂的旅館,距離交大非常近,又非常高級,只是多少有點貴XD 我們要在這住五個晚上,感覺就超棒的~ 晚上大家懶惰就在旅館樓下的麵店速速解決掉晚餐,回到房間躺上床就快睡著了,晚點看要不要早點睡吧XD

IOI 2019 國手培訓日記 Day 6

早上起床看到昨天晚上 Codeforces 的比賽結果,終於爬回紅了,也順利拿到了台灣隊裡面積分最高的位置,表示開心。欸等等,是不是不應該開心阿,讓我們來看看前年的選訓名次、CF 積分名次、以及 IOI 的台灣隊相對名次對照表(詳見 Blog),再看看今年目前的選訓名次跟 CF 積分名次,巧合嗎?我不這麼認為,看來我 IOI 要拿台灣隊最後一名囉 (X) 到師大之後一樣先去學生餐廳吃早餐,接著就回教室繼續討論王炳豐老師的題目,題目都是 ICPC 世界賽的歷屆題目。題目大概在老師到的半小時前討論完,等老師到了之後就跟他討論我們的作法。有一題我們很努力的弄出會 AC 的確定性作法,結果官方解答竟然很暴力的做,然後寫上「根據機率,應該不會做太多次,而且我們也構不出會爛的測資,所以這樣就是好的了」,老師跟我們都表示很生氣ww 早上還順便把一題 IOI 官方測試題的互動題寫掉,現在只剩下一題普通題跟 Output-Only 題的一分(已經拿到 99 分)要寫了。中午吃完午餐之後就繼續想練習賽的題目,不過一直都沒有什麼進展。 這幾天有一位平常住在美國的親戚回來台灣,所以今天晚上在高雄有一場家族聚餐,剛好選訓營今天下午跟明天早上沒課,所以就順利的跟選訓請了假。今天大概下午兩點的時候離開師大,搭高鐵下高雄,五點多吃飯,現在吃完九點多回到飯店。 是說剛好想到算了一下,我這個禮拜七天(禮拜一到明天禮拜天)總共搭了(新竹 - 台北)、(台北 - 台南)、(台北 - 高雄)各兩趟(就去回各一),花了大約八個小時在高鐵上,真是浪費青春阿(X) 等會半夜一點到半夜四點有 FB 的比賽,差不多要先睡了,12:30 再起來準備比賽。到底什麼爛時間阿ww 希望不要打太爛害我白熬夜,然後也希望明天不會精神太差w

IOI 2019 國手培訓日記 Day 5

由於早上是王炳豐老師的課,所以在上課前有比較多的空檔時間,剛好 IOI 官方測試題組裡面昨天說消失的 Output-Only 題又放回去了,所以我們四個就開始研究,喇喇分順便研究怎麼構造滿分解。

拿到大概 90 分左右老師就來了,今天講的是我們期待已久的 Top Tree,一種類似重心剖分,同樣可以把一棵樹分割成最多 $O(log(N))$ 層的分解演算法。高一聽到老師講這個算法的時候只覺得很有趣,但是幾乎不記得作法,這次聽則是比較有感受到精隨,實做的部份就這幾天有空來寫寫看吧,或許要多買個幾瓶 Tree Top 蘋果汁來充足 Top Tree 的信仰才能夠順利寫出來。

今天中午一樣去學生餐廳吃,不過今天發現校內的用餐額度降到 90 元了(不再是之前吃的 100 元),王師宇昨天點的本來是「西西里雞腿堡不加蛋加起司」以及「咖啡鮮奶不加咖啡」,今天他只好換成「西西里雞腿堡不加蛋」,飲料不變,師宇表示「我的起司被剝奪了」,莫名的有點好笑ww

中午去學生餐廳吃完午餐之後就收拾東西,搭公車去西門町拿上個月訂做的西裝。我們實在是運氣有夠差,已經連續三年領西裝那天都下雨了呢。領西裝比量西裝那天快速了不少,就試穿一下,拍拍照就差不多了。量完之後我們先回去師大把西裝放在老師的辦公室,這樣之後幾天去新竹才不用帶來帶去,唐博彥則是直接拿回家,我們再到會館附近的八方會合吃晚餐。

晚餐吃完早早回到房間,晚上 10:30 有 Codeforces 可以打,理論上休息一下精神沒問題的話應該會打吧,至少維持一下手感w

IOI 2019 國手培訓日記 Day 4

今天早上 7:50 起床,預計 8:00 在會館一樓集合。我跟蔡旻諺經過師宇他們房門的時候蔡旻諺問我要不要敲門叫師宇,我想說當時已經 8:01 感覺遲到了,他們應該已經在樓下了,所以就說不用吧。接著我們還等了超久的電梯,第一次來的時候人太多,第二次來的時候是清潔人員搬東西把電梯塞滿了,等到第三次電梯來才順利下樓,到一樓已經 8:06。結果沒想到一樓什麼人都沒有,師宇他們大概五到十分鐘之後才跟輔導員下來,師宇表示他們想說我們要下樓的時候應該會敲他們的門,所以他們就待在房間等了www 好不容易人到齊之後我們就慢慢的往公車站走,由於蔡旻諺要跟師宇討論題目,我就跟唐博彥走在前面,我們兩個到公車站的時候陸續看到了兩班能搭的公車開過去,可是師宇他們還沒到我們就在那繼續等,沒多久師宇就傳訊息說他們不小心走到捷運站去了www 真是的,早知道我們就先搭前面的公車不等他們,害我們多花了五六分鐘在等下一班公車ww 大概 8:40 左右到師大分部之後我們先去買早餐,這時看到我有老師的未接來電,打回去問才發現慘了,原來是 8:30 上課阿,我們看課表的時候都沒在看時間,以為是九點,只好等早餐做好之後趕快趕回教室。總之今天早上還沒上課就已經各種雷了QQ 早上教授給我們寫了一些題目,也跟我們聊了一些天,順便把教授給的題目推廣了一下。聽說我們之後還有機會去爬山,我們也跟教授說或許可以去遊樂園文教參訪,超期待的XD 吃完午餐回到教室之後發現門上貼的公告,也就是 Blog 的封面圖,上面寫著「近日教室部份電腦 “CPU” 遭竊,…」,我們看到笑到快翻過去了,到底為什麼會 CPU 被偷啦ww 中午吃完午餐小小休息了一下,緊接著下午四個人揪團打了模擬賽,用的是 JOI 2017 的 Day4。整體思考感覺不太優,尤其是一題可以大膽的水題我卻被外層的幾何包裝卡住了ww 另外一題編碼題則是完全沒有想法。打到最後剩下大概一個小時的時候大家就已經沒什麼動力繼續寫了,直接在前面白板上討論題目。 大概同個時間我們也終於收到這次 IOI 的官方練習題的資訊了,題目除了一題水互動題以外,剩下的題目都還沒什麼在想,另外還有一題 Output-Only 的題目在剛開 Judge 的時候有看到,沒想到過一兩個小時再上去系統看就已經不見了,可能是出了什麼問題吧ww 總之等會日記發出去之後再來好好想練習題吧~

IOI 2019 國手培訓日記 Day 3

今天早餐吃完之後就從成大會館走去台南火車站,搭火車到長榮大學車站,跟吳邦一教授在車站見面之後走到會場報到參加開幕式。報到的地方是按照學校分的,極度意外的是我們竟然也有報到的地方,桌排上寫著「IOI」,可是之後系統上寫的卻是「TOI」呢,不過不太重要就是了w 開幕式大概就是聽聽致詞,聽聽規則說明還有合照。早上剩下的時間是測機,我大概確認了一下我開賽需要做的設定,包含 vimrc、系統快速鍵、編譯腳本跟打模板之類的,測題目的時候還有一題出大 bug 找了很久,結果題目還沒測完就結束了QQ 吃完午餐就是正賽了,由於這次比賽我們是自己一組的非正式隊伍,加上要模仿資奧的比賽性質,我們四個人的分數不會顯示在記分板上面,於是我們自己訂了以下的排名方式:每一題分開計分,第一、第二、第三及最後一個寫出這題的人分別可以獲得 5 分、 3 分、 2 分及 1 分,如果沒寫出來則是扣 10 分,某種題數優先的概念,最後總分最低的人要請客。雖然以我們的計分方式來說,開賽應該先想辦法搶個幾題的首殺來提高分數,不過我想說我還是好好按照自己的節奏,所以就花了先花了五六分鐘把所有東西都設好才開始看題目,根據最後的記分板來看這時候王師宇已經寫掉兩題了ww 整場比賽有八題,基本上都滿簡單的,不過偶爾還是會遇到一點問題,像是有用英文寫還超級長不知道重點是什麼的題目,有明明有多筆輸入卻不在題目裡面寫清楚還讓我們需要自己通靈的題目(後來聽說是題目印錯版本啦),還有用最慘要跑 $10^{10}$ 的暴力作法卻可以在一秒內跑完的題目ww 最後我花了 1 小時 40 分鐘把題目寫完,比蔡旻諺慢一些,比王師宇快一些,唐博彥的部份則是各種問題導致他到賽末都還沒寫完(差一題)。神奇的是,使用我們的計分方式之後,前三名卻是離場順序的逆序,也就是名次依序是師宇、我、蔡旻諺跟唐博彥。詳見 Blog 中的分數登記表還有原始 ACM 模式記分板截圖。 比完賽我們就走去搭火車到高鐵站,上高鐵前把前天的車票拿回來也辦完退票手續,然後把今天的車票交給蔡旻諺保管XD 高鐵真的有夠快,感覺沒做什麼事就到台中,再沒多久就到台北了。晚上好像沒做什麼事情,就吃吃晚餐回房間耍廢寫日記。明天好像也沒什麼特別的事情,就正常上課啦~

IOI 2019 國手培訓日記 Day 2

早上被 7:40 的鬧鐘叫起來之後下樓在會館吃早餐,早餐菜色我覺得不怎麼樣啦,後來裝了一點炒麵結果還會辣。不過至少吃的飽,問題也沒太大。 今天整天都是謝孫源教授的課,早上講的是滿簡單的圖論,雖然說是都聽過了,不過還是多少聽一些。大概十點左右我們開了一場 JOI 來打模擬賽,這次的題目比前兩天友善一點點(就至少最後分數比昨天高)。 中午午餐是輔導員出去幫忙買,我們就繼續打 JOI,午餐來就邊吃邊打。可惜下午因為有其他事情,就沒有把五小時打滿,感覺有點小浪費題目,改天再來把題目寫完吧。 下午教授安排了一場模擬賽,用的是以前 ITSA 桂冠賽出過的題目。不過由於這些題目都稍顯煩躁,又不太符合 IOI 的類型,我們大多只寫了幾題之後就去寫自己的題目了ww 晚餐前唐博彥傳訊息找了施名軒來,所以我們的晚餐就由專業的在地人帶路,吃了一中人(管他中一中還是南一中,都不重要啦)平常吃的店,還合拍了一張「選訓前四名跟四位國手的合照」。 晚上依舊是房間的聊天時間,施名軒也來我們這串門子,然後唐博彥依然早早就睡了。 明天就要打比賽了(全國私立大專校院程式競賽),好緊張歐ww (X)