AtCoderに登録したら解くべき精選過去問10問をSedで解いてみた。

はじめに。

この記事は ISer Advent Calendar 2019 の13日目の記事として書かれました。そして本ブログはこれを書くために開設されました。わいわい。

先日AtCoderにおいてSedのLanguage Owner*1を獲ったのですが、軽く検索してみたところSedABSを解いた記事が見つかりません。これはオリジナリティのある記事になりそうだというわけで私が書くことにしました。需要はわかりません。

この記事の梗概。

AtCoder Beginners Selectionの1+10問を、Sedというテキスト変換などのデータ処理に特化したプログラムで解いたり解けなかったりします。またSedAtCoderの提出可能言語に含まれてはいるものの競技プログラミング向きでなく、この記事を読む層にも文法が全くわからないという方も多くいると思いますので適宜解説もがんばって加えます*2。なお解説や難易度の都合でそこそこ、いやかなり問題の順番を変更しています。こうした難易度の逆転現象も主流でない言語で問題を解く面白さの一つだと思います。

第1問:ABC086A - Product

/[24680]\>/cEven
cOdd

実際の提出

まずは入出力のお話ですね。Sedでは入力ファイルを1行ずつ受け取り、各行ごとにプログラムの処理を順番に行います。そしてその処理とは基本的にテキストの置換やパターンマッチです。プログラムを通り抜けた時点で残っていたテキストが、その行での出力というわけです。

さて本問題ですが、わざわざA\times Bを計算せずとも入力に偶数が含まれていれば”Even”、奇数だけなら"Odd"を出力すればよく、そして偶数とは2,4,6,8,0のいずれかで終わる数のことです。というわけで「(2,4,6,8,0のいずれか)+(空白あるいは行末)」という部分を見つければ"Even"、さもなくば"Odd"を出力します。

1行目の/wasawasa/は「wasawasa」を見つければ直後のコマンドを実行、さもなくばその次のコマンドから実行するもので、cwasawasaとはその行を「wasawasa」に書き換えその行に関する処理をその場で終えるコマンドです*3。また[wai]は(w,a,iのいずれか)を指し、\<,\>は通常文字(a-zA-Z0-9_)以外との境界を指します。よって、今回の場合は「2,4,6,8,0のいずれかの直後に空白あるいは行末が存在する」というパターンを探しているわけです。

第9問:ABC049C - 白昼夢 / Daydream

/^\(dream\(er\)\?\|eraser\?\)*$/cYES
cNO

実際の提出

前問で見た正規表現によるパターンマッチはこのような問題で大活躍します。

入力文字列を後ろから見ていくのが想定解法らしいですが、実はAtCoderで使えるSedは30000文字程度を超えて置換しようとすると正常動作をしなくなりますし、3000回程度のコマンド操作が実行時間制限の限界になります*4。そのため最大100000文字を扱う本問題において、後ろから処理をする想定解法はSedとしては箸にも棒にもかかりません。SedにはSedらしい解法があります。

Sedでは(,),|,?,+,/,\などの文字は、入出力のための文字とコマンドのための文字を区別するために、コマンドとして扱う際は前に\をつけてエスケープします。そこで可読性のために\を外して1行目を見ると次のようになります。

/^(dream(er)?|eraser?)*$/cYES

?は0あるいは1回の繰り返し、*は0回以上の繰り返しを表し、^は行頭、$は行末、|は「または」を指します。よってこのコードは「(dream,dreamer,erase,eraserのいずれか)を0回以上繰り返したものが行頭と行末の間にぴったり存在する」というパターンが存在するか否かを判定しています。これならパターンを探すだけでそれをどうこうしてはいませんし、コマンドも1回しか呼び出していません。他の言語より楽に書け、むしろ複雑に書くことが困難であるような例ですね。

第2問:ABC081A - Placing Marbles

s/0//g
/.../c3
/../c2
/./c1
c0

実際の提出

