C - XX to XXX@AtCoder Beginner Contest 259 の解法

表題のプログラミング課題に取り組んだので備忘までに解法を記録します。

課題
考え方
手順
Python による解法の例
本課題を解くのに必要な最低限の正規表現の知識
その他

課題

問題文は下記を参照。

2つの文字列 $S$ , $T$ に対して、「ある文字 $c$ が2個連続する範囲内に $c$ を任意個（0個でもOK）挿入する」という操作（以下この操作を「文字挿入操作」と呼ぶことにします）を前者に繰り返し適用することで、後者の文字列に変換できるか？を答える課題です。

考え方

例えば $T$ が問題文の入力例1と同じ "abbbbaaac" の時を考えてみます。

見たまんまですが $T$ は「1つの"a", 4つの"b", 3つの"a", 1つの"c", これらを順に連結した文字列」です。つまり $T$ の正規表現は "^ab{4}a{3}c$" です（意味が分からない方は後段の章を参照下さい）。

では $S$ が文字挿入操作の繰り返しで $T$ に変換できるのは、 $S$ がどのような文字列（正規表現）の時でしょうか？いくつかの例を挙げて考えます。

$S$	正規表現	$T$ に変換可能？	補足
abbaac	^ab{2}a{2}c$	Yes	2~3文字目の範囲に2つの "b", 4~5文字目の範囲に1つの "a" を挿入すればOK
abbaaac	^ab{2}a{3}c$	Yes	2~3文字目の範囲に2つの "b" を挿入すればOK
abbaaaac	^ab{2}a{4}c$	No	4~7文字目の "a" の繰り返しが多すぎて $T$ に変換できない
aabbaaac	^a{2}b{2}a{3}c$	No	1~2文字目 "a" の繰り返しが多すぎて $T$ に変換できない
abbac	^ab{2}ac$	No	4文字目の "a" を繰り返していないので文字挿入操作を行えず $T$ に変換できない
abbaaacd	^ab{2}a{3}cd$	No	$T$ に登場しない "d" が邪魔で $T$ に変換できない
abbaaa	^ab{2}a{3}$	Yes	$T$ に登場する "c" が無いので $T$ に変換できない

$S$ に対して行えるのは文字挿入操作だけであり、文字挿入操作は同じ文字が複数回連続する個所だけを対象に行えることから、

$T$ の文字が繰り返されている箇所について、 $S$ の対応する範囲では同じ文字が2~< $T$ と同じ数>だけ繰り返されている
$T$ の文字が繰り返されていない個所について、 $S$ の対応する個所では同じ文字が繰り返されないで登場する

・・・となっていなければならなさそうです。

$T=$ "abbbbaaac" $=$ 正規表現 "^ab{4}a{3}c$" に対して $S$ が上記の条件を満たす文字列になっているかどうかは、ずばり $S$ が正規表現 "^ab{2, 4}a{2, 3}c$" にマッチするかどうかで確かめられます。この $S$ の正規表現は $S$ が「1つの"a", 2~4つの"b", 2~3つの"a", 1つの"c", これらを順に連結した文字列」であることを示します。 $S$ がそのような文字列である場合のみ "b", "a" の繰り返しの箇所に適切な回数の文字挿入操作を行うことで $T$ に変換可能です。

手順

以上の考え方を実装するには以下の手順を踏めば OK です。

$T$ の正規表現を求める（これを仮に $\hat{T}$ とする）
$\hat{T}$ における文字の繰り返しの正規表現について繰り返し回数を { $2, n$ } 又は { $2$ } に置換する（置換後の正規表現を仮に $\dot{T}$ とする）
$S$ が $\dot{T}$ にマッチすれば $S$ を $T$ に置換可能と判定する（逆もしかり）

Python による解法の例

ほぼ上述のアイデアを愚直にコードにしただけです。

atcoder.jp

あたかも $T$ の正規表現を求めるには $T$ の文字を後ろから順に見なければならないように書かれていますが、これは多分私が勘違いをしていて、前から見ても問題ないはずです。

本課題を解くのに必要な最低限の正規表現の知識

本課題を解くには「ある文字を繰り返す」ことをどのような正規表現で表すかを理解していればほぼ十分です。

"a{m, n}" は文字 "a" を $m$ 回以上 $n$ 回以下繰り返した文字列の正規表現です（ただし $1 \leq m \leq n$ ）。例えば正規表現 "a{2, 4}" は "a" を2~4回繰り返した文字列を表すため "aa", "aaa", "aaaa" は全てこの正規表現で表せられます。"a", "aaaaa" 等は繰り返し数が過少ないし過大なのでこの正規表現には当てはまりません。また "bbb" も繰り返す文字が違うのでやはりこの正規表現には当てはまりません。

今回の課題では $S$ に対して文字挿入操作を行う箇所を表現するために <連続する文字 $c$ >{2, < $T$ の対応する個所での繰り返し数 $n$ >} という正規表現を駆使しました。この正規表現に当てはまれば文字挿入操作の繰り返しによって $c$ の繰り返し数を $n$ に増やし、当該箇所を $T$ の対応する個所と一致させられます。

他に正規表現について理解すべきことは "^" は文字列の始まりを、"$" は文字列の終わりを表す正規表現であることくらいです。例えば正規表現 "^a{2, 4}b$" は "a" を2~4回繰り返した文字列で始まり "b" で終わる文字列を表します。"aab", "aaab", "aaaab" がこれに該当します。

その他

解法は以上の通りです。余談ですが、時間切れでコンテスト中の提出はできませんでした・・・。