【AtCoder ABC452C】
Fishbonesに文字を書く
（Common Lisp）

• AtCoder ABC452Cは、魚の骨を模した構造に文字列を割り当てる問題で、脊椎の各文字が対応する肋骨の条件を満たすかをM個のクエリに答える。
• 前処理として「長さa・b文字目・文字ch」の三つ組をキーにしたハッシュテーブルを作り、クエリごとの線形探索を避ける。
• ハッシュテーブルのキー比較には:test #'equalを指定することで、リストの中身まで正しく照合できる。
• クエリ判定ではloop ... alwaysで全肋骨条件を短絡評価し、1つでも不成立なら即座にnilを返す。

1. 問題

アーティストの高砂君は、魚の骨をかたどったオブジェを作りました。
オブジェは $N$ 本の肋骨と 1 本の脊椎からなります。
肋骨には 1 から $N$ までの番号が付けられています。

高砂君は、以下の条件をすべて満たすように $N+1$ 本の骨に 1 つずつ文字列を書こうと考えています。

• 脊椎に書く文字列の長さは $N$ である。
• 肋骨 $i=1,\dots,N$ に対して、以下が成り立つ。
• 肋骨 $i$ に書く文字列の長さは $A_i$ である。
• 肋骨 $i$ に書く文字列の $B_i$ 文字目は、脊椎に書く文字列の $i$ 文字目に一致する。
• $N+1$ 本の骨に書く文字列はいずれも、$S_1,\dots,S_M$ のいずれかである（重複してもよい）。
• $S_1,\dots,S_M$ は英小文字からなる文字列であり、互いに異なります。

$j=1,\dots,M$ に対して、以下の質問に答えてください。
条件を満たす書き方のうち、脊椎に書く文字列が $S_j$ であるものは存在しますか？

• $N$ は整数 $1 \le N \le 10$
• $A_i, B_i$ は整数 $(1 \le i \le N)$$1 \le B_i \le A_i \le 10 \ \ (1 \le i \le N)$
• $M$ は整数 $1 \le M \le 200000$
• $S_j$ は英小文字からなる文字列 $(1 \le j \le M)$ $1 \le |S_j| \le 10 \ \ (1 \le j \le M)$
• $S_1,\dots,S_M$ は相異なる

入力は以下の形式で標準入力から与えられる。

N
A_1 B_1
⋮
A_N B_N
M
S_1
⋮
S_M

$M$ 行出力せよ。

$j$ 行目 $(1 \le j \le M)$ には、条件を満たす書き方のうち脊椎に書く文字列が $S_j$ であるものが存在するならば Yes を、存在しないならば No を出力せよ。

1.1. 例

入力例

5
5 3
5 2
4 1
5 1
3 2
8
retro
chris
itchy
tuna
crab
rock
cod
ash

出力例

Yes
Yes
No
No
No
No
No
No

2. ハッシュテーブルで記録した

背骨となる単語を一つ選んだときに、1文字目から順にほかの単語で作れるか、を調べることにします。

すると、必要なのは b 文字目に必要な文字があるか、ということになります。
これは単語リストによって決まるので、あらかじめハッシュテーブルに三つ組を記録しておきます。

;; Make hash-table, key (a b ch)
;; to consult whether the word whose length is a has letter ch on b 
;; usage: (gethash '(5 3 #\r) (char-table words))
(defun char-table (words)
  (declare (type list words))
  (let ((table (make-hash-table :test #'equal)))
    (loop for w in words do
      (loop for ch across w
	    for b from 1
	    with a = (length w)
	    do (setf (gethash (list a b ch) table) t))
      finally (return table))))Code language: Lisp (lisp)

キーの同一性は、equalで検査すれば、三つ組の中身を含めてチェックできます。

そうすれば、あとは1文字目から順に利用可能かどうかをチェックするだけです。

;; check whether the word can be constructed by char table.
(defun can-construct-p (the-word n ab-s ch-table)
  (cond ((/= n (length the-word)) nil)
	((loop for ab in ab-s
	       for i from 0
	       always (gethash
		       (list (car ab)
			     (cadr ab)
			     (aref the-word i))
		       ch-table)) t)))Code language: Lisp (lisp)

2.1. 完成したコード

;; The words need to be collected by read-line.
(defun solve ()
  (let* ((n (read))
	 (ab-s (loop repeat n collect (list (read) (read))))
	 (m (read))
	 (words (loop repeat m collect (read-line)))
	 (ch-table (char-table words)))
    (loop for w in words do
      (princ (if (can-construct-p w n ab-s ch-table)
		 "Yes"
		 "No"))
      (princ #\newline))))

;; Make hash-table, key (a b ch)
;; to consult whether the word whose length is a has letter ch on b 
;; usage: (gethash '(5 3 #\r) (char-table words))
(defun char-table (words)
  (declare (type list words))
  (let ((table (make-hash-table :test #'equal)))
    (loop for w in words do
      (loop for ch across w
	    for b from 1
	    with a = (length w)
	    do (setf (gethash (list a b ch) table) t))
      finally (return table))))

;; check whether the word can be constructed by char table.
(defun can-construct-p (the-word n ab-s ch-table)
  (cond ((/= n (length the-word)) nil)
	((loop for ab in ab-s
	       for i from 0
	       always (gethash
		       (list (car ab)
			     (cadr ab)
			     (aref the-word i))
		       ch-table)) t)))

#-swank
(solve)
Code language: Lisp (lisp)