Selectionの1+10問を、Sedというテキスト変換などのデータ処理に特化したプログラムで解いたり解けなかったりします。SedはAtCoderの提出可能言語に含まれてはいるものの競技プログラミング向きでなく、この記事を読む層にも文法が全くわからないという方も多くいると思いますので適宜解説もがんばって加えます*2。解説や難易度の都合でそこそこ、いやかなり問題の順番を変更しています。した難易度の逆転現象も主流でない言語で問題を解く面白さの一つだと思います。Product/[24680]\>/cEvencOdd実際の提出まずは入出力のお話ですね。Sedでは入力ファイルを1行ずつ受け取り、各行ごとにプログラムの処理を順番に行います。その処理とは基本的にテキストの置換やパターンマッチです。プログラムを通り抜けた時点で残っていたテキストが、その行での出力というわけです。計算せずとも入力に偶数が含まれていれば”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のいずれかの直後に空白あるいは行末が存在する」というパターンを探しているわけです。前問で見た正規表現によるパターンマッチはこのような問題で大活躍します。入力文字列を後ろから見ていくのが想定解法らしいですが、実はAtCoderで使えるSedは30000文字程度を超えて置換しようとすると正常動作をしなくなりますし、3000回程度のコマンド操作が実行時間制限の限界になります*4。そのため最大100000文字を扱う本問題において、後ろから処理をする想定解法はSedとしては箸にも棒にもかかりません。SedにはSedらしい解法があります。Sedでは(,),|,?,+,/,\などの文字は、入出力のための文字とコマンドのための文字を区別するために、コマンドとして扱う際は前に\をつけてエスケープします。そこで可読性のために\を外して1行目を見ると次のようになります。/^(dream(er)?|eraser?)*$/cYES?は0あるいは1回の繰り返し、*は0回以上の繰り返しを表し、^は行頭、$は行末、|は「または」を指します。よってこのコードは「(dream,dreamer,erase,eraserのいずれか)を0回以上繰り返したものが行頭と行末の間にぴったり存在する」というパターンが存在するか否かを判定しています。これならパターンを探すだけでそれをどうこうしてはいませんし、コマンドも1回しか呼び出していません。他の言語より楽に書け、むしろ複雑に書くことが困難であるような例ですね。Marbless/0//g/.../c3/../c2/./c1c0実際の提出パターンマッチとc以外のコマンド、sが出てきました。ここからがSedの本番です。s/boku/watashi/は最初に見つけたbokuというパターンをwatashiというパターンに置換するコマンドで、gは最初のものだけでなくすべてを置換するためのオプションです。パターンマッチに使っている.は任意の1文字を表します。本コードは0をすべて空文字列に置換、つまり消去してから残った文字数=元々含まれていた1の数を出力しています。\2/e実際の提出Nは現在読んでいる行の次の行も読み込むコマンドです。プログラムの1行目で入力の2行目まで読んだ後、2行目で空白及び\nつまり改行をすべて+に置換しています。プログラムの3行目で入力の3行目まで読み込んだ時点で、現在読んでいるテキストは以下のようになっています。a+b+cs最後に4行目ですが、\1,\2はそれぞれキャプチャした一つ目,二つ目の文字列を指します。「任意の文字列+改行+任意の文字列」つまり今回は「a+b+c,\n,s」を読んで、echoを呼び出して\1=a+b+cを評価し続けて空白と\2=sを出力しています。eは呼び出したechoを実行するオプションです*5。Sedは入力をテキストとして扱うことしかできないので、直接数値として計算をすることができません。巧みな文字列操作でインクリメントを行い足し算することも可能ですが、echoを呼び出してしまった方が簡単だしコマンド操作が少なくなって速いのでそのようにしました。段々とコードがわさわさしてきましたね。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を追加して式を評価してやれば答えとなります。$((&))/e実際の提出この問題は1行目を消去し2行目をソートして順に交互に足し引きしていくと良いです。読者の皆さんもそろそろSedに慣れてきたことでしょう。&はマッチしたパターン全体を指すことgでまとめて置換するときには、一度読んだ箇所をもう一度読んで処理することはないこと新しい事項はこの二点ですね。これらを考慮して試しにコードを読んでみませんか?どうやってSedでバブルソートを実現しているのかコードとにらめっこして考えてみるのも楽しいですよね。2行目で各数の前に0を追加して文字数を揃えるなど前処理をし、3行目で辞書順にソートし、4行目でソートのために追加した部分を元に戻す。5行目で空白を交互に-+に置換して式を評価しています。//g;t実際の提出これは問題文の通り、実際に2で割る操作をできなくなるまで繰り返し、その回数をカウントします。例の通り入力の1行目は使えないので消去し、カウンターとして使う0を末尾に付け加えるのが1行目。2行目から4行目では以下の内容をできなくなるまで繰り返します。2行目:カウンター以外で奇数があればカウンター以外を削除3行目:カウンターのインクリメント4行目:カウンター以外の数をすべて2で割る*はできる限り前の方からできる限り長い文字列とマッチしようとすることを利用してパターンの指定を簡潔に書いています。eオプションとgオプションは相性が悪くばたばた足跡を残していくので、ちゃんとその処理もしないと文字数が増えすぎる、テキストの状態が把握しきれなくなるなどの不都合があります。\w*\)/\1/;b実際の提出このあたりから解法やその実現、そして実行時間制限への対処を考えるのが厳しい気持ちになってきます。コードも横幅がお気持ちです。この問題は嘘解法で名高いですがえらいので本当で通しています、えらいので。奇が一致していれば移動可能なので、それをすべて旅程について調べるというものです。2~6行目には$!Nが100個並んでいます。これはまとめて処理する旅程の個数で、解法上は1個で十分なのですが実行時間制限の都合で100個くらいないとTLEします。定数倍の高速化が有意に効いてきます。テストケースでは1900ms以内に収まっていますが、実は最悪を考えると2200ms程になります。それも$!Nをさらに増やせばちゃんと2000ms以内に収まります。具体的な実装ですが、言葉を重ねるより実際にテキストの変化の様子を見てもらった方がわかりやすいと思います。8行目のsコマンドについている2というオプションは、2番目にマッチしたところから置換するという意味です。3次のループにてYes各旅程について情報を複製したのち、改行を挟んだお隣で実行可能か否かを評価する数を取り出します。奇が異なるということなので、それらが出たらNoを出力してqコマンド、今持っているテキストだけ出力してしまって以降の行については触ることはおろか出力すらせずに終了するコマンド*6を実行します。Noに到達することなく最後まで調べられたらYesを出力します。-1実際の提出コードを二つ貼りました。前者は普通の解法、後者はO(1)解法です。後者はただの数学なので、詳細は他記事で眺めてください。ここはSedの記事なので前者の話をします。組み合わせの候補を全列挙します。以下の非負整数すべてを列挙しようとすると、最大2000個の数を列挙することになり文字数も実行時間も厳しい気持ちになります。列挙すれば素敵な気持ちになれます。消去、そして残った候補から任意に一つ取り出せば解になります。実装ですが、まだ解説をしていないのは6行目のhとseq、それから7行目のGでしょうか。yでx以上y以下の整数を改行区切りで列挙します。地道なデクリメントで列挙しても間に合いますが、seqを使った方が速いしコードもわかりやすくなります。hとGはh,H,g,Gでセットです。Sedは保存領域を一つだけ持っていて、h,Hは現在のテキストの保存領域への上書きと追加、g,Gは保存領域のテキストの現在のテキストへの上書きと追加です。あとはテキストの変化の例を見て感じてください。全列挙し、その個数を数えます。調べて負の数なら消去します。作る小さい問題に分割できます。以下か否かを確認して数えます。ついてしか展開していないので実行時間はギリギリ間に合います。ついての情報は適宜落とせます。そのため文字数の限界もなんとかなります。文章での解説ではわかりにくいと思いますので例のごとくテキストの変化の例を置いておきますが、これを見てもなかなかわからない気もします。以下か否かを確認する段で個別ではなく2個ずつ確認しています。なくば実行時間制限に間に合いません。Sums解けませんでした......。超えられなかった点はちょっと厳しい。Daydreamは相性が良かったので、TravelingはYes/Noだし調べる対象が初めから入力として与えられていたのでなんとかなりましたが、自分で調べる対象を挙げて保持しなければならない本問題は難しいです。個数ではなく総和を求めなくてはならない。最悪ケースだと1から10000まで足す羽目になるのですが、これ、一気に処理しようとするとおよそ40000文字で扱えません。処理することで文字数を少なく済ませようとしても、今度は実行時間制限が厳しいです。1000ごとに分割して数表を与えればなんとかなるかもしれませんが、それはもはやどの言語でも変わらんやんという気持ちになっちゃいますし。