パターンマッチとc以外のコマンド、sが出てきました。ここからがSedの本番です。s/boku/watashi/は最初に見つけたbokuというパターンをwatashiというパターンに置換するコマンドで、gは最初のものだけでなくすべてを置換するためのオプションです。またパターンマッチに使っている.は任意の1文字を表します。本コードは0をすべて空文字列に置換、つまり消去してから残った文字数=元々含まれていた1の数を出力しています。

第0問:PracticeA - Welcome to AtCoder

N
s/ \|\n/+/g
N
s/\(.*\)\n\(.*\)/echo $((\1)) \2/e

実際の提出

Nは現在読んでいる行の次の行も読み込むコマンドです。プログラムの1行目で入力の2行目まで読んだ後、2行目で空白及び\nつまり改行をすべて+に置換しています。そしてプログラムの3行目で入力の3行目まで読み込んだ時点で、現在読んでいるテキストは以下のようになっています。

a+b+c
s

最後に4行目ですが、\1,\2はそれぞれキャプチャした一つ目,二つ目の文字列を指します。「任意の文字列+改行+任意の文字列」つまり今回は「a+b+c,\n,s」を読んで、echoを呼び出して\1=a+b+cを評価し続けて空白と\2=sを出力しています。eは呼び出したechoを実行するオプションです*5

Sedは入力をテキストとして扱うことしかできないので、直接数値として計算をすることができません。巧みな文字列操作でインクリメントを行い足し算することも可能ですが、echoを呼び出してしまった方が簡単だしコマンド操作が少なくなって速いのでそのようにしました。

第7問:ABC085B - Kagami Mochi

1d;:;$!{N;b}
:d;s/\<\(\(\w*\)\>.*\)\n\2\>/\1/;td
s/\w//g;s/\n/+1/g
s/.*/echo $((1&))/e

実際の提出

段々とコードがわさわさしてきましたね。cコマンドなどの一部例外を除き、改行の代わりに;によってコマンドの区切りを示すことができます。またこの問題は、相異なる直径を持つ餅を数えればそれが解になります。

1行目は1d,:,$!{N;b}の3つに分かれます。dは行を消去するコマンドで、1を前につけることで「1行目ならば実行」を意味しています。同様に$は入力の最後を指しており、$!によって「最後でなかったら実行」を表しています。:はラベルを張るコマンドであり、bは対応するラベルへ無条件にジャンプするコマンドです。よって1行目全体として、入力の1行目は削除しそれ以降は入力の最後までまとめて読み込んでしまうというコードです。ラベルを用いてループを実現できるのがポイントです。

2行目は:d,s~~~~~,tdの3つに分かれます。:dはラベルを張ってそれにdという名前をつけるもので、tdはtコマンド、前でsコマンドが実行されていたなら対応するラベルにジャンプというコマンドをラベルdに対して行うものです。さて間のsコマンドが難読ですね。キャプチャの括弧が入れ子になっています。この場合、外側が\1で内側が\2になります。\wは通常文字(a-zA-Z0-9_)を表し、そのため\2がキャプチャしている\<\w*\>は途中の1単語ぴったりを指しています。よってマッチしているパターンは「単語\2、間、\2と同一の単語」というもので、それを「\2、間」に減らしています。つまり2行目全体で、同じ数字を一つにまとめることをしています。

あとは残った行数を数えて出力すれば良いので、3行目で数字をすべて消し去り改行を+1という文字列に変えています。改行文字は行数-1だけあるので、先頭に1を追加して式を評価してやれば答えとなります。

第6問:ABC088B - Card Game for Two

1d
s/\<.\>/0&/g;s/\<..\>/0&/g;s/ /<0123456789>/g
:;s/\<\(\(\w*\)\(.\)\w*\)\(<\w*\3\w*\(.\)\w*>\)\(\2\5\w*\)\>/\6\4\1/g;t
s/<\w*>/ /g;:0;s/\<0//g;t0
s/\<\(\w*\) \(\w*\)\>/\1-\2/g;s/ /+/g;s/.*/echo $((&))/e

実際の提出

