🦁

競技プログラミングにおける正規表現

に公開
C++
Python
競技プログラミング
AtCoder
正規表現
tech

もってきた

もともとQiitaで書いてた↓の記事をZennでも公開することにしました。
競技プログラミングにおける正規表現

投稿日自体は古いですが、内容は今でも通用するものと思われます。

はじめに

最近、脳トレがてら AtCoder の過去問を解いています。
AtCoderProblems の 簡単な問題から順に解いてる感じです。

やっていて気づきましたが、文字列処理の問題で正規表現を使うと簡単に解ける場合が結構あります。
ソートや貪欲アルゴリズムなど気づけば簡単なパターンがあるのは経験している方も多いと思いますが、そんな感じです。

簡単に解けるかどうかは慣れや人にもよると思いますが、コードがキレイに書けるのは間違いありません。特に C++ の場合、一般に文字列処理は複雑になりがちなため、顕著です。
また、標準ライブラリのコードを使用するため、自前の実装に比べてバグを入れてしまう可能性を下げることができることが利点になります。

コードを提出して AC した後、もっと他にいい方法や書き方ないかなと、他の方のコードの拝見させてもらうことがあるのですが、あまり正規表現を使っているコードを見かけません。
実際、公式の解説でも正規表現という文字をまあ見かけないです。おそらく正規表現は計算量が表現しづらいことが原因のひとつかなと思います。というのも計算量は処理系が用意する標準ライブラリの実装に依存してしまいます。

とはいえ、AtCoder では入力される文字列に制約が課されることが多く、文字列の長さが大して長くない場合が多いので実際には大丈夫なケースばかりなイメージです。(というより長すぎる文字列を AtCoder さん側は標準入力させることができるのでしょうか？)

というわけで今回は正規表現ではこう解けるみたいなのを紹介していこうと思います。
コードは C++ と Python の実装例を載せておきます。

あくまで例なので参考程度に思っていただけたら幸いです。

問題例

ABC 053 B - A to Z String

問題文

すぬけくんは文字列 s の連続した一部分(部分文字列という)を取り出して先頭が A であり末尾が Z であるような文字列を作ることにしました。 すぬけくんが作ることのできる文字列の最大の長さを求めてください。 なお，s には先頭が A であり末尾が Z であるような部分文字列が必ず存在することが保証されます。

制約

  • 1 ≦ |s| ≦ 200,000
  • s は英大文字のみからなる
  • s には先頭が A であり末尾が Z であるような部分文字列が必ず存在する

入力例
HASFJGHOGAKZZFEGA

出力例
12

文字列 s の部分文字列のうち先頭が A ，末尾が Z であるようなものの最大の長さを求めよ という問題になります。

先頭が A ，末尾が Z であるようなものの最大の長さを持つ部分文字列にマッチする正規表現は A[A-Z]*Z と書けますので、正規表現を使用した実装例は以下のようになります。

c++
int main() {
  string s;
  cin >> s;

  smatch m;
  regex_search(s, m, regex("A[A-Z]*Z"));
  cout << m.str().length() << endl;
  return 0;
}

制約から正規表現にマッチする部分文字列は必ず存在するので if 文による分岐を書く必要はありません。
Python での実装例は以下のようになります。

python
import re

S = input()
m = re.search(r'A[A-Z]*Z', S)
print(len(m.group(0)))

ABC 084 B - Postal Code

問題文

Atcoder国では、郵便番号は A + B + 1 文字からなり、A + 1 文字目はハイフン - 、それ以外の全ての文字は 0 以上 9 以下の数字です。
文字列 S が与えられるので、Atcoder国の郵便番号の形式を満たすかどうか判定してください。

制約

  • 1 ≦ A, B ≦ 5
  • |S| = A + B + 1
  • S は 0 以上 9 以下の数字、およびハイフン - からなる

入力例
3 4
269-6650

出力例
Yes

正規表現に標準入力で受け取った数字 A , B を組み込めば楽に解けます。

c++
int main() {
  int A, B;
  cin >> A >> B;
  string S;
  cin >> S;

  const string pat = (boost::format("^\\d{%d}-\\d{%d}$") % A % B).str();
  const regex re(pat);
  cout << (regex_match(S, re) ? "Yes" : "No") << endl;
  return 0;
}

上の入力例でいえば、正規表現のパターンは ^\d{3}-\d{4}$ のようにフォーマットされています。
C++ の場合、 snprintf などでもフォーマットできますが、std::fmt が来るまでは boost::format を使っててよいと思います。
regex_matchは全体マッチなので、メタ文字^ , $ は別になくともかまいません。

以下は Python での実装例です。

python
import re

