HSPC 2014

Sylveon

HSPC比完了，應該來懺悔一下只有拿第二!? 明明有看過題目(又抄題...)，但卻放掉兩題，兩題都是flow，一題是我高一全國賽的最後一題，是KM algoithm的原始模型題... 不過當時只有國手一人寫出來... ，另一題股票走勢也是全國賽題目，不過我把模型建錯，變成用加的加到答案，然後就一片混亂，結果原來是用總額扣回去，真是悲劇，另一個未解出的也很可惜，一直想要怎樣搬座標，沒想到用向量直接乘一乘就好了，水題未解出超慘，原本想說時間還滿微妙，下面給下個人隨興題解吧：

A.睡吧喬治
BASIC
http://ideone.com/VH3esg

兩時間相減，我直接小時/分鐘直接減，隨便處裡一下進位就拿到傳說中的SID:1 Yes. 本人第二次，上一次是去年NPSC出賽被我亂翻到gcd瞬殺得到的，超開心。

B.神奇寶貝大師之路 - 迷幻森林
BFS
http://ideone.com/Kq9Fkm
這一題是李弘毅想出來的，我在爆pG時哪幫我弄出來讓我可以接著coding，基本上可以想像所有的訓練師都執著地要在終點對戰，那可以證明只有該訓練師與終點之最短路小於等於主角時才能對戰。多起點最短路如果笨笨的從每個起點開始搜應該是會TLE的，不如從終點一網打盡的乾脆。

C.四面體
DP
Code遺失~ 不過超水
有人在四面體的邊上走路，問跨過N條邊回到原點的方法有幾種。簡單DP亂加一通再建表O(1)輸出就好了。
EXIN 2 4
EXOUT 3 21

D.公車司機問題
Gready
http://ideone.com/WAbAzH
經典問題，盡可能的填滿即可達最佳解，就把最大加最小，以此類推即可。

E.股票走勢圖
Flow
none
GCJ 2009 R2 C Stock Charts
https://code.google.com/codejam/contest/204113/dashboard#s=p2
這題把模型建成NP問題，然後就悲劇了，由原題另一觀點構造其實這題很簡單。

F.機器人
模擬+數學
none
先模擬走一次，再用向量平移求整數解，沒解出也很悲劇

G.城市馬拉松
Shortest Path + 位元DP
http://ideone.com/9mfQE5
http://zerojudge.tw/ShowProblem?problemid=a416
原題的奇數點有20個，成大只有16個，不過其他方面相同，說這題防破台，也太常見此題了！
中國郵差問題，本題起終點不同，要補成歐拉環的基本概念就是加一條起點到終點的雙向邊，為不影響答案，權重設為極大數值。找出奇數點有哪些後，做最短路求出全奇點對間最短路徑長，個人用SPFA，然後再求奇數點的最小權匹配，一般圖的最小權匹配是NP，在此用位元DP，複雜度O(2^N)，可在時間限制內完成，就把這題給爆開了。

H.(給老師了XD 同2012全國賽最後一題)
Flow
擺了兩年還是不會KM......