この問題は1行目を消去し2行目をソートして順に交互に足し引きしていくと良いです。

読者の皆さんもそろそろSedに慣れてきたことでしょう。

  • &はマッチしたパターン全体を指すこと
  • gでまとめて置換するときには、一度読んだ箇所をもう一度読んで処理することはないこと

新しい事項はこの二点ですね。これらを考慮して試しにコードを読んでみませんか?どうやってSedバブルソートを実現しているのかコードとにらめっこして考えてみるのも楽しいですよね。わいわい。

2行目で各数の前に0を追加して文字数を揃えるなど前処理をし、3行目で辞書順にソートし、4行目でソートのために追加した部分を元に戻す。そして5行目で空白を交互に-+に置換して式を評価しています。

第3問:ABC081B - Shift only

1d;s/$/ 0/
:;/[13579] /s/.* //
s/\(.*\) \(.*\)$/echo \1 $((\2+1))/e
s/\w* /echo $((&\/2)) /eg;s/echo //g;t

実際の提出

これは問題文の通り、実際に2で割る操作をできなくなるまで繰り返し、その回数をカウントします。

例の通り入力の1行目は使えないので消去し、カウンターとして使う0を末尾に付け加えるのが1行目。そして2行目から4行目では以下の内容をできなくなるまで繰り返します。

  • 2行目:カウンター以外で奇数があればカウンター以外を削除
  • 3行目:カウンターのインクリメント
  • 4行目:カウンター以外の数をすべて2で割る

*はできる限り前の方からできる限り長い文字列とマッチしようとすることを利用してパターンの指定を簡潔に書いています。またeオプションとgオプションは相性が悪くばたばた足跡を残していくので、ちゃんとその処理もしないと文字数が増えすぎる、テキストの状態が把握しきれなくなるなどの不都合があります。

第10問:ABC086C - Traveling

s/.*/0 0 0/;:
$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N
$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N
$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N
$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N
$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N;$!N
/^\w* \w* \w*$/cYes
s/\<\(\w*\) \(\w*\) \(\w*\)\>/& &/2g
s/\<\(\w*\) \(\w*\) \(\w*\)\n\(\w*\) \(\w*\) \(\w*\)\>/echo $((-\1+\2+\3+\4-\5-\6))/eg
/-\|[13579]\>.\+ .* .*/{s/.*/No/;q};s/.* \(\w* \w* \w*\)/\1/;b

実際の提出

このあたりから解法やその実現、そして実行時間制限への対処を考えるのが厳しい気持ちになってきます。コードも横幅がお気持ちです。うおおおおおおおお。この問題は嘘解法で名高いですがえらいので本当で通しています、えらいので。

まず解法ですが、今の位置から次の位置へ行くのに必要な最小移動回数をm、今の時間から次の時間までの猶予をtとおくと、m\leq tかつmtの偶奇が一致していれば移動可能なので、それをすべて旅程について調べるというものです。

次に高速化の話です。2~6行目には$!Nが100個並んでいます。これはまとめて処理する旅程の個数で、解法上は1個で十分なのですが実行時間制限の都合で100個くらいないとTLEします。定数倍の高速化が有意に効いてきます。わいわい。テストケースでは1900ms以内に収まっていますが、実は最悪を考えると2200ms程になります。まあそれも$!Nをさらに増やせばちゃんと2000ms以内に収まります。わいわいわいわい。

さて具体的な実装ですが、言葉を重ねるより実際にテキストの変化の様子を見てもらった方がわかりやすいと思います。なお8行目のsコマンドについている2というオプションは、2番目にマッチしたところから置換するという意味です。

入力

3
3 1 2
6 1 1
12 3 3

$!Nゾーンを抜けた時点(開始地点0 0 0を追加した上で最大100行読み込む)

0 0 0
3 1 2
6 1 1
12 3 3

8行目まで(開始地点以外を複製)

0 0 0
3 1 2 3 1 2
6 1 1 6 1 1
12 3 3 12 3 3