A, B = [int(x) for x in input().split()]
S = input()
print ('Yes' if re.search(r'\A\d{{{}}}-\d{{{}}}\Z'.format(A, B), S) else 'No')

Python で {} をエスケープするには {{}} とする必要があります。
re.search としていますが、 re.match でいいです。そうすれば、メタ文字 \A, \Z　は必要なくなります。

ABC 104 B - AcCepted

問題文
文字列 S が与えられます。S のそれぞれの文字は英大文字または英小文字です。 S が次の条件すべてを満たすか判定してください。

  • S の先頭の文字は大文字の A である。
  • S の先頭から 3 文字目と末尾から 2 文字目の間（両端含む）に大文字の C がちょうど 1 個含まれる。
  • 以上の A, C を除く S のすべての文字は小文字である。

制約

  • 4 ≤|S|≤10（|S| は文字列 S の長さ）
  • S のそれぞれの文字は英大文字または英小文字である。

入力例
AtCoder

出力例
AC

S が問題の条件 3つすべて満たすような正規表現を考えます。

1つ目の条件は ^A と書けます。
2つ目の条件と3つ目の条件から2文字目と末尾は必ず小文字であることがわかるので、^A[a-z](第2条件)[a-z]$ のように書くことができます。

問題は2つ目の条件をどのように正規表現で書くのか？になります。

(第2条件) 内の C の現れる位置について、先頭、末尾、それ以外で場合分けして考えてみると、最終的に [a-z]*C[a-z]* というように書くことができることに気が付きます。

以上のことから、正規表現は ^A[a-z]([a-z]*C[a-z]*)[a-z]$ のように書けますが、カッコは必要ないので、これは ^A[a-z]+C[a-z]+$ とできます。

以下は C++ と Python の実装例になります。

c++
int main() {
  string S;
  cin >> S;

  cout << (regex_match(S, regex("^A[a-z]+C[a-z]+$")) ? "AC" : "WA") << endl;
  return 0;
}
python
import re

print ('AC' if re.match(r'\AA[a-z]+C[a-z]+\Z', input()) else 'WA')

例によって全体マッチなので先頭と末尾にマッチするメタ文字は不要です。

ABC 106 C - To Infinity

問題文
Mr. Infinity は, 1 から 9 までの数字からなる文字列 S を持っている. この文字列は, 日付が変わるたびに次のように変化する.

  • 文字列 S に含まれるそれぞれの 2 が 22, 3 が 333, 4 が 4444, 5 が 55555, 6 が 666666, 7 が 7777777, 8 が 88888888, 9 が 999999999 に置き換わる. 1 は 1 のまま残る.

例えば, S が 1324 の場合, 翌日には 1333224444 になり, 翌々日には 133333333322224444444444444444 になる.
あなたは 5000 兆日後に文字列がどのようになっているか知りたい. 5000 兆日後の文字列の左から K 文字目は何か？

制約

  • S は 1 文字以上 100 文字以下の文字列.
  • K は 1 以上 10^{18} 以下の整数.
  • 5000 兆日後の文字列の長さは K 文字以上である.

入力例
1214
4

出力例
2

5000 兆は 5 × 10^{15} なので 1 文字目ですら 2 以上の数が来てしまうとその文字に決定してしまいます。

結局の所、この問題は 1 が 1 文字目から K 回以上連続しているか？ という問題に帰着します。　
よって出力する文字は

  • 文字列 𝑆 において、1 文字目から 𝐾 文字目まで全て 1 であれば、1
  • そうでなければ、答えは 𝑆 中に初めて出現する 2 以上の文字

と考えられます。

今回は連続する 1 と その次にくる数字をキャプチャする正規表現 ^(1*)([1-9]*)$ を使用します。
C++ と Python による実装例は以下のようになります。

c++
int main() {
  string S;
  long long K;
  cin >> S >> K;
  smatch m;
  regex_match(S, m, regex("^(1*)([1-9]*)$"));
  cout << ((m.length(1) >= K) ? '1' : m.str(2).front()) << endl;
  return 0;
}
python
import re

m = re.match(r'\A(1*)([1-9]*)\Z', input())
print('1' if len(m.group(1)) >= int(input()) else m.group(2)[0])

制約から正規表現のグループいずれかにはかならずマッチします。

正規表現の利点は for やら if を書かなくて済むというところでしょうか。

ABC 066 B - ss

問題文
同じ文字列を 2 つ並べてできる文字列のことを偶文字列と呼ぶことにします。 例えば、 'xyzxyz' や 'aaaaaa' は偶文字列ですが、'ababab' や 'xyzxy' は偶文字列ではありません。

