sed の花嫁

sed で AtCoder の問題を解いていきます.
AtCoder の現時点の最新環境では GNU sed 4.4 が使われており, これを動作環境ということにする.

sed らしく解けるものを解く

文字列処理をするだけの問題は sed を使うと自然に解決します（主には ABC の A 問題が対象になる）. 自然度合いを 🌝🌝🌝🌚🌚 で表現しました.

ABC254/A - Last Two Digits 🌝🌝🌝🌝🌝

3桁の数字が与えられる. この末尾2桁を出力せよ.

文字列処理の問題だと思って読み替える.
ほとんどそのままだが, 3文字の文字列が与えられるので末尾の2文字を出力せよという問題と思える.
これをするには s コマンドを使って,

s/.\(..\)/\1/

とする.
簡単にシェル上で次を実行すれば動作確認ができる.

echo 123 | sed 's/.\(..\)/\1/'
# 23 が出力されればOK

これでもいいんだけど...

問題を読み替えて, 入力は三文字で固定なので, ただ1文字目を削除しろという問題だと思う.
文字を削除するのは空文字への置換 s/.// をすればよい. 置換はデフォルトでは最初にマッチした文字列に一度だけしか適用されないので, 何も考えなければ一文字目の削除になる.

s/.//

これで解けた.

ABC247/A - Move Right 🌝🌝🌝🌝🌝

これも文字列処理だとして問題を読み替える.

4文字が与えられる. 頭に 0 を付け足し, 末尾の一文字を削除せよ.
先頭のことは ^, 末尾のことは $ で表現できる.
これら2つをそれぞれ s コマンドで置換すればよい.

s/^/0/
s/.$//

読みやすさのために1コマンドを一行ずつで書いてるが, ; で区切って一行に圧縮してもよい.

s/^/0/;s/.$//

ABC244/A - Last Letter 🌝🌝🌝🌝🌝

二行に渡って2つの文字列が与えられる.
1つ目は破棄せよ.
2つ目は末尾の一文字だけを出力せよ.

sed のコマンドは全てアドレスを指定することが出来る.
アドレスには行番号がそのまま使える.
2 { ... } と書けば2行目にだけ {} の中身が実行される（中身が一つのコマンドだけなら {} は省略可）.
2!{ ... } と書けば2行目 以外 に実行される.

2 {
  s/.*\(.\)$/\1/
}
2!{
  d  # 削除
}

これで解けているのだが, アドレスの説明をしたいが為に冗長になっている.

d コマンドは入力を破棄し, 即座にそのサイクル（入力を一行読んでプログラムを実行するまでのステップ）を終了する. なので d コマンドに続けて別なコマンドを書けば, これは「d コマンドが実行されなかったとき (else) に実行される」を表現する.

# 一行目なら削除する
# さもなくば (else) `s` を実行する
1d;s/.*\(.\)$/\1/

ABC149/A - Strings 🌝🌝🌝🌝🌝

2つの文字列が与えられるので, 順番を逆にして結合した文字列を出力せよ.

2つの文字列は空白区切りで一行で与えられる.
sed の文字列はいわゆるトークンじゃなくて行単位（改行文字が唯一の区切り文字）なので, 特に気にせず一つの文字列として解釈すればよい.

パターンの中でグルーピングするのは \( \) を使い, \1 とか \2 でこのグループを参照できる.

s/^\(.*\) \(.*\)$/\2\1/

ABC224/A - Tries 🌝🌝🌝🌝🌝

末尾が er で終わるか ist で終わるか判定せよ.

入力はこのどちらかであることが保証されてるので, er で終わるかどうかだけ判定すれば十分. コマンドの前にアドレスを指定できることは先程述べたが, ここにパターンマッチをアドレスとして使うこともできる. これによって, このパターンにマッチした場合だけこのコマンドを使うという書き方が出来る.

/er$/ {
  cer
}  # /er$/ にマッチした場合だけ {} の中身が実行される

1コマンドなので {} は省略できて

/er$/cer

でも同じ.

c コマンドは今の読んでる行を, 指定した文字列 (今の場合は er) に置き換える. c に続く文字列は改行までを読み取るので注意. 別なコマンドを一行に続けて書こうとしてはいけない.
またさらに c コマンドは実行した時点でプログラムのループを終える. したがって, 続けて別なコマンドを書いておくと, これは「c が実行されなかった場合 (else)」を表す.

