作者puzzlez (渴望一份好工作)
看板puzzle
標題[中譯] PuzzleUp 2009 (12) Ascending Letters
時間Wed Oct 7 19:28:09 2009
首頁：
http://www.puzzleup.com/2009/?home
時限：2009/10/08（四）19:00～10/14（二）18:59
答案可上傳５次，但每改１次扣２０分（基本分為１００分）
在比賽期間內可隨時回答，但只有在時限內回答者有額外加分
◆Ascending Letters
將 a～z 26個英文字母的次序打亂，重新排列出一條字串。然後再由前往後或由後往前，
從其中一個字母開始，挑出接下來字母次序
遞升者，形成另一個新字串。就這樣反覆嘗試
，挑出其中最長的字串。
請問這條次序遞升且最長的新字串，最小的長度是多少？
以下舉兩個7個字母（A、B、C、D、E、F、G）的例子：
若重新排列過後的字串為：
BGEDFCA
那麼其中次序遞升字串，最長者為
GEDCA（方向是由後往前找，從字母A開始）
BGEDFCA ←方向
若重新排列過後的字串為：
DBCAGEF
那麼其中次序遞升字串，最長者為
BCEF（方向是由前往後找，從字母B開始）
方向→ DBCAGEF
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.194.247.146
※ 編輯: puzzlez 來自: 123.194.247.146 (10/07 19:37)
1F：→ puzzlez:這次的題目真是麻煩=.=" 10/07 19:41
2F：推 LPH66:這竟然是 Longest Increasing Subsequence...@_@||||| 10/07 22:51
3F：→ puzzlez:太好了 樓上偷偷告訴我答案...我懶得算了-.-" 10/07 23:34
4F：推 FACE90006:帕索好自私喲!o(〒﹏〒)o 10/07 23:46
5F：推 LPH66:啊, 我只是把這個題目重講一遍而已 XD 10/08 01:58
6F：→ LPH66:帕索大果然厲害, 這樣就可以悟出答案 XDDDD 10/08 01:58
7F：推 ars1an:我對這題的解讀是：讓你任意排列26字母，如何使得最長遞升 10/08 04:49
8F：→ ars1an:字串最小？ 10/08 04:49
9F：→ ars1an:所以LIS的演算法應該是不相關的 10/08 04:50
10F：→ ars1an:我的答案反而是去找一個特定結構，盡量讓遞升狀況最少化 10/08 04:52
12F：推 ars1an:如果我的想法沒錯的話，字母數=26這點很微妙 :p 10/08 05:08
13F：推 stimim:我發現一件很奇妙的事情!! 10/08 12:31
14F：推 coolbetter33:這題在離散數學中很有名.但證明從來沒看懂過(攤) 10/08 12:45
15F：→ puzzlez:幹嘛要出這種題目啊◢▆▅▄▃崩╰(〒皿〒)╯潰▃▄▅▇◣ 10/08 13:02
16F：推 stimim:PuzzleUp才出到第24題啊...知道其他題目的作法orz 10/08 13:21
17F：→ stimim: 好想 10/08 13:22
18F：→ coolbetter33:我想把 NumberGame轉到MATH版給大家討論.啪所同意嗎 10/08 13:24
19F：→ puzzlez:嗯，OK呀.... 10/08 13:56
20F：推 utomaya:感覺跟鴿籠原理有關 10/08 19:08
21F：→ utomaya:數學板有討論到這一篇 可是當時沒把編號記下 10/08 19:10
22F：→ utomaya:現在回頭去找 卻找不到了...好像是這兩個月內的文章 10/08 19:11
23F：推 werul:這比賽我好早就放棄了(崩潰) 10/08 19:19
24F：推 ars1an:u大說得沒錯 (Math) #1ADqDBUY 鴿籠原理真好用 10/09 03:13
25F：→ puzzlez:看不懂證明+1 不過隱約可以感受到它的原理..... 10/09 10:43
27F：→ turing:其中1.4. 十人中之高矮次序有證明，還蠻好懂的 10/09 12:41
28F：→ turing:不過其中的ain <= ain+1 應該是ain >= ain+1 10/09 12:43
29F：→ puzzlez:那個網頁我之前有找到 也是看不懂啊>"< 10/09 15:54
30F：推 utomaya:謝教授寫得沒錯 應該是ain <= ain+1 10/09 17:44
31F：→ utomaya:噢...如果你說的是最後1行的那一個 那的確是筆誤 10/09 17:49
32F：推 turing:a大提到26，26是唯一在平方數(25)和立方數(27)之間的數字 10/09 18:10
33F：推 utomaya:上次那個硬幣問題 轉到數學板去 馬上被秒殺了 10/09 18:25
34F：→ utomaya:結果我們還跑了半天的程式 算出來還是錯的答案 10/09 18:26
35F：→ utomaya:只能說 我們太嫩了 10/09 18:26
36F：推 FACE90006:"我們"應該不包括帕索大...帕索都裝嫩>"< 10/09 19:55
37F：推 ars1an:咦？u大你硬幣問題也算出最佳解了吧，有錯嗎？@@a 10/09 20:16