アルファベットの小文字からなる偶文字列 S が与えられます。 S の末尾の文字を 1 文字以上消して作れる偶文字列のうち、最も長い偶文字列の長さを求めて下さい。 与えられる入力では、条件を満たす 1 文字以上の文字列が存在することが保証されています。

制約

  • 2≤|S|≤200
  • S は小文字のアルファベットのみからなる偶文字列である。
  • S に対して、条件を満たす 1 文字以上の文字列が存在する。

入力例
abaababaab

出力例
6

まず最初に、最後の文字は全く関係なく、むしろ邪魔であることに注意してください。以下では対象の文字列 S から末尾の文字を削除した文字列に対して議論します。

繰り返しに着目することで、最長の偶数列を取得する正規表現は ^([a-z]+)\1 とできることに気がつきます。

C++ での解答は以下のようになります。

c++
#include <boost/xpressive/xpressive.hpp>
namespace xp = boost::xpressive;
  
int main() {
  string S;
  cin >> S;

  S.pop_back();
  xp::smatch m;
  const xp::sregex re = xp::sregex::compile("^([a-z]+)\\1");
  xp::regex_search(S, m, re);
  cout << m.str().length() << endl;
  return 0;
}

STL の正規表現では後方参照できなさそうだったので、 Boost の正規表現を用いています。

今まで Boost の 正規表現は何度か試したのですが、コンパイルが通らない場合が結構あり、エラー文が長すぎてコードテストではログをすべて見れないので諦めていましたが、だいたい名前の衝突が原因となっていることが多いと気づいたので xpressive 名前空間は using 宣言しないようにしてます。

今回は動的な正規表現を用いていますが静的な正規表現を用いても構いません。
Boost の xpressive は再帰などにも対応しているため、Boost が使える環境であればできることの幅がかなり広がります。

Python での解答は以下になります。

python
import re

S = input()
m = re.search(r'\A([a-z]+)\1', S[:len(S) - 1])
print(len(m.group(0)))

ABC 049 C - 白昼夢

問題文
英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。

T の末尾に dream dreamer erase eraser のいずれかを追加する。

制約

  • 1≦|S|≦10^5
  • S は英小文字からなる。

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

出力
S=T とすることができる場合 YES を、そうでない場合 NO を出力せよ。

入力例
erasedream

出力例
YES

AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～
にもある有名な問題です。ただしリンク先ではやはり正規表現での解法は紹介されていないです；；

dream, dreamer, erase, eraser のいずれかが連続した文字列かどうか照合するのに必要な正規表現は
^(?:dream(?:er)?|eraser?)+$
で表すことができます。キャプチャする必要ないのでキャプチャしない括弧を使っています。
C++ と Python での解法は以下のようになります。

c++
int main() {
  string S;
  cin >> S;
  const regex re = regex("^(?:dream(?:er)?|eraser?)+$");
  cout << (regex_match(S, re) ? "YES" : "NO") << endl;
  return 0;
}
python
import re

print ('YES' if re.search(r'\A(?:dream(?:er)?|eraser?)+\Z', input()) else 'NO')

キーエンス プログラミング コンテスト 2019 B - KEYENCE String

問題文
連続した部分文字列 (空でも良い) を 1 度だけ取り除くことで keyence に変換することができる文字列をキーエンス型文字列と呼ぶことにします．

英小文字のみから成る文字列 S が与えられるので，S がキーエンス型文字列かどうか判定してください．

制約

  • S の長さは 7 以上 100 以下
  • S は英小文字のみから成る

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

S

出力
S がキーエンス型文字列なら YES を，そうでないなら NO を出力せよ．

入力例
keyofscience

出力例
YES

愚直に対応する正規表現を考えると
(.*)keyence|k(.*)eyence|ke(.*)yence|key(.*)ence|keye(.*)nce|keyen(.*)ce|keyenc(.*)e|keyence(.*)
となります。実際、全体マッチならこれでいいです。
もうちょっと難しくなったら、ループとかで正規表現の文字列作ったほうがいいと思います。

c++
int main() {
  string S;
  cin >> S;
  const regex re("(.*)keyence|k(.*)eyence|ke(.*)yence|key(.*)ence|keye(.*)nce|"
                 "keyen(.*)ce|keyenc(.*)e|keyence(.*)");
  cout << (regex_match(S, re) ? "YES" : "NO") << endl;
  return 0;
}

随分とどんくさい正規表現になりますが、正直、解答例と比べるとだいぶスッキリしています。

さいごに

正規表現は思いつきさえすれば、正攻法よりもかなりコードが短くて済むため、時短処理できます。
今まで使ってこなかった方も一度検討してみてはいかがでしょうか。

それでは！

Discussion