sed の花嫁
sed で AtCoder の問題を解いていきます. AtCoder の執筆当時の環境では GNU sed 4.4 が使われていました. これを動作環境ということにします.
2026 年久しぶりにこの記事を自分で読んでてキレイに書き直したい欲が湧き更新しています.
当然まだ sed 使えるだろうから今のバージョンを確認しようとしたら, なんと消えていました...
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) に実行される」を表現する.
そしてこの問題で与えられるのは二行の文字列なので, 「一行目なら削除する, さもなくば s コマンドを実行する」とだけすれば十分.
1d;s/.*\(.\)$/\1/
ABC149/A - Strings 🌝🌝🌝🌝🌝
2つの文字列が与えられるので, 順番を逆にして結合した文字列を出力せよ.
"abc def" => "defabc"
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 🌝🌝🌝🌝🌝
100 の倍数であることは文字列として見たときに末尾が 00 で終わることと同値.
/00$/cYes
cNo
ABC183/A - ReLU 🌝🌝🌝🌝🌝
与えられる文字列が - で始まっていたら, 0 に置き換える. それ以外なら何もしない.
置き換えは c コマンドで出来て,
/^-/c0
入力に - があるとしたら先頭以外ありえないので, 先頭判定の ^ は実はなくても良く,
/-/c0
で十分.
ABC166/A - A?C 🌝🌝🌝🌝🌝
入力が ABC であるかどうかを見る.
もっと言うと B を含むかどうか見るだけでも十分で,
B があれば ARC を出力し, そうでなければ ABC を出力すればいい.
/B/cARC
cABC
ABC154/B - I miss you... 🌝🌝🌝🌝🌝
与えられる文字列の全ての文字を x に置換せよというまんまの問題.
s/./x/g
丁寧に説明すると . は全ての一文字にマッチする記号.
最後の g はマッチする箇所全てに置換を適用することを表すフラグ.
ABC162/A - Lucky 7 🌝🌝🌝🌝🌝
問題に書いてある通り /7/ を含むか見る.
/7/cYes
cNo
このようなパターンマッチを一回すればいいだけのA問題は他にもいくらでも列挙できるけど, そろそろ飽きてきたのでやめる.
やや難
ちゃんと正規表現知ってますかとか, 問題をどこまで sed に変換できるかとか, そういう一番楽しい難易度.
ABC145/B - Echo 🌝🌝🌝🌝🌝
文字列が与えられる. これがある文字列を2つ繰り返して結合したものになっている
sed が扱うパターンは慣例として正規表現と呼ばれてはいるが, 実際には前方参照という機能拡張によって厳密には正規表現ではなく, もっとより強い何かになっている.
繰り返しになっていることは
^\(.*)\1$
という正規表現で表現できる.
1d
/^\(.*\)\1$/cYes
cNo
ABC222/A - Four Digits 🌝🌝🌝🌝🌚
与えられる4桁以下の整数をいわゆるゼロ埋めして4桁の文字列に変換せよ.
頭に 0 を十分（4つ以上）付けて, 末尾の四文字を出力する.
s/^/0000/
s/.*\(....\)$/\1/
ABC151/A - Next Alphabet 🌝🌝🌝🌚🌚
z ではない小文字アルファベットが一文字与えられる.
ABC 順でその次のアルファベットを出力せよ (a → b, b → c, ..., y → z).
z を除けば与えられる入力は 25 通り. 変換も 25 パターンだけ. 全列挙しよう.
一文字を一文字に変換する対応表が決まっているような置換は y コマンドを知ってると少し楽.
例えば,
y/123/ABC/
は, 1 を A に, 2 を B に, 3 を C に置換するという意味.
というわけで,
y/abcdefghijklmnopqrstuvwxy/bcdefghijklmnopqrstuvwxyz/
ABC251/A - Six Characters 🌝🌝🌝🌚🌚
長さが 1 または 2 または 3 の文字列
これを適切な回数繰り返して長さ 6 の文字列を作り, 出力せよ.
素直に読むと
しかしもっとズボラに次のようにしてよい.
十分な回数（例えば6回）繰り返せば必ず 6 文字以上にはなる.
それの先頭6文字を拾う.
s/.*/&&&&&&/ # 6 回繰り返し
s/^\(......\).*/\1/ # 頭の6文字を拾って残りを捨てる
キーエンスプログラミングコンテスト2019/A - Beginning
入力がちょうど4つの数字であることに注意すると, 問題は次のように言い換えられる.
与えられる文字列に 1 9 7 4 の全てが出現するか確認せよ.
各文字について, 出現したかどうかチェックして, 出現したらカウントする. 最後にカウントが 4 になってたらOK. 入力の文字列は自由にイジっても大丈夫そうなので, パターンラインの頭に @ を追加することでカウントしよう. @ という文字は, 入力に含まれないはずの文字から選んだだけで意味はない.
s/^/@/ # カウント +1 する
/@@@@/ # カウントが 4 以上あること
これを使って次のようになる.
/1/s/^/@/
/4/s/^/@/
/7/s/^/@/
/9/s/^/@/
/@@@@/cYES
cNO
パターンを全列挙する系
例えば sed には整数といったデータを扱う方法は無いので「二つの整数が与えられるのでその和を出力せよ」といった問題は普通には解けない.
しかし実はその整数が 1 以上 3 以下であることが保証されてるなら, ありえる入力は全部で 9 通りしかないので, これを全列挙してしまえばいい.
/1 1/c2
/1 2/c3
/1 3/c4
...
/3 3/c6
ABC175/A - Rainy Season 🌝🌝🌝🌝🌚
3文字が与えられる. この中で R という文字が最長で何文字が連続して出現しているか数えよ.
全部で3文字なのだからありえる R の長さは 0 以上 3 以下の4通りしかない。
パターンマッチングは上から順に実行されるので, 長いものから順に書いていけばよい.
/RRR/c3
/RR/c2
/R/c1
c0
ABC229/A - First Grid 🌝🌝🌝🌝🌚
2x2 のグリッドからなる迷路が与えられるのでスタートからゴールまで到達可能か判定せよ.
制約をよく読めば, 到達不能なパターンは次の二通りしかないことがわかる.
#.
.#
または
.#
#.
この2つだけを文字通りパターンマッチして判定すればよい.
二行の入力に関するマッチをしたいわけだが, sed は基本的には一行ずつ読んで, 一行に関するパターンマッチを行う.
そこで N コマンドは次の行を追加で読むことが出来る（改行文字が挟まることに注意）. これを使えば二行以上に渡るパターンマッチが出来るようになる.
また c コマンドは今の入力を捨てて別な文字列で置き換える. これで Yes または No の出力が出来る.
N
/#\.\n\.#/cNo
/\.#\n#\./cNo
cYes
注意として, c コマンドは続く文字列を改行まで読む.
c コマンドの次の行を一行にまとめて書いてはいけない.
cYes; cNo
# => "Yes; cNo" が出力される
ABC225/A - Distinct Strings 🌝🌝🌚🌚🌚
三文字が与えられる. この文字を並び替えることで何通りの異なる文字列が作れるか答えよ.
算数です. 入力の三文字の中で同じものがどれだけあるかで決まる.
- 3文字とも同じ: 1 通り
- 内2文字が同じ: 3 通り
- 全て異なる: 6 通り
この判定が sed でできればOK.
入力の内同じものを含むことのパターンマッチは前方参照を使うと実現できる. またパターンマッチは宣言した順番にチェックされることも重要. というのも, 異なるということをチェックできないわけだが, これを「どのパターンにもマッチしなかった」ことで表現する.
# 3文字同じ
/\(.\)\1\1/c1
# それ以外で, 内2文字が同じ（三通りある）
/\(.\)\1./c3
/\(.\).\1/c3
/.\(.\)\1/c3
# それ以外 == 全て異なる
c6
sed で解くならこんなもんだと思うが, 現実では sed 以外の選択肢を考えるべきだろう.
ABC203/A- Chinchirorin 🌝🌝🌝🌚🌚
3つのサイコロの出目が与えられる.
この内ある二つが同じ出目であるなら残りの出目を出力せよ. そうでなければ, 0 を出力せよ.
これも入力のうちに同じものが含まれてるかをチェックすればよい.
前の問題と同じで, 例えば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
# それ以外?
???
どれかの 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 では簡単ではない.
つまり難しさポイントは二つあって,
- 最長の方だけを採用すること
-
ACACXGTにはACACとGTという二つの候補があるが, これらのうちACACだけを採用すること
-
- その長さを得ること
-
ACACという文字列があったときに, これの長さである4を得ること
-
この二つをいっぺんに解決するのがパターン全列挙だ. 入力の長さが最大で 10 ということは, 最長文字列の長さは 0 以上 10 以下の 11 通りしかないことがわかる. 全列挙できる.
例えば, 長さがちょうど 7 の /[ACGT]*/ は,
/[ACGT]\{7\}/
と書ける.
これを長いものから順に書いていけば, 最長のものだけが採用されるようになる.
/[ACGT]\{10\}/c10
/[ACGT]\{9\}/c9
/[ACGT]\{8\}/c8
/[ACGT]\{7\}/c7
/[ACGT]\{6\}/c6
/[ACGT]\{5\}/c5
/[ACGT]\{4\}/c4
/[ACGT]\{3\}/c3
/[ACGT]\{2\}/c2
/[ACGT]\{1\}/c1
c0
パワープレイをする
e コマンドや, s コマンドにある e フラグは内部で popen を呼び出すので, Bash と同じことを sed の内部で出来る. これを使えば, 入力を少し置換して後は bash に流せば ok みたいな解き方が出来る. もはや何でもアリになってくるのでパワープレイと呼ぶ.
これが果たして AtCoder の内外で実用的かどうかは知らない.
最初から bash を呼べばいいので.
Hello World (cowsay)
$ 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 🌝🌝🌝🌝🌚
入力は三文字の文字列だが, これが一桁と一桁の掛け算を表現している. 計算してほしい.
3x7
二文字目は掛け算を表す記号として x であることが保証されている.
これを適当に置換して sh に計算させよう.
s/x/*/
s/.*/echo $((&))/e
例えば 3x7 という文字列が1つ目の s で 3*7 になり, 2つ目の s で echo $((3*7)) になる. e フラグはこれを実行する.
ABC256/A - 2^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// # さもなくば, s コマンドを実行して一行目を消す
ABC137/B - One Clue 🌝🌝🌝🌚🌚
2つの整数
$ 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つの整数
さんざん同じようなものをやってたので何も怖くない. やはり
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
Discussion