9行目まで(移動可能か否かの判定)

0 echo 4 echo 2 12 3 3

10行目まで(開始地点の更新)

12 3 3

次のループにて

Yes

各旅程について情報を複製したのち、改行を挟んだお隣で実行可能か否かを評価する数を取り出します。もし負の数が出たらm>t、奇数が出たらmtの偶奇が異なるということなので、それらが出たらNoを出力してqコマンド、今持っているテキストだけ出力してしまって以降の行については触ることはおろか出力すらせずに終了するコマンド*6を実行します。Noに到達することなく最後まで調べられたらYesを出力します。

第8問:ABC085C - Otoshidama

s/^\(.*\) \(.*\)000$/echo \1 $((\2-\1))/e
s/^\(.*\) \(.*\)$/echo $((\2\/9)) \1 $(((\2-\1*4)\/5)) \1?\2/e
s/-\w* /0 /;s/^\(\w*\) \(\w*\) /echo $((\1-\2)) &/e;s/-\w* \(\w*\) \w* /\1 /;s/\w* \w* \(\w*\) /\1 /
s/^\(\w*\) \(\w*\) /echo $((\1-\2)) &/e;/-/c-1 -1 -1
s/^\w* \(\w*\) \(\w*\)/\2 \1/
h;s/ \w*?\w*//;s/.*/seq &/e;s/\n/ /g
G;s/\n.* \(.*\)/ \1/
:YKC;s/^\(\w*\) \(.*\)\<\(.*?\(.*\)\)$/echo \2 \1!$(((\4-\1*9)%4))!$(((\4-\1*9)\/4)) \3/e;tYKC
s/\<\w*![1-3]!\w* //g
s/!0!/-/g 
:NGC;s/^\(\w*-\w*\) \(.*\)\<\(\(.*\)?.*\)$/echo \2 \1-$((\4-\1)) \3/e;tNGC
s/\<\w*-\w*--\w* //g
s/ .*$//;y/-/ /;/?/c-1 -1 -1

実際の提出

s/\(.*\) \(.*\)000/echo $(((\2-\1-7*(\2-\1)%9*4)\/9)) $((7*(\2-\1)%9)) $((\1-(\2-\1-7*(\2-\1)%9*4)\/9-7*(\2-\1)%9))/e;/-/c-1 -1 -1

実際の提出

コードを二つ貼りました。前者は普通の解法、後者はO(1)解法です。後者はただの数学なので、詳細は他記事で眺めてください。ここはSedの記事なので前者の話をします。

