読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

【競プロのための正規表現】のためのメモ

この記事は「競プロのための正規表現」と題し、競プロに頻出の文字列の問題を正規表現でさくっと解けるようになろう!という目的のために書かれた記事、を、いつか書くためのメモです。

実際のコードも載せているので、「正規表現ってなんですか><」「競プロで正規表現って使えるの?」という人には感覚はつかんでもらえるかと思います。

競プロで使いそうな正規表現

正規表現ってなに?って人はここを見るとよさそう↓

qiita.com

よく使いそうなものだけまとめておきます。

正規表現 意味
'.' 任意の1文字
'*' 直前の文字の0回以上の繰り返し
'+' 直前の文字の1回以上の繰り返し
'?' 直前の文字が0回or1回
'[ ]' [ ]内の文字列のいずれか
'^' 正規表現の最初で用いた場合: 行頭を示す
それ以外: 否定(例: [^asd]でa, s, d以外を示す)
'$' 行末
'|' or(例: '(yes|no)'で'yes'か'no'を示す

他にも、英数字は '0-9', 'A-Z, 'a-z' という感じでまとめて表せます。

例題

ARC022 A - スーパーICT高校生

arc022.contest.atcoder.jp

文字列の中に'I', 'C', 'T'がこの順にならんでいることがあるかを判定する問題。ただし大文字小文字は問わない。

forループを書いてもいいですが順番を考慮してネストをつけたりといろいろ面倒です。

正規表現なら2行で書けます。

import re
print('YES') if re.match(r'.*[iI].*[cC].*[tT].*', input()) else print('NO')

まず、python正規表現を使うためのパッケージであるreをimportしています。

re.match(pattern, string)がstringの中に正規表現で表されるpatternがあるかを判定するメソッド

正規表現の前にrをつけているのは、pythonだとそうしないと''内でバックスラッシュがバックスラッシュとして扱われないからいつもrをつけておくことが推奨されているとのことで。

yukicoder No.341 沈黙の期間

No.341 沈黙の期間 - yukicoder

文字中で'…'(三点リーダ)が最も多く連続する個数を求めよという問題。

正規表現を使うと、注目したい部分だけ抜き出すということができます。

# -*- coding: utf-8 -*-

import re
s = input()

#'…'のかたまりだけ抜き出す
li = re.findall(r'…+', s)

mx = 0
for x in li:
    mx = max(mx, len(x))

print(mx)

re.findall(pattern, string)は、stringの中でpatternに合致する部分列のすべてをリストとして返すメソッドです。

今回は'…'が1個以上連続している部分だけ取れればいいので、例えば入力が'……いいよ…………'なら['……', '…………']というリストを得ます。

そうしたら後はそのリストの中で最大の長さを求めればいいですね。

yukicoder No.342 一番ワロタww

これがこの記事を書こうと思ったきっかけです。はい。

No.342 一番ワロタww - yukicoder

文字列中で、一番長く続く'w'の直前の文字列をすべて出力せよという問題。

これがしんどかった。連続する'w'の個数の最大値は前問と同様に求められますが、そのあとのwの直前の文字列を抜くという処理が面倒です。(最大長の'w'じゃないときは抜かないとか、'w'の直前から前の'w'の直前まで戻るとか)

正規表現でさくっといきましょう。

# -*- coding: utf-8 -*-

import re
s = input()

#先頭のwを除去
s = re.sub(r'^w+', '', s)

#全部wだったら空文字列になるので終了
if not s:
    print('')
    exit()

#「文字列www」のかたまりに分解
li = re.findall(r'[^w]+w+', s)

#単語の後ろにwがなければ空リストになるので終了
if not li:
    print('')
    exit()

#各かたまりのwの個数をカウント
cnt = []
for x in li:
    cnt.append(x.count('w'))

#wが最も多く含まれるかたまりのw以外を出力
mx = max(cnt)
for c, l in zip(cnt, li):
    if c == mx:
        print(re.sub(r'w+', '', l))

さっきよりは長くなりましたが、やっていることは少ないです。

re.sub(pattern, repl, string)は新しくでてきたメソッドですね。これはstringのうち、patternに合致する部分をreplで置き換えるメソッドです。

徹底的に「使うところだけ取り出す」「いらないところは空文字列に置換」ということをしています。

まとめ

正規表現のいいところは、正規表現さえ書けば分岐やループを自分で書く必要がない」というところだと思います。文字列をどう処理すればいいのかというのを直感的に、思ったままに実装することができます。上でも述べたように「使うところだけ取り出す」という意識を持っていれば結構使えるんじゃないでしょうか。逆に言うと、自分でさくっと実装できるような問題はわざわざ正規表現を使わなくてもいいでしょう。

果たして本当の「競プロのための正規表現」を書く日は来るのだろうか。