Day.9、10 暴風
進階動態規劃
二階開始了
課程也變得更加困難
今天的課程聽得好痛苦 QwQ
尤其是位元 DP，完全跟不上講師的速度
後面複習時，總算漸漸有了頭緒
這次的手寫作業史上最難
歸約法、NP-hard、3-SAT、……
完全不知道怎麼寫證明
第二堂課的講師其實有提到這些東西
他也說之後可能會要大家證明
原來他埋了這麼深的梗 OAOAOAO
作業進度 QuQ：幾乎沒什麼進展
Day.11 小雨
進階圖論
經過前兩周的摧殘後
我終於在今天得到救贖
相較於動態規劃，圖論不僅好理解
實作上也順手許多
（一定是我還沒接觸到更深的知識
總之今天算是把之前略聽過的東西
全部學習得更紮實
這次的手寫作業真的好有趣><
BIT 好好寫，只是能有的地方感覺不是很多 QQ
(聽說有個東西較 zkw 線段樹
(實用性跟 code 複雜度介於線段樹跟 BIT 之間(?
作業完成度>u<：手寫：剩一題證明題 / 上機 4/7 題
Day.12 彩虹
計算幾何
先前就對這主題很有興趣
（把幾何圖形用電腦表示!?
並且研究過好多次向量
利用純記憶的方式學習它
因此每每學過之後都會忘記
直到今天才真正搞懂那些運算的意義
內積、外積、線段平行、線段相交等等
手寫作業則是介紹了 hash 演算法
還好這部分已經有一些背景知識
寫起來格外輕鬆
（殊不知這是之後上課的伏筆
作業完成度 OuO：手寫：剩一題證明題 / 上機 5/8 題
Day.13 綠葉
線段樹
以前碰線段樹的時候
知道它在幹嘛、知道它可以 O(log n)區間操作
但是就。是。不。會。實。作 QuuQ
（線段樹啊線段樹為什麼你這麼冷漠 QAQ
今天上完這堂課後
總算跟他培養出好感情了
我們之間終於有了好的發展
但是要到摯友的等級
還要走好長一段路呢！
禮拜五的時候發生了一些小插曲
班上另一位資芽的同學
寫線段樹 WA 了一整個晚上
在課堂上繼續寫時寫到爆氣、翻桌
後來試著看他的 code
然後莫名其妙改了一些東西就好了(!?
（看來他們之間默契不太好：（
其實這也算是競程這條路必經的過程吧
總是會卡住、挫折
熬夜 debug 結果還是不得其解
那種手抖、挫敗、的憂鬱的歷程對我來說很有共鳴
畢竟我不是那種一路 AC 的天選神才
（我吃過的 WA 跟 TLE 比 AC 多非常多
而這些困境真的要有夠強大的意志力才撐得下去……
作業：沒有手寫 / 上機：4/6 題
Day.14
歡樂團體賽
團體賽！！！！！！！>u<
聽說這是往年資芽都有的傳統
學員組隊打比賽，1~3 人
採 ICPC 制，3 小時 8 題
我跟很電很電的 joy 還有柏瑄組隊><
先來講解題的情況
開場沒多久，joy 就已經把所有題目看完了
每當我看完一題，還在思考或是正要寫的時候
joy 已經把它結束掉了（電電電電電電電電電電）
柏瑄雖然比較晚到，但是他也很成功的貢獻一題
終場以 AC 六題拿下這次的第二名（joy 凱瑞了 5 題 Orz）
而我呢？完全的躺分仔 OAOAOAOAOAOAOAO
（一題都沒有寫的廢物 QuQ……）
發獎品的時候，我真的太心虛，根本沒資格拿……
拿著他拍完照以後就不斷的塞給他們兩個人
儘管如此，這場比賽至少讓我有了些經驗
坐在 joy 旁邊，能夠近距離觀察他的解題方式還有寫 code 的速度（真的好快 OAO），算是學到一些比賽的經驗了吧(?
題目的部分，講師們真的很用心 XDDD
看到題敘好多日麻就會一直想到 YP 好好笑 XDD
（日麻大師 Orz）
最讓我印象深刻的是π筆測資那題 XD
題目是一個很難的數學題
但是輸出的答案竟然要 mod 2 而且只有[π]筆測資(π=3)
那當然是猜答案囉 XD
joy 把它認領走後，接著就是瘋狂亂猜
最後丟了 47 筆才 AC XDDDDD 好好笑
但就算吃了這麼多 penalty 他依舊輾壓其他題目
拿下全場第二 (— —)/ /(_ _)\ (— —)/
總之今天這場比賽真的很歡樂~
Day.15 小樹
隨機演算法
這堂課據講師說是最輕鬆的一堂
教大家如何騙過水測資 X)
有些題目看似需要很高深的演算法
但是其實隨機就可以唬爛過去 XD
（居然連最近點對也可以隨機 OAO
當然還是有正經的部分
除了隨機還學到了雜湊函數、rolling hash 等壓縮資訊的演算法
因為是最後一堂資訊之芽
講師們也在下課後約吃晚餐
跟講師們聊天聊得很愉快
也發現了他們的一些小秘密
兩周後就是最終的認證考了
由於第一次慘痛的教訓
這次考試我不抱任何期望
就隨緣吧～
反正拿 0 分我也無所謂
驗收時刻 – 二階認證考
小樹的考驗
(賽中)
開場先打開所有題目
雖然真的比上次友善許多
但是我腦袋仍舊一片混沌
看完 pA 以後的半個小時真的在耍智障
隨便寫了個最小生成樹丟上去顯然大假解
結果後面才真正看懂題目
大概知道做法的方向
但是拖太久時間了，懶得想完整細節+重寫 code
於是跳過（記取上次教訓
（1hr flied away）
題目都看完了後（對，我看題目就是要這麼久 QuQ
決定先撈 pD 子題
但是我跟線段樹不太熟，擔心刻爛
所以寫了 O(n^2)水水解丟上去->70 分
（暴力解就可以拿超過一半分數，這真的很賺欸
再來從 pE 下手
疑似想到正解，然後就開始寫
這一寫就是一個小時…… （我的線段香蕉相交 QwQ
（寫到一半突然被前面砸鍵盤的人嚇到
加上之前作業沒有認真寫->第一次寫凸包
寫完以後丟上去，只有 50 分 OnO，重點是只卡一筆小測資！！！
（1hr remaining）
在那邊修修改改 code 然後一直 WA
就這樣你瞪我我瞪你快 15 分鐘
最後還是放棄了，到這裡也快要砸鍵盤了，但還是冷靜了下來
跑去寫 pC，看能不能撈分
想用個背包解決掉子題，但是 code 真的寫太慢
剩兩分鐘就放棄了
（05
這時又跑回去看 pA
往下滑題本，看啊看，看到第一子題
莫名其妙發現輸出 0 就可以拿到 10 分 XDDDDDDDD
（在最後 30 秒丟上去 XDDDD 好爽
然後比賽就結束ㄌ
(結果)
分數：悽慘的 130 分／500 分。排名：居然有 8。
備註：林柏瑄(180)＆林哲宇(沒看到)兩位都把我踩在腳下 m(_ _)m
(賽後題解)
聽完題解感想：真的是扼腕扼腕加扼腕啊 OAOAOAOAO
講師講 pB 時我也跟著往下滑題本
（講師：那麼現在來講 1、2 子題怎麼做
（我：看到 mod <= 1e7
大水分啊 OAOAOAOAO 因為逃避問題 60 分就去了 qwq
只要枚舉 1e7+1 個字串就好了我到底在想什麼 QwQ
還什麼可能要觀察 hash 函數的性質，最好是啦
其實這題題解真的很酷
利用上課講過的生日悖論
只要枚舉的字串數在 sqrt(mod)之間
就有 50%的機率找到兩個 hash 值相同
白話一點，就是有一半的機率會 AC
pC 要用到換零錢的 greedy 性質加上 DP 性質
（這還不是正解ㄛ
出這題的講師是 greedy 的講師
他真的把我們電焦了（這題沒有人滿分
這題 O(n^3)題解難到用講的也不會有人聽得懂
索性就把有關題解的論文放到社群上
（皓神 Orz
電電電電電電電電電電電電電電電電電電電電電電電電電電電
pD 線段樹，聽說有人被卡常數(?
pE 聽完才發現我大假解 OAOAOAOAOAO
可以拿到 pE 第一子題 50 分
是因為那是三角形一定是凸的
為甚麼簡單多邊形會有凹的啦 QWQ
看到這裡的你
一定會想說怎麼沒有 pA 呢
沒錯你猜對了
我還是不會 pA QuQ
所以我想求問各位大神
有沒有人知道 pA 怎麼做><
心得
二階認證考就這樣結束了>_<
我覺得這次的狀況比上次好很多
心情上至少沒有上次那樣緊張
精神也還算穩定
但是能力仍然偏差，反應也很遲鈍@@
（一場比賽花超過 1/6 的時間看題目(_ _)||||）
最大原因還是缺乏練習＆經驗
因此我打算利用暑假時間開始刷題（立 flag
希望之後能變得越來越強>///<
結語
恍惚之間四個月就這樣過去了
2020 資訊之芽就在大合照後謝幕
一開始升高一的暑假第一次與 C++邂逅
接著培訓時狠狠地被講師還有同學電，讓我看清一切
最後下學期進入資芽，大量密集課程+作業
不斷讓我向上成長，從幼芽長成一棵樹
經過 16 周，我感受到自己增強不少
終於能夠稍微看見班上同學們的車尾燈，與他們談論演算法
更甚至由自己解說演算法的原理
然而往上一看
有許多人依舊在我看不到的山峰上
因此即使資芽結束了
我也要繼續努力
期許自己也能在這競賽的舞台上發光發熱！
最後
謝謝 joy 那場團體賽願意讓我躺分
見識到了真正高手的思維，讓我大開眼界
謝謝 wiwi 願意讓我在半夜的時候戳你問題
不管是手寫還是上機作業
都因為有你的幫忙才能拿分><
謝謝你願意教我>///< wiwihorz
最重要的是
謝謝資芽的團隊，尤其是講師
這 16 周準備了這麼多豐富的課程
包括那場好玩的團體賽
還有幫助我們解答任何疑惑、甚至幫我們處理 bug
這段時間，你們辛苦了！:pusheen_love:
幼芽日記 第二部 終