解法ですが、10000a+5000b+1000(N-a-b)=Yより、Y'=Y/1000-Nと置くと9a+4b=Y'なるa\geq 0,b\geq 0\; such\; that\; a+b\leq Nを見つければ良いです。このためにa,bの組み合わせの候補を全列挙します。aの候補として愚直にN以下の非負整数すべてを列挙しようとすると、最大2000個の数を列挙することになり文字数も実行時間も厳しい気持ちになります。そこでa,bの条件にしたがってえいえいと計算すると、\min(N,Y'/9)\geq a\geq\min(0,(Y'-4N)/5)が得られるので、この範囲でaを列挙すれば素敵な気持ちになれます。あとは各aについて、(Y'-9a)\%4\neq 0ならば消去、対応するbを計算してa+b>Nなら消去、そして残った候補から任意に一つ取り出せば解になります。

さて実装ですが、まだ解説をしていないのは6行目のhとseq、それから7行目のGでしょうか。seqはecho同様にお外から呼び出してきたもので、seq x yでx以上y以下の整数を改行区切りで列挙します。地道なデクリメントで列挙しても間に合いますが、seqを使った方が速いしコードもわかりやすくなります。hとGはh,H,g,Gでセットです。Sedは保存領域を一つだけ持っていて、h,Hは現在のテキストの保存領域への上書きと追加、g,Gは保存領域のテキストの現在のテキストへの上書きと追加です。あとはテキストの変化の例を見て感じてください。

入力

1000 1234000

5行目まで(aの下限、上限、N、Y')

0 26 1000?234

7行目まで(aの候補の列挙)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 1000?234

10行目まで(候補となるa bの組)

2-54 6-45 10-36 14-27 18-18 22-9 26-0 1000?234

12行目まで(条件を満たすa b cの組)

2-54-944 6-45-949 10-36-954 14-27-959 18-18-964 22-9-969 26-0-974 1000?234

出力

2 54 944

第4問:ABC087B - Coins

N;N;N;s/\n/ /g;s/^\(.*\) \(\w*\)$/echo \1 $((\2\/50))/e
:500;s/^\([0-9]*\) \(.*\) \(\w*\)$/echo $((\1-1)) $((\3-\1*10)) \2 \3/e;t500;s/-[0-9]* //g
s/ \(\w*\)$/?/;:div;s/^\(\w*\) \(.*\) \(\w*\) \(\w*\)?/\2 \3 \4?\n\3 \1/;tdiv;s/^\(\w*\) \(\w*\) \(.*\)?/\2 \3\n\2 \1/
s/ /__/g
:100;s/\<\([0-9]*\)_\(\w*\)_\([0-9]*\)\>/echo $((\1-1))_$((\3-\1*2))_\2_\3/eg;s/-/a/g;t100
s/a[0-9]*_//g;s/^\w*__//;s/\n/!_/;s/__\w*\n\?/_/g
:50;s/\(.*\)\(!.*_\)\([0-9]*\)_\([0-9]*\)_/echo \1\2$((\3-\1-1))$((\4-\1-1))/e;t50;s/^\(.*\)!_\(\w*\)_/echo \1!_$((\2-\1-1))/e
s/[0-9!_]//g;s/-/+1/g;s/.*/echo $((0&))/e

実際の提出

前問と同様に10a+2b+c=X/50なる0\leq a\leq A,0\leq b\leq B,0\leq c\leq Cを全列挙し、その個数を数えます。aの候補としてA以下の非負整数を全列挙し、その各数に対しX/50-10aを調べて負の数なら消去します。するとbcX/50-10aを作る小さい問題に分割できます。さらにbについて同様のことを行えば大量のX/50-10a-2bが得られるので、これがC以下か否かを確認して数えます。abについてしか展開していないので実行時間はギリギリ間に合います。またa,b,cの組み合わせを答えるわけではないので、a,b,Xについての情報は適宜落とせます。そのため文字数の限界もなんとかなります。文章での解説ではわかりにくいと思いますので例のごとくテキストの変化の例を置いておきますが、これを見てもなかなかわからない気もします。

入力

30
40
50
2000

2行目まで(aについて展開して負の数を削除した状態)

40 30 20 10 0 40 50 40

3行目まで(部分問題に整えた状態)

40 50
40 0
40 10
40 20
40 30
40 40

5行目まで(bについて展開した状態、便宜上-をaで置換している)

a1_50_48_46_44_42_40_38_36_34_32_30_28_26_24_22_20_18_16_14_12_10_8_6_4_2_0_a2_a4_a6_a8_a10_a12_a14_a16_a18_a20_a22_a24_a26_a28_a30__50
a1_0_a2_a4_a6_a8_a10_a12_a14_a16_a18_a20_a22_a24_a26_a28_a30_a32_a34_a36_a38_a40_a42_a44_a46_a48_a50_a52_a54_a56_a58_a60_a62_a64_a66_a68_a70_a72_a74_a76_a78_a80__0
a1_10_8_6_4_2_0_a2_a4_a6_a8_a10_a12_a14_a16_a18_a20_a22_a24_a26_a28_a30_a32_a34_a36_a38_a40_a42_a44_a46_a48_a50_a52_a54_a56_a58_a60_a62_a64_a66_a68_a70__10
a1_20_18_16_14_12_10_8_6_4_2_0_a2_a4_a6_a8_a10_a12_a14_a16_a18_a20_a22_a24_a26_a28_a30_a32_a34_a36_a38_a40_a42_a44_a46_a48_a50_a52_a54_a56_a58_a60__20
a1_30_28_26_24_22_20_18_16_14_12_10_8_6_4_2_0_a2_a4_a6_a8_a10_a12_a14_a16_a18_a20_a22_a24_a26_a28_a30_a32_a34_a36_a38_a40_a42_a44_a46_a48_a50__30
a1_40_38_36_34_32_30_28_26_24_22_20_18_16_14_12_10_8_6_4_2_0_a2_a4_a6_a8_a10_a12_a14_a16_a18_a20_a22_a24_a26_a28_a30_a32_a34_a36_a38_a40__40

6行目まで(負の数を削除しあとはC以下か否かを確認するだけの状態)

50!_0_10_8_6_4_2_0_20_18_16_14_12_10_8_6_4_2_0_30_28_26_24_22_20_18_16_14_12_10_8_6_4_2_0_40_38_36_34_32_30_28_26_24_22_20_18_16_14_12_10_8_6_4_2_0_

出力

55

なお7行目、C以下か否かを確認する段で個別ではなく2個ずつ確認しています。さもなくば実行時間制限に間に合いません。わいわい。

第5問:ABC083B - Some Sums

解けませんでした......。

超えられなかった点

  • N=10000はちょっと厳しい。
    • Daydreamは相性が良かったので、TravelingはYes/Noだし調べる対象が初めから入力として与えられていたのでなんとかなりましたが、自分で調べる対象を挙げて保持しなければならない本問題は難しいです。
  • 個数ではなく総和を求めなくてはならない。
    • 最悪ケースだと1から10000まで足す羽目になるのですが、これ、一気に処理しようとするとおよそ40000文字で扱えません。
    • 少しずつ処理することで文字数を少なく済ませようとしても、今度は実行時間制限が厳しいです。

試しに総和ではなく個数を求めるコードを書いてみたものの、それでもN=2000あたりが限界でした。

例えば1000ごとに分割して数表を与えればなんとかなるかもしれませんが、それはもはやどの言語でも変わらんやんという気持ちになっちゃいますし。

結び。joinではない。

Sedはテキストファイルというカンバスの上でお絵描きして計算している気分になるので楽しいです。わいわい。

他の主流言語にとっては文字列より数字の方が扱いやすいでしょうから仕方のないことではありますが、そもそもABSにはSedの得意な文字列わいわい問題が少なく厳しいです。もっと文字列操作でわいわい解ける問題の方がSedでの語り甲斐があったのですが。かっこいいSedを見たい方はABC062-BABC064-Dの提出欄をご覧ください。

Sedには本記事で紹介できた以外にもまだまだ色んなコマンドや表現*7があり、複雑なアルゴリズムの実装には向きませんがコードゴルフや実用的なテキスト処理ではそこそこ便利なプログラムです。標準搭載されていることも多いので、今まで使ったことなかったという方もAwkPerlなどと一緒に上手に使い分けると幸せな気持ちになれるかも。

最後に宣伝ですが、私は次のAdvent Calendar企画にも参加しておりちょうど来週の20日を担当しています。Curry-Howord-Lambek対応に関連するCartesian Closed Categoryのちょっとした話を書く予定なので、興味のある方は是非合わせてよろしくお願いします。 adventar.org

*1:カレンダー7日目の記事、sh-mugさんのAtCoderでLanguage Ownerになりたい! - 取っ手が付いた円筒形の食器も合わせてどうぞ。

*2:正規表現Sedと区別せずに解説しています。

*3:正確にはc以降の行末までの全ての文字を、プログラムではなく出力対象の文字列として扱います。

*4:勿論コマンドによって重い軽いがあり、後述のsコマンドを実行できるのが3000回程度と言った方が正確です。

*5:正確にはテキストをsコマンドに従って書き換えた上でコマンドラインとして評価しています。

*6:for文からbreakで脱出するようなもの、と表現すると理解しやすいでしょうか?

*7:これはSedというより正規表現の話ですが。