114台北市學科能力競賽簡單題目及心得

成績

125/600分 第48名佳作

• pA 23分
• pB 62分
• pD 40分
• 其餘0分

心得

糟透了，可能是高三花的時間不夠，還有更多進步空間。第C題我到最後才想到子題的做法（用炸的很快，可惡），其他的就是還需要學會活用演算法。

南湖高中（主辦校）校長位子在我們大同前面，所以我跟學弟的談話內容有兩度被寫進他的引言裡面：一次是學弟在猜演講題目，一次是他問我的成績（各種害羞）

演講是台灣師範大學專任副教授蔣宗哲主講，內容簡明扼要就是AI會不會取代工作，但很有趣，也有許多深入的看法！

題目

以下題目為憑我印象，大致上精簡過題敘後的內容，供您思考，詳細題目請等公告內容

pA 購物折扣

（我拿了一個子題23分）

給定書本的數量及每本書的價格（價格必定為100倍數），有兩種折扣方式

1. k （$3<=k<=20$）個一組，最便宜的免費
2. 不成組的（可以刻意不成組）$價格*(100-p)\%$，p為整數（好像$3<=p<=30$）

求最便宜總價

註：子題一：$k=3$

pB 巫師傳送陣

（我拿兩個子題共23+39分）

給定一個一維地圖v（例如…

1 2 3 4 5 6 2 7

從索引0開始，目標是最後面，可以執行以下操作各消耗一點能量

• 往前走一步
• 往後走一步
• 若v[i] == v[r]則可以從i移動至r

求最小消耗能量（上面的例子答案為3）

我一開始沒看到可以往後但是可以拿到23分

我用了這個（題解防雷連結）演算法但我不會優化直接用queue但被TLE了。

pC 武林大賽

有m個機器人n場比賽，每場比賽分別有兩個輸入代表參賽的兩個機器人，求最小需要參加比賽數量以達到「每個機器人都有比賽到」的目標。

註：子題一：$m=4$，我最後才做來不及。難受。

pD 旅遊路線

（拿下10+10+20分三個子題）

給定m、n分別代表有向圖的節點、邊數量，接下來有n行輸入包含p、s、d分別代表這條邊奇/偶數日能通過、起點、終點。最後輸入k、t代表終點以及日數。

目標：找出一個起點在走了t天後能抵達k，超過一個點時取路線最多者，若仍超過一個則再取編號最小者。注意：除非無路可走否則必須前往下一個點。

這題我用這個（題解防雷連結）但不知道哪裡有問題，有一個三十幾分的子題最後一個測資被WA了。這題是最有想法的一題（我甚至昨天在練習這個演算法，到現在還不知道哪裡錯）

pE 雨滴音樂

題敘最簡單但是完全沒想法的一題：一串數字由0、1組成，找出輸入的字串為其子字串的機率高於$50\%$的最小長度。

例如：11出現在長度為3字串的機率為$3/8$（110、111、011在$2^3$個可能中發生），小於$50\%$需要再增長，求最短符合的長度（越長機率會越大，可以自己算一下）

pF 捷運

給定每個車站的發車時間、發車間隔、行駛時間、換線所需時間，求從A站到B站的最短時間。

這題我腦袋跟打結一樣完全沒想法，做出來的可以考慮去重寫台北捷運的軟體。

總結

有很多題目在復盤的時候在想一些發揮空間，但也沒辦法過了就過了，希望未來能夠更收悉不同演算法。他是有給帳號說可以拿回程式但他們甚至沒有官網…？

致謝

非常感謝瑞宜老師、昱珺老師和翔惟老師的帶領及安慰（我真有點對自己失望。），過程中幫我們處理各種事情以及鼓勵會讓我難忘！

小插曲

他們忘記鎖Python，但聽說後來分數被收走了（但不影響有得獎的人的成績）