Arantium Maestum

プログラミング、囲碁、読書の話題

Best Cow Line問題

POJ/蟻本から:

3617 -- Best Cow Line

ある文字列の左右どちらかの端から文字を1個ずつ取って、lexical orderが最小になる文字列を作成する、という問題。

最初は舐めていたのだが、bacbなどを正しく処理するためには先読みが必要になる。

しかしbbbbbacbbbbbabcabcabcdecbacbacbaなど、ナイーブに先読みすると簡単に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