iT邦幫忙

2022 iThome 鐵人賽

DAY 27
0

比賽的時候,由於題目都是已經有人做過的,總是能保證有答案。而大量訓練過後,就能夠訓練出多數題目解題的直覺。筆者印象比較深刻的例子是動態規劃類型的搜索與最大網路流演算法之間的區別。這兩者的題目型態相當類似,但是要細想下去卻各自得花上不少時間。

比方說,有一道經典的題目是這樣的:你想要使用四種俄羅斯方塊 (方形、山形、兩種之形) 拼滿一個某些格子已經被佔據了的棋盤。有兩個詭異的條件:其一、是所有山形與兩種之形只能橫放。其二、則是橫放後較寬的 (中間那排) 位置必須要放置於偶數行。這個問題便是要問你是否有機會將這個棋盤鋪滿。是個相當有意思的題目。

但是出題目的時候就沒辦法總是仰賴這個直覺了,因為你甚至不知道自己出的題目是否總是作得出來。這部分可能跟研究或出上課習題比較像吧。我印象最深刻的,則是自己曾經在高中的一場練習賽出過一個貪婪演算法的題目:在一條直線上有許多圓點,這些圓點有很多種類。你現在想要將這些點兩兩匹配 (匹配時只能將相同種類的點搭配起來) 並且繪製線路將他們連起來,但是繪製時,你只能從「直線上方」或「直線下方」繪製他們,而且同一個「上方」或「下方」的位置不能同時有兩條以上的連線,題目的要求便是找出一種可行的做法。

這道題目當時想破了頭,一直卡在 O(n^2) 時間複雜度的動態規劃。但是當年同屆一起比賽的朋友 (應該是木木吧!希望沒有記錯XD) 卻能一語道破 O(n) 時間複雜度的做法,並且解出來以後淡淡地說了一句『你相信他有 O(n) 就做得出 O(n) 啊』過了這麼多年了,我發現這句話真的影響我有夠深,哈。


上一篇
研究對競賽的影響
下一篇
實作過才知道細節藏在哪裡
系列文
有事者·試競程(附帶每日演算法小謎題)30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言