- AtCoderのABC049C「Daydream」をCommon Lispで解く過程で、メモリ制限オーバーに繰り返し直面した。
- 早期終了・末尾再帰・BFS化と段階的に改善したが、部分文字列のコピーがキューを肥大化させる問題が残った。
- 文字列をインデックスの整数で管理することでコピーをなくし、ようやくメモリ問題を解消できた。
- 逆順から照合すると分岐が生じないため、貪欲法だけで解ける別解も存在する。
1. ABC049C問題とは？
AtCoderのABC049C「Daydream」をCommon Lispで解こうとして、メモリ制限オーバーで悩みました。
正しいアルゴリズムを書いたはずでも実行効率が悪いと、大きなデータサイズでうまく答えが出ません。
ABC049C「Daydream」は、文字列Sが与えられ、"dream" "dreamer" "erase" "eraser" を順に並べたものがSと一致できるか判定する問題です1。
先頭から一致箇所を消していくと "dreamer" と "dream"+"er" の分岐で詰まってしまいます。
今回は、この分岐処理をCommon Lispで解くことにしました。
ちなみに、この問題にはちょっとした「仕掛け」があり、逆順に解くとマッチさせていくだけで解決します。
1.1. 第1版：素直にすべての可能性を調べると……
まずは、素直に問題を解いていきます。
対象の文字列が、テスト文字列で開始しているのかをチェックし（startp）、該当すればその部分を削除した部分文字列を返す（eat）。
あとは、テスト文字列をリストで与えて（eat-by-list）、うまく進んだものを集めて、最終的に空文字列になるかどうかを判定結果を返していきます（eat-by-list-greedy）。
最後に、contain-t-p で t が含まれるか判定して、結果の YES, NO を出力します。
(defvar tests '("dream" "dreamer" "erase" "eraser"))
(defun startp (test str)
(let ((pos (search test str)))
(cond
((null pos) nil)
(t (zerop pos)))))
(defun eat (test str)
(if (startp test str)
(subseq str (length test) (length str))
str))
(defun eat-by-list (tests str)
(loop for test in tests
when (startp test str)
collect (eat test str)))
(defun eat-by-list-greedy (tests str)
(let ((candidates (eat-by-list tests str)))
(loop for c in candidates
collect (if (string= c "")
t
(eat-by-list-greedy tests c)))))
(defun contain-t-p (list)
(cond
((null list) nil)
((consp list)
(or (contain-t-p (car list))
(contain-t-p (cdr list))))
((eq list t) t)
(t nil) ) )
(format t (if (contain-t-p
(eat-by-list-greedy tests (read-line)))
"YES"
"NO"))この方法の問題は、解が見つかっても探索が止まらず木全体をメモリに展開することです。
入力が長くなると可能性の数が指数的に増え、メモリを使い切ってしまいます2。
2. 第2版：早期終了の導入
そこで、eat-by-list-greedyを少し改良しました。
候補の中に空文字列があれば即 t を返し、t が返った時点でループを抜けます3。
(defun eat-by-list-greedy-first (tests str)
(let ((candidates (eat-by-list tests str)))
(cond
((null candidates) nil)
((member "" candidates :test #'string=) t)
(t (loop for c in candidates
thereis (eat-by-list-greedy-first tests c))))))Code language: PHP (php)これで、探索のショートサーキットは入りました。
しかし、まだ再帰呼び出しによって、スタックが深くなってしまう問題がありました。
2.1. 第3版：末尾再帰の最適化
次は、コールスタックを平たくすることを考えました。
valid-pでは、複数の候補を一致できるまで短くしていくeat-by-list-greedyの代わりに、未処理文字列をpendingsにキューとして持って判定していく形式に直してみました4。
(defun valid-p (tests s)
(labels ((check-lists (tests pendings)
(cond
((null pendings) nil)
((string= "" (car pendings)) t)
(t (check-lists tests
(append
(eat-by-list tests (car pendings))
(cdr pendings)))))))
(check-lists tests (list s))))Code language: PHP (php)ローカル関数を末尾再帰する形で、スタックの問題は消えます5。
しかし、まだメモリ制限は残りました。pendings の中身がすべて subseq 由来の文字列コピーで、幅優先で広がる分岐の数がキューを肥大化させてしまっていたのです。
2.2. 第4版：部分文字列のコピーをやめる
ここで、作業途中を部分文字列で管理する方法を見直すことにしました。
(defun next-match (test str n)
(cond
((> (+ (length test) n) (length str)) nil)
((string= test str
:start2 n
:end2 (+ n (length test)))
(+ n (length test)))
(t nil)))
(defun next-match-list (tests str n)
(loop for test in tests
for pos = (next-match test str n)
when pos
collect pos))
(defun valid-p (tests s)
(labels ((check-step (tests str pendings)
(cond
((null pendings) nil)
((= (length str) (car pendings)) t)
(t (check-step tests
str
(append
(next-match-list tests str (car pendings))
(cdr pendings)))))))
(check-step tests s (list 0))))Code language: PHP (php)「どこまで食べたか」を文字列ではなく整数のインデックスで持つようにしました。
string= は :start1 :end1 :start2 :end2 を受け取り、コピーなしで部分比較ができます6。
(string= "dream" "erasedream" :start2 5 :end2 10) ; => TCode language: PHP (php)元の文字列をそのまま参照してマッチが確認できるようになり、ようやくメモリ問題は解決しました。pendings はただの整数リストになり、メモリ使用量が大きく下がったのです。
3. 何を変えたのか
| 版 | 変えたこと | 効果 |
|---|---|---|
| 第1→2版 | 早期終了 | 探索木の刈り込み |
| 第2→3版 | 末尾再帰・BFS化 | スタック解消 |
| 第3→4版 | インデックスで持つ | 同じ問題を別アプローチで解消 |
各ステップで「なぜ重いか」の診断が変わっています。
第2版まではアルゴリズム上の問題で、第3版以降はデータ表現の問題でした。
4. 【参考】後ろから食べる解法
ところで、この問題、なんと後ろから照合すると分岐が生じません。
"dreamer" と "dream" の競合は、末尾から見ると、どちらにマッチするか先頭1文字で確定するのです。
分岐がなければ、順に eat を試すだけの貪欲法で解けます。
(defvar tests-rev
(mapcar (lambda (s)
(coerce (reverse (coerce s 'list)) 'string))
'("dreamer" "dream" "eraser" "erase")))
(defun eat-one (tests str)
(loop for test in tests
when (and (>= (length str) (length test))
(string= test str :end2 (length test)))
return (subseq str (length test))
finally (return nil)))
(defun eat-rev-greedy (tests str)
(cond
((string= str "") t)
(t (let ((rest (eat-one tests str)))
(and rest (eat-rev-greedy tests rest))))))
(let ((rev (coerce (reverse (coerce (read-line) 'list)) 'string)))
(format t (if (eat-rev-greedy tests-rev rev) "YES" "NO")))Code language: PHP (php)マッチする候補は常に高々1つなので、eat-one は最初に見つけた時点で return できます。eat-rev-greedy は空文字列になれば t、eat-one が nil を返せばそのまま nil に短絡します。
分岐がないため木の展開はなく、subseq のコストは文字列長に比例するだけ7。
4.1. 【補足】displaced-substring
文字列の問題をインデックスの数値で解決するのは、ちょっと直感的でないのが気になりました。
たとえば、C言語などの解答では、前方から探索しても効率的に部分文字列を扱えます。solve(s + len)のように文字の配列にアクセスするポインタを動かすだけで、コピーせずに部分文字列を扱えるからです。
#include <stdio.h>
#include <string.h>
const char *words[] = {"dream", "dreamer", "erase", "eraser"};
const int nwords = 4;
int solve(const char *s) {
if (*s == '\0') return 1;
for (int i = 0; i < nwords; i++) {
int len = strlen(words[i]);
if (strncmp(s, words[i], len) == 0) {
if (solve(s + len)) return 1;
}
}
return 0;
}
int main(void) {
char s[100001];
scanf("%s", s);
puts(solve(s) ? "YES" : "NO");
return 0;
}Code language: PHP (php)そこで、Common Lispでも同じように、もとの文字列の一部をそのまま部分文字列として扱えるか挑戦してみました。
この発想で書いたコードが、displaced-substring関数です。eatにあるsub-seqをdisplaced-substringで置き換えます。
(defun displaced-substring (str start)
(make-array (- (length str) start)
:element-type 'character
:displaced-to str
:displaced-index-offset start))
(defun eat (test str)
(if (startp test str)
(displaced-substring str (length test))
str))
(defun valid-p (tests s)
(labels ((check-lists (tests pendings)
(cond
((null pendings) nil)
((string= "" (car pendings)) t)
(t (check-lists tests
(append
(eat-by-list tests (car pendings))
(cdr pendings)))))))
(check-lists tests (list s))))Code language: PHP (php)Common Lisp のディスプレイスト配列（displaced array）は、独自のデータ領域を持たず別の配列のデータ領域を参照する配列です。
(defparameter *a* #(10 20 30 40 50))
(defparameter *b*
(make-array 3
:displaced-to *a*
:displaced-index-offset 1))
*b* ;=> #(20 30 40)Code language: PHP (php)この場合、*b* は独立した配列ではなく、*a*の要素を参照しています。
既存配列の一部（または全部）を別の形で見せる、「ビュー」に近い概念です。
この方法なら、pendings に積まれる文字列がすべてディスプレイスト配列になり、コピーは発生しません。
ただし、実際に試してみると、今度は「実行時間制限超過」になってしまいました。
やっぱり、文字列を判定に使うのは難しいみたいです。
- 制約は文字列長が1以上10⁵以下。英小文字のみ。 – ABC049C – Daydream
subseqはCLHSの仕様上、常に新しいシーケンスをアロケートします。元のシーケンスとストレージを共有することはありません。 – CLHS: Accessor SUBSEQthereisは条件が非nilになった時点でその値を返してループを終了します。finally節があっても評価されません。 – CLHS: Section 6.1.4- 幅優先探索（BFS）は、グラフや木の探索で同じ深さのノードを先に処理する手法です。キューを使って未訪問ノードを管理します。 – 幅優先探索 – Wikipedia
- Common LispはSchemeと異なり、言語仕様として末尾呼び出し最適化（TCO）を保証していません。処理系依存で、SBCLはspeedを上げると最適化しますが、すべての状況で動作するとは限りません。 – Tail Call Optimisation in Common Lisp Implementations
string=はこれらのキーワード引数で比較範囲を絞ることができます。同ファミリーのstring<string>なども同様のキーワードを持ちます。 – CLHS: Function STRING=coerceはシーケンス型を相互変換するCLHSの標準関数です。(coerce s 'list)で文字リストに、(coerce list 'string)で文字列に戻せます。なおreverseは文字列を直接受け取って逆順の文字列を返すので、(coerce (reverse s) 'string)の二重変換は(reverse s)だけで済む点も覚えておくと便利です。 – CLHS: Function COERCE