PKU1196-Twofive

題目：http://poj.org/problem?id=1196
(IOI2001，USACO5.5也有收錄)
現在把A...Y總共25個字母、填到一個5*5方塊裡，好比說
ABCDE
FGHIJ
KLMNO
PQRST
UVWXY
如上的方塊型式，轉成字串型式則有ABCDEFGHIJKLMNOPQRSTUVWXY
現在25-語言是一些單詞組成的，就像上面的字串形式
然而這些25-語言的方塊形式的字母序都具有「由左而右遞增」以及「由上而下遞增」這兩種特性
按照字典序排列，第二個單詞是ABCDEFGHIJKLMNOPQRSUTVWXY、由第一個單詞交換ＵＴ組成
要求輸入單詞能算出是字典序第幾個、輸入數字能輸出對應編號的單詞

(USACO第五章最後一道AC的題目…倒數三題了)


程式碼：http://codepad.org/Xrw26Mjz
不是我在說，這真的是相當淫蕩的一道題目…
我一開始想說來建模看看說不定可以得到絕世妙解
果斷把ABCDEFGHIJKLMNOPQRSTUVWXY(詞序1)換成1111122222333334444455555
意思就是依序把A放row1、B,C,D,E放row1、FGH row2...
或是像
1234512345123451234512345
就是把AFKPU放row1、BGLQV放row2
可以知道詞序第一個是1111122222333334444455555
最後一個是1234512345123451234512345
這種數字序列的特性就是：
任一段前綴，1的數量>=2個數量>=3的數量>=4的數量>=5的數量

於是很容易想到屬於卡特蘭數的一種組合問題：dyck word
給n個X和n個Y，任一前綴X的數量比Y多(例如XXYYXY)
所以很自然的就想到利用DP來解決這道問題

狀態數並不多：5*5*5*5*5=78125，
懶得遞推乾脆來個記憶化搜索
如此想要算出「以某字串開頭」的合法字串數目、就不是難事

於是整個算法核心的面目就呼之慾出了
拿字串轉序號來說(我們拿ADJPTBEKQUCGLRVFINSWHMOXY當範例)
首先看到頭兩個字是AD
已知詞序[1]、給定字串詞序[X]，這中間一定夾疊了很多字串
由於字典序的要求，這些字串都是有特徵的：
ABCDEFGHIJKLMNOPQRSTUVWXY[1]
AB@@@@@@@@@@@@@@@@@@@@@@@[2]
.
.
.
AC@@@@@@@@@@@@@@@@@@@@@@@
.
.
ADE@@@@@@@@@@@@@@@@@@@@@@
.
.
ADF@@@@@@@@@@@@@@@@@@@@@@
.
.
ADG@@@@@@@@@@@@@@@@@@@@@@
.
.
(如此逼近、和目標詞越來越像：)
ADJPTBEKQUCGLRVFINSWHMOXY[X]

具體來說就是把
AB開頭的方法數+AC開頭+ADE開頭+ADF+ADG+ADH+ADI+
ADJK+ADJL+ADJM+ADJN+ADJO+ADJPQ+....全部加起來

最後+1，就是我們要的答案

(可以先設想例如10個字母無限制條件任意排列
10!種情形求字典序、也是類似的道理)

如果換成了數字轉字串、也是類似的道理，假設所求第n單詞
(首先第一位一定是A、不必檢查)
一位一位枚舉，第二位的時候：
AB...有3000種方法，如果n>3000便說明了第二位不可能是B
AC...有2800種方法，如果n>2800+3000便說明了第二位不可能是C...
(可能接下來AD...有2500種方法，而n<=2500+2800+3000，確定第二位D)
ADE...有1500種方法，如果n>1500+2800+3000、表示第三位用E太少
.
.
.
一直重複直到25位都確認
有注意到嗎？2500不用加進來，因為AD開頭的字串他們序號會是5801~8300

其餘細節就留給讀者自己發堀實現，說一點心得：

1.一道相當有趣的題目、很有組合數學味道

2.實際操作的過程中作一個暴力模擬的程式是很有幫助的(debug有意想不到的好處)

3.USACO Training第五章的題目難度突然暴漲…(這些等我全破之後再發文)