Best Cow Line問題
POJ/蟻本から:
ある文字列の左右どちらかの端から文字を1個ずつ取って、lexical orderが最小になる文字列を作成する、という問題。
最初は舐めていたのだが、bacb
などを正しく処理するためには先読みが必要になる。
しかしbbbbbacbbbbb
やabcabcabcdecbacbacba
など、ナイーブに先読みすると簡単にO(N^2)
になってしまう。個別には対処できるのだが、すべてのケースを網羅してO(N^2)
を避けるうまい書き方が思い浮かばず、思わず蟻本の回答を見たら何事もなくO(N^2)
だった。でもN<2000だから1000msで4*106件って考えると余裕だな・・・
def isLeftSmaller(s, i, j): while i < j: if s[i] != s[j]: return s[i] < s[j] i += 1 j -= 1 return True def solve(s): i, j = 0, len(s) - 1 res = [] while i < j: if isLeftSmaller(s, i, j): res.append(s[i]) i += 1 else: res.append(s[j]) j -= 1 res.append(s[i]) return ''.join(res)
しかしPythonでindexをいじっていると嫌な気持ちになるが、効率よく先読みしていくにはこれが(悪い中で、考え付く限り)一番すっきりした書き方であるように思う。
試しにHaskellで書いてみるとこんな感じか?
solve :: [Char] -> [Char] solve cs = take (length cs) (mergeSmaller cs (reverse cs)) mergeSmaller :: [Char] -> [Char] -> [Char] mergeSmaller [] cs = cs mergeSmaller cs [] = cs mergeSmaller xs ys | isLeftSmaller xs ys = (head xs) : mergeSmaller (tail xs) ys | otherwise = (head ys) : mergeSmaller xs (tail ys) isLeftSmaller :: [Char] -> [Char] -> Bool isLeftSmaller [] _ = False isLeftSmaller _ [] = True isLeftSmaller (x:xs) (y:ys) | x < y = True | x > y = False | otherwise = isLeftSmaller xs ys