/er$/cer
cist

/er$/ の場合は er に置き換える, さもなくば (else) ist に置き換える.

ABC223/A - Exact Price 🌝🌝🌝🌝🌝

$X$ が 100 の倍数かどうか判定する問題.
100 の倍数であることは文字列として見たときに末尾が 00 で終わることと同値.

ABC183/A - ReLU 🌝🌝🌝🌝🌝

与えられる文字列が - で始まっていたら, 0 に置き換える. それ以外なら何もしない. 置き換えは c コマンドで出来て,

/^-/c0

入力のされかたから, - はあるとしたら先頭以外ありえないので, ^ は実はなくても良く,

/-/c0

で十分.

ABC166/A - A?C 🌝🌝🌝🌝🌝

入力が ABC であるかどうかを見る.
或いは B を含むかどうか見るだけでも十分.

ABC162/A - Lucky 7 🌝🌝🌝🌝🌝

問題に書いてある通り /7/ を含むか見る.

パターンマッチを一回すればいいだけの問題は他にもいくらでも列挙できるけど飽きたのでやめよう.

ABC154/B - I miss you... 🌝🌝🌝🌝🌝

与えられる文字列の全ての文字を x に置換せよというまんまの問題.

s/./x/g

丁寧に説明すると . は全ての一文字にマッチする記号.
最後の g はマッチする箇所全てに置換を適用することを表すフラグ.

ABC175/A - Rainy Season 🌝🌝🌝🌝🌚

3文字が与えられる. この中で R という文字が最長で何文字が連続して出現しているか数えよ.

連続するのも最長で3だと分かって, 結局3通りのことだけを考えれば良いのだから, このくらいは全列挙しよう.

/RRR/c3
/RR/c2
/R/c1
c0

ABC145/B - Echo 🌝🌝🌝🌝🌝

文字列が与えられる. これがある文字列を2つ繰り返して結合したものになっている $(S=T \cdot T)$ 形になっているか判定せよ.

sed が扱うパターンは慣例として正規表現などと呼ばれるが, 実際には前方参照という拡張のために正規表現ではなく, より強い何かになっている.

繰り返しになっていることは

/^\(.*)\1$

で判定できる.

1d
/^\(.*\)\1$/cYes
cNo

ABC229/A - First Grid 🌝🌝🌝🌝🌚

2x2 のグリッドからなる迷路が与えられるのでスタートからゴールまで到達可能か判定せよ.
制約をよく読めば, 到達不能なパターンは次の二通りしかないことがわかる.

#.
.#

または

.#
#.

この2つだけを文字通りパターンマッチして判定すればよい.
二行の入力に関するマッチをしたいわけだが, sed は基本的には一行ずつ読んで, 一行に関するマッチを行う.
わけだが, N コマンドは次の行を追加で読むことが出来る（改行文字を挟んで二行を同時に読むことが出来る）.
また c コマンドは今の入力を捨てて別な文字列で置き換える. これで Yes または No の出力が出来る.

N
/#\.\n\.#/cNo
/\.#\n#\./cNo
cYes

注意として, c コマンドは続く文字列を改行まで読む. 上は四行に分けて書いたが, c コマンドに続く改行は省略できない.
あと当たり前だが, パターン中の . は正規表現の . として解釈されないようにエスケープする必要がある.

キーエンスプログラミングコンテスト2019/A - Beginning

入力がちょうど4つの数字であることから問題は次のように言い換えられる.

与えられる文字列に 1 9 7 4 の全てが出現するか確認せよ.

各文字について, 出現したらカウントを一回する.
最後にカウントが 4 になってたらOK.
入力の文字列は自由にイジっても大丈夫そうなので, パターンラインの頭に @ を追加することでカウントしよう.
@ という文字は, 入力に含まれないはずの文字から選んだだけで意味はない.

s/^/@/  # カウント +1 する

/@@@@/  # カウントが 4 以上あること

これを使って次のようになる.

/1/s/^/@/
/4/s/^/@/
/7/s/^/@/
/9/s/^/@/
/@@@@/cYES
cNO

ABC151/A - Next Alphabet 🌝🌝🌝🌚🌚

与えられる (z ではない) アルファベット一文字について, その次のアルファベットを出力せよ.

