蟻本初級編攻略 - 2-2 Best Cow Line

POJからのBest Cow Lineという辞書順についての問題。

Best Cow Line - POJ 3617 - Virtual Judge

牛まったく関係ない。文字列の先頭か後尾から一文字ずつとっていって、辞書順で最小の文字列を作るというもの。

例によって以前も記事を書いていた：

zehnpaard.hatenablog.com

やはりなんだかごちゃごちゃしている。添字でいろいろやっているのは各ステップで新しいデータ構造を作らないためだと思うが・・・

from collections import deque

s = deque(input())
t = []

while s:
    left = True
    for l, r in zip(s, reversed(s)):
        if l != r:
            left = l < r
            break
    c = s.popleft() if left else s.pop()
    t.append(c)

print(''.join(t))

deque使えば添字使わずに同一のデータ構造で処理が完結するし、reversedは逆順のリストではなく遅延評価的なイテレータを返す。シンプル・イズ・ベスト（でもオランダ的なシンプル）。

それではAtCoder 版！蟻本 (初級編) - Qiitaに載っているAtCoder上の類題を解いていく。

ABC076C - Dubious Document 2

abc076.contest.atcoder.jp

英小文字と?でできている文字列Sと英小文字でできている文字列Tがあたえられ、Sの?を任意の文字で埋めてTを含んだ辞書順最小の文字列S'を作る問題。

辞書順最小にする戦略は簡単で、後ろの方からTに一致させられる部分文字列を探して、残りの?はすべてaで埋めればいい。

s = input()
t = input()
 
def match(s1, t):
    return all(a in (b, '?') for a, b in zip(s1, t))
 
substrings = [s[i:i+len(t)] for i in range(len(s)-len(t)+1)]
res = 'UNRESTORABLE'
for ss in reversed(substrings):
    if match(ss, t):
        left, _, right = s.rpartition(ss)
        res = left + t + right
        res = res.replace('?', 'a')
        break
print(res)

match関数で「すべての文字が一致するか?文字か」を判定してrpartitionで左側優先で文字列を分割して再合成。残った?をaに入れ替えて終了。

ABC007B - 辞書式順序

abc007.contest.atcoder.jp

与えられた文字列より辞書順で小さい文字列を出力する問題。

s = input()
print('a' if 'a' < s else -1)

うんまあ・・・　あまりコメントも必要ない気がするが、'a'が最小なのでそれと比較して'a'か-1を返す。

Pythonのstring interning実装に頼ってprint(-1 if 'a' is s else 'a')だともしかするともっと効率的な可能性もあるが、実装依存なのと、問題の制限内の文字列長なら誤差なので無視。

ABC009C - 辞書式順序ふたたび

abc009.contest.atcoder.jp

ある文字列の最大K個の文字の位置を入れ替えて可能なかぎり辞書順最小な文字列を作る問題。

一気に難易度がはねあがった。数分考えてあまりいい解法が思い浮かばなかったのでヒントを見てしまった・・・

ヒントを読んだら実装まではほぼ一直線：

from collections import Counter

n, k = map(int, input().split())
s = input()

def diffs(s1, s2):
    return sum(a!=b for a, b in zip(s1, s2))

def possible(i, j, c, solution, best):
    head = solution + [c]
    diff = diffs(head, s[:i+1])
    if diff > k:
        return False
    remains = Counter(d for n, d in enumerate(best) if d and n != j)
    substring = Counter(s[i+1:])
    diff2 = sum((remains - substring).values())
    return diff + diff2 <= k

best = sorted(s)
solution = []
for i in range(n):
    for j, c in enumerate(best):
        if c == None:
            continue
        if possible(i, j, c, solution, best):
            solution.append(c)
            best[j] = None
            break

print(''.join(solution))

先頭から順に「残っている文字で最小のものを当てて制約を満たすことができるか」をループで調べ続ける。「各位置において」「残っている文字を」「あてはめられるかチェック」の各パートでN分のループが回っているので最終的にO(N³)・・・　だがN<=100なのでまったく問題ない。

二つの集まりの要素の違いを数で把握したいときにCounterクラスの引き算は便利。長さが同じ文字列の比較なので一回の引き算でいくつの要素が違っているかがわかる（Counter同士の引き算ではマイナスは切り捨てになる）

追記：

dequeを使ってもう少しすっきりするよう書き直した：

from collections import Counter, deque
 
n, k = map(int, input().split())
s = input()
 
def possible(solution, s=s, k=k):
    leftstr, rightstr = s[:len(solution)], s[len(solution):]
    diff1 = sum(a != b for a, b in zip(solution, leftstr))
    if diff1 > k: return False
    diff2 = sum((Counter(s) - Counter(solution) - Counter(rightstr)).values())
    return diff1 + diff2 <= k
 
solution = []
remaining = deque(sorted(s))
for _ in range(n):
    for j, c in enumerate(remaining):
        solution.append(c)
        if possible(solution):
            del remaining[j]
            break
        solution.pop()
 
print(''.join(solution))

dequeについてはもうちょっと調べたほうがいい気がする。特殊なdoubly-linked-listのようだ。

dequeはやめて、さらに最適化してみた：

from collections import Counter
 
n, k = map(int, input().split())
s = input()
counters = {i+1:Counter(s[:i+1]) for i in range(n)}
 
def possible(solution):
    diff1 = sum(a != b for a, b in zip(solution, s))
    if diff1 > k: return False
    diff2 = sum((counters[len(solution)] - Counter(solution)).values())
    return diff1 + diff2 <= k
 
solution = []
remaining = sorted(s)
for _ in range(n):
    for j, c in enumerate(remaining):
        if c is None: continue
        solution.append(c)
        if possible(solution):
            remaining[j] = None
            break
        solution.pop()
 
print(''.join(solution))

さきほどのコードもよく見てみると読みやすくなったのはdequeの恩恵ではなくCounterをうまく使ったことによるpossible関数の整理が大きかった。

行った最適化は二点：

zip(solution, s[:len(solution)])はzip(solution, s)に置き換えられるし後者のほうが効率的

というマイナーな点（こちらは最適化よりもコードの見通しがよくなることのほうが嬉しい）、そして：

Counter(s) - Counter(solution) - Counter(s[len(solution):])はCounter(s) - Counter(s[len(solution):]) - Counter(solution)に置き換えられる
Counter(s) - Counter(s[len(solution):])はCounter(s[:len(solution)])に置き換えられる
Counter(s[:len(solution)])はsolutionごとに計算する必要はないのでsの先頭からはじまる部分文字列について最初に計算して辞書化しておく。

これで大体二倍くらいのスピードアップが得られる。

remainingをLinked Listにするともうちょっと効率化できるか？ただ、Pythonには標準のSingly Linked List実装はないので自前で書くことになるから多分実際には逆効果だと思う。

def possible(solution, s=s, k=k):のように外側のスコープの名前を関数に束縛する手法、はやくなると言われてやってみたが計測してみるとまったく関係なかった。読みにくくなるだけだからやめよう・・・

Arantium Maestum

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

蟻本初級編攻略 - 2-2 Best Cow Line

ABC076C - Dubious Document 2

ABC007B - 辞書式順序

ABC009C - 辞書式順序ふたたび