103北市賽 1.水晶球 (Crystal Ball)

想法：

對於所有在時間t-1可以到的格子b, 把第t秒的格子b的上下左右d_t格設為true。
雖然看時間複雜度有點危險(O(4*10^8))，
但其實有一些cut可以加(ex. 表被填滿了就跳出)，
又有5秒可以跑，
應該可以直接AC。

Code：

103北市賽 2.得分高手 (Master)

想法：

DP題。
狀態：以座標(i,j)為終點所能得的最高分。
轉移：dp(i,j) = ar(i,j) + max(0,dp(i-1,j),dp(i,j-1))。

Code：

103北市賽 3.領土 (Territory)

想法：

滿裸的凸包+有向面積題。
小高一沒教計算幾何哭哭喔QAQ。

Code：

103北市賽 4.太空迷走 (Astro)

想法：

DP題。
要記錄的狀態有[剩餘能量f，座標p，當前前進方向w]，
轉移的話有dp ( f, p, w ) = min ( dp ( f, p+w, w ) , dp ( f+1, p+其他方向, w) ) + 1，
然後枚舉到終點前的最後一次轉彎，同時更新最佳解。
有點不太懂它給已知最佳解要幹嘛= =。
有些邊界條件不太確定，
但是沒有judge可以傳，範測也過了，
於是乎我就當它是對的吧>///<。

Code：

103北市賽 5.加密金鑰 (Key)

想法：

觀察發現，若存在長度=m的解，那麼對於x<=m均有解。
由這項單調性，可以二分搜長度，
再枚舉這個長度的子字串是否相同即可。

實作上要使用string hash的技巧，
請諸位自己多背一些質數吧^^。

Code：