z を除けば与えられる入力は 25 通り. こんくらい列挙しよう.
一文字を一文字に変換するだけの置換は y コマンドで実現できる.

例えば,

y/123/ABC/

は, 1 を A に, 2 を B に, 3 を C に置換するという意味.

というわけで,

y/abcdefghijklmnopqrstuvwxy/bcdefghijklmnopqrstuvwxyz/

ABC251/A - Six Characters 🌝🌝🌝🌚🌚

まず, 文字列 $S$ を十分（長さが 6 以上になることが保証されるまで）繰り返した文字列を得,
これの頭 6 文字を出力する.

s/.*/&&&&&&/  # 6 回繰り返し
s/^\(......\).*/\1/  # 頭の6文字を拾って残りを捨てる

6文字拾う処理がやや苦しい.

ABC222/A - Four Digits 🌝🌝🌝🌚🌚

頭に 0 を十分（4つ以上）付けて, 末尾の四文字を出力する.

ABC225/A - Distinct Strings 🌝🌝🌚🌚🌚

三文字が与えられる. この並び替えて何通りの文字列が作れるだろうか.

結局入力の三文字の中で同じものがどれだけあるかで決まる.

• 3文字とも同じ: 1 通り
• 内2文字が同じ: 3 通り
• 全て異なる: 6 通り

入力の内同じものを含むことのパターンマッチは前方参照を使うと実現できる. またパターンマッチは宣言した順番にチェックされることも重要. というのも, 異なるということをチェックできないわけだが, これを「どのパターンにもマッチしなかった」ことで表現する.

# 3文字同じ
/\(.\)\1\1/c1
# それ以外で, 内2文字が同じ（三通りある）
/\(.\)\1./c3
/\(.\).\1/c3
/.\(.\)\1/c3
# それ以外 == 全て異なる
c6

sed で解くならこんなもんだと思うが, 現実では sed 以外の選択肢を考えるべきだろう.

ABC203/A- Chinchirorin 🌝🌝🌝🌚🌚

これも入力のうちに同じものが含まれてるかをチェックすればよい.
前の問題と同じで, 例えば1つ目と2つ目が同じことを次のパターンでチェックする

# 1つ目と2つ目が同じ
/\(.\) \1 ./

上記のときには3つ目を出力したいので,

s/\(.\) \1 \(.\)/\2/

でできた.
同様に1つ目と3つ目が同じパターン, 2つ目と3つ目が同じパターン, そしてそれ以外を列挙してくのだが,

s/\(.\) \1 \(.\)/\2/  # 1st==2nd
s/\(.\) \(.\) \1/\2/  # 1st==3rd
s/\(.\) \(.\) \2/\1/  # 2nd==3rd
# それ以外?
???

1つ目の s コマンドによって置換が行われたなら, 後に続くパターンマッチングは実行されてほしくない.
一つはアドレスで制御する方法だが, t コマンドは直前の置換が成功した場合にジャンプ (goto) が出来る.
: でラベルを作りこのラベルを指定したジャンプが出来る.
今回は置換に成功したらそれ以上何もしたくないので, プログラムの末尾にラベルを貼ってそこにジャンプすればよい.

s/\(.\) \1 \(.\)/\2/  # 1st==2nd
tend
s/\(.\) \(.\) \1/\2/  # 1st==3rd
tend
s/\(.\) \(.\) \2/\1/  # 2nd==3rd
tend
c0
:end

tend で「直前の s に成功したら end というラベルまでジャンプする」という意味になる.

ABC122/B - ATCoder 🌝🌚🌚🌚🌚

与えられる文字列の内, /[ACGT]*/ という部分文字列であって, 最長のものの長さを答えよ.

欲しい部分文字列にマッチするようなパターンは既に与えたように簡単に書けるが, この中から最長のものを得て, そしてその長さを得るのは sed では簡単ではない. 入力の長さが最大で 10 ということは, 最長の長さは 0 以上 10 以下の 11 通りしかないことがわかる.
全部列挙すればいい.

長さがちょうど 7 の /[ACGT]*/ は,

/[ACGT]\{7\}/

と書ける. これを 10 から順にマッチすればよい（短いものが先にマッチすると正しくない）. 解答をここに書くことは控えるので, /abc122/submissions/4717811 を見てほしい.

パワープレイをする

