蟻本初級編攻略 - 2-2 Best Cow Line
POJからのBest Cow Lineという辞書順についての問題。
Best Cow Line - POJ 3617 - Virtual Judge
牛まったく関係ない。文字列の先頭か後尾から一文字ずつとっていって、辞書順で最小の文字列を作るというもの。
例によって以前も記事を書いていた:
やはりなんだかごちゃごちゃしている。添字でいろいろやっているのは各ステップで新しいデータ構造を作らないためだと思うが・・・
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
英小文字と?でできている文字列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 - 辞書式順序
与えられた文字列より辞書順で小さい文字列を出力する問題。
s = input() print('a' if 'a' < s else -1)
うんまあ・・・ あまりコメントも必要ない気がするが、'a'が最小なのでそれと比較して'a'か-1を返す。
Pythonのstring interning実装に頼ってprint(-1 if 'a' is s else 'a')
だともしかするともっと効率的な可能性もあるが、実装依存なのと、問題の制限内の文字列長なら誤差なので無視。
ABC009C - 辞書式順序ふたたび
ある文字列の最大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(N3)・・・ だが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):
のように外側のスコープの名前を関数に束縛する手法、はやくなると言われてやってみたが計測してみるとまったく関係なかった。読みにくくなるだけだからやめよう・・・