e コマンドや s コマンドの e フラグは内部で popen を呼び出すので, Bash と同じことを sed の内部で出来る. これを使えば, 入力を少し置換して後は bash に流せば ok みたいな解き方が出来る. もはや何でもアリになってくるのでパワープレイと呼ぶ. これが AtCoder の内外で実用的かどうかは知らない.

$ echo Hello World | sed 's/.*/cowsay &/'
cowsay Hello World

$ echo Hello World | sed 's/.*/cowsay &/e'
 _____________
< Hello World >
 -------------
        \   ^__^
         \  (oo)\_______
            (__)\       )\/\
                ||----w |
                ||     ||

$ echo Hello World | sed 's/.*/cowsay &/; e'
 _____________
< Hello World >
 -------------
        \   ^__^
         \  (oo)\_______
            (__)\       )\/\
                ||----w |
                ||     ||

ABC232/A - QQ solver 🌝🌝🌝🌝🌚

入力は三文字の文字列だが, これが一桁と一桁の掛け算を表現している. 計算してほしい.

二文字目は掛け算を表す記号として x であることが固定されている.
これを適当に置換して sh に計算させよう.

s/x/*/
s/.*/echo $((&))/e

例えば 3x7 という文字列が1つ目の s で 3*7 になり, 2つ目の s で echo $((3*7)) になる. e フラグはこれを実行する.

ABC256/A - 2^N 🌝🌝🌚🌚🌚

入力 $N$ に対してべき乗 $2^N$ を出力せよ.
べき乗は $1$ の左シフト $1 \texttt{<<} N$ と思って良い.

Bash (sh の互換性については知らない) で書くと

# 2の5乗
echo $((1<<5))

となる. このコマンドを sed で作れば良くて,

s/.*/echo $(( 1 << & ))/

で作れた.
最後に e フラグをつけるか, 別途 e コマンドを実行させて,

s/.*/echo $(( 1 << & ))/e
s/.*/echo $(( 1 << & ))/; e  # これでも同じはず

しかし最初から Bash で解くのとそう変わらない.

ABC150/B - Count ABC 🌝🌝🌝🌚🌚

2行に渡って2つの文字列が与えられる.
1つ目は破棄せよ.
2つ目について, ABC という文字列がいくつ含まれるか数えよ.

sed は整数をプリミティブに扱う手段を持たないので, 簡単に数えることはできないが,

• s コマンドで ABC を一つずつ潰してく
• なんとかしてカウントをインクリメントする
• これをループする

という方法で原始的なカウントが出来そう.

:loop           # ループのためのラベル
/ABC/ {         # /ABC/ がマッチしたら次を実行
  s/ABC//;      # 一つだけ ABC を潰す
  ???????       # なんかしてインクリメント
  bloop;        # ループに戻る (continue)
}
??????          # なんかしてカウントしたものを数値に変換して出力

カウントするのに ホールドスペース を使う.
この記事でホールドスペースの概念は初出なはずなので詳細に説明する.
sed は入力から一行ずつ読んで処理するが, この一行を持っておく空間（これはパターンスペースとか呼ばれる）とはまた別に, ホールドスペースを持つ.
テトリスにおけるホールド と全く同じで, 一時的に退避させて後から読むなどといったことが出来る. テトリスを知らないのはヤバいのでやってください.

• ホールドスペース
  • 最初は空文字列
  • h コマンドで, ホールドする
    • パターンスペースにある文字列をコピーする
  • g コマンドで, ホールドにある文字列をパターンスペースにコピー
  • H コマンドは h によく似てる
    • パターンスペースにある文字列を, ホールドの末尾に付け加える
    • 厳密にはまず改行文字を追加した後に, パターンの文字列を追加する
  • G コマンドは H の g 版

sed が行指向のコマンドであることと, H が改行文字を挟むことは自然な関係になっている. 最初に読まれるパターンスペースには改行は含まれないので, H をシた結果, ホールドにある文字列は改行文字を区切りとした, 配列（またはスタックやキュー）として機能する.

ホールドの解説は以上にして問題に戻る.
カウンタとして, ホールドの行数を使う. 厳密には含まれる改行文字の個数が欲しい値と一致する. インクリメントする代わりに, なんでもいいのでホールドに一行追加すればよい. これは H コマンドを一回実行することに等しい. H はちょうど一つの改行文字を追加してくれる（改行文字以外には興味がない）.

パターンに ABCXYZ という文字列があるときに, H を二回実行したとき, ホールドは次のようになっている.

\nABCXYZ\nABCXYZ

最初空文字列なので, \n から始まっており, また末尾に改行文字がないことに注意してほしい.
というわけで /\n[^\n]*/ というパターンがいくつ含まれるかを見ることが, 行数を見ること, つまりカウンタの値を読むことになる.
ひとまず単純にしておきたい気持ちから

s/\n[^\n]*/@/g

とでもすれば, @ が並んだ文字列が得られ, これの文字数を読めばよくなった. さすがに文字列を10進数に変換するのは sed では辛い（やればできるけど, やらなくていいだろう）.
wc コマンドを使おう. これの -c オプションは入力の文字数を出力してくれる. @ からなる文字列を echo して wc -c にパイプすればよい. 注意としてただ echo すると末尾に余計な改行文字を一つ付け足してくれるので, 今回はこれを抑制するために echo -n を使う.

$ echo -n | wc -c
0
$ echo -n @@ | wc -c
2
$ echo -n @@@@@@@@@ | wc -c
9

以上説明したことを組み合わせれば完成する.

1d                # 一行目は破棄して終了
:loop
/ABC/ {
  s/ABC//
  H;              # インクリメント
  bloop
};
g;                # ホールドした文字列を得る
s/\n[^\n]*/@/g
s/.*/echo -n &|wc -c/e

ホールドしてこその sed なんで.

ABC138/A - Red or Not 🌝🌝🌚🌚🌚

整数と文字列が与えられる.
整数が 3200 未満なら与えられた文字列を出力せよ.
さもなくば, red と出力せよ.

何度も言うが sed は整数という表現方法を持ってないので大小比較など出来ない.
shell に任せる.

$ a=3199
$ echo $(( a >= 3200 ))
0
$ a=3200
$ echo $(( a >= 3200 ))
1

このコマンドをそのまま使えば, 0 かどうかを見れば良くなる.

N コマンドの説明をもしかしたらまだシてなかったかも.
今読んでる行（パターンラインという）に, さらに追加で一行読んで, これをパターンラインの末尾に追加することができる.
この際には改行文字を一つ追加して区切り文字にする.

パターンラインが ABC であって次の行が XYZ のとき, N の結果, パターンラインは

ABC\nXYZ

になっている.

s/.*/echo $((&>=3200))/e
N           # 次の行を追加で読む
/^0\n/cred  # 0 なら (3200未満なら), red に置き換えて終了
s/^1\n//    # さもなくば (else), s を実行

ABC137/B - One Clue 🌝🌝🌝🌚🌚

2つの整数 $K,X$ が与えられる.
$X-K+1$ から $X+K-1$ までの整数を小さい順に列挙せよ.
（トークン区切りの空白と改行は好きなものを使って良い.）

やはり shell で解く.
$K,X$ を例えば $3,7$ で固定して書くと Bash で次のコードで解ける.

$ seq $((7-3+1)) $((7+3-1))
5
6
7
8
9

このコマンドを発行するように文字列処理すればよいだけ. もはや簡単だ.

s/\(.*\) \(.*\)/seq $((\2-\1+1)) $((\2+\1-1))/e

ARC104/A - Plus Minus 🌝🌝🌝🌚🌚

2つの整数 $A,B$ が与えられるので $X = (A+B)/2$ と $Y = (A-B)/2$ を出力せよ. $X,Y$ は整数の範囲で計算できることが分かってる.

さんざん同じようなものをやってたので何も怖くない. やはり

echo $(( (A+B)/2 )) $(( (A-B)/2 ))

というコマンドを発行できれば勝ち.
ここで注意だが,

s/^\(.*\) \(.*\)$/echo $(( (\1+\2)/2 )) $(( (\1-\2)/2 ))/e

は正しくない. s/.../.../e に使う / と除算の為の / が紛れているから. 後者の / をエスケープしても良いのだが. s のための区切り文字は / である必要がないことは知っておくべきだろう. 1byte 文字であれば実は何でも良い.

$ echo 123X456 | sed 's#X#/#g'
123/456
$ echo 123X456 | sed 'ssXs/sg'
123/456

というわけで次が正しい解答になる.

s#^\(.*\) \(.*\)$#echo $(( (\1+\2)/2 )) $(( (\1-\2)/2 ))#e