Qiita Engineer Festa 2024（キータ・エンジニア・フェスタ 2024） - Qiita
において、約1ヶ月で38記事という大量の記事の投稿を要求されることがわかった。
そこで、あまりコストをかけずに記事数を稼ぐ方法を考えた結果、「Welcome to AtCoder を様々な言語で解く」ことを思いついた。
単に解くだけでなく、使用する言語仕様の解説を入れれば、記事として一応成立するだろう。
Welcome to AtCoder
PracticeA - Welcome to AtCoder
Welcome to AtCoder では、以下の形式で整数 $a$, $b$, $c$ および文字列 $s$ が入力として与えられる。
a
b c
s
この入力をもとに、与えられた整数の和 $sum = a + b + c$ および文字列 $s$ を、以下の形式で出力することが求められる。
sum s
整数 $a$, $b$, $c$ は 1 以上 1,000 以下である。
今回用いる sed の機能
sedでこういう時はどう書く? #Linux - Qiita
sed(1) - Linux man page
regex - sed error: "invalid reference \1 on `s' command's RHS" - Stack Overflow
コマンド
sed では、以下のコマンドを用いることができる。
コマンドは1行に1個ずつ書く。
基本的に、入力の各行について、コマンドを上から下に順に実行していく。
| コマンド | 意味 |
|---|---|
# コメント |
コメント (何もしない) |
s/置換対象/置換先/ |
処理中のデータ中の 最初の「置換対象」1個を「置換先」に置換する |
s/置換対象/置換先/g |
処理中のデータ中の 「置換対象」すべてを「置換先」に置換する |
N |
入力の次の行を処理中のデータに加え、 コマンドを実行する対象から外す |
:ラベル |
ラベルを設定する |
tラベル |
前回の t の実行 (t を実行していない場合は、実行開始)以降に s による置換を適用できているならば、次に実行するコマンドを :ラベル の位置にする |
sed には他のコマンドもあるが、ここでは今回使ったコマンドのみを紹介した。
正規表現
sed の s による置換では正規表現を用いることができるが、Perl などで用いられる正規表現とは一部の書き方が異なる。
今回は、以下の構文を使用した。
| sed | Perl | 意味 |
|---|---|---|
\n |
\n |
改行文字 |
^ |
^ |
行頭 |
$ |
$ |
行末 |
[文字リスト] |
[文字リスト] |
リスト内の文字どれか1個 |
\+ |
+ |
直前の文字などを1回以上繰り返す |
\{数\} |
{数} |
直前の文字などをちょうど「数」回繰り返す |
\(…\)
|
(…)
|
グループを設定する |
\1, \2
|
$1, $2
|
設定したグループに相当する文字列 (置換先で用いる) |
提出コードの戦略
最後以外の数値を加算指示に変換する
まず、
a
b c
の形式になっている数値の入力について、2行目を取り込み、さらに改行を空白に置換して
a b c
の形式にする。
続いて、右側で空白に隣接している数字を1個ずつカウントダウンしながら、その桁への加算指示を表す文字を追加していく。
カウントダウンが終了 (数字が 0 になる) したら、その数字を消去し、(存在すれば) 次の桁を同様に処理する。
ここでは繰り上がり・繰り下がりを考慮しなくてよく、各桁におけるカウントダウン・加算指示追加の操作は最大でも9回しか行われない。
操作の完了後、残った空白を消去する。
加算指示に基づいて最後の数値に加算を行う
まず、加算を行いやすいよう、必要に応じて 0 を追加し、最後の数値を4桁に変換する。
次に、加算指示に従って最後の数値の各桁に加算を行っていく。
これは、「加算指示がある場合、加算指示を1個消去し、対応する桁をカウントアップする」という形で行う。
この操作は下の桁から順に行い、繰り上がりは「上の桁に対する加算指示を追加する」という形で表現する。
最初の2個の数字からの加算指示が合計で最大18個、さらに下の桁からの繰り上がりが最大2個あるので、合計で操作は各桁についてそれぞれ最大20回行われる。
十分な数の s を並べてもいいが、今回は t を用いたループにより十分な回数の操作を実現する。
最後に、上位桁に余った余計な 0 を消去し、仕上げを行う。
文字列を結合する
数値の加算が完了したら、続いて3行目に与えられる文字列を N で取り込み、改行を空白に置換して出力形式に合わせる。
提出コード
# 最初2個の数値を加算指示に変換し、数字を消去する
N
s/\n/ /
# 一の位
s/9 /8 a/g
s/8 /7 a/g
s/7 /6 a/g
s/6 /5 a/g
s/5 /4 a/g
s/4 /3 a/g
s/3 /2 a/g
s/2 /1 a/g
s/1 /0 a/g
s/0 / /g
# 十の位
s/9 /8 b/g
s/8 /7 b/g
s/7 /6 b/g
s/6 /5 b/g
s/5 /4 b/g
s/4 /3 b/g
s/3 /2 b/g
s/2 /1 b/g
s/1 /0 b/g
s/0 / /g
# 百の位
s/9 /8 c/g
s/8 /7 c/g
s/7 /6 c/g
s/6 /5 c/g
s/5 /4 c/g
s/4 /3 c/g
s/3 /2 c/g
s/2 /1 c/g
s/1 /0 c/g
s/0 / /g
# 千の位
s/9 /8 d/g
s/8 /7 d/g
s/7 /6 d/g
s/6 /5 d/g
s/5 /4 d/g
s/4 /3 d/g
s/3 /2 d/g
s/2 /1 d/g
s/1 /0 d/g
s/0 / /g
s/ //g
# 最後の数値を4桁にする
s/\([0-9]\+\)$/000\1/
s/[0-9]\+\([0-9]\{4\}\)$/\1/
# 加算指示を実行する
# 一の位
tone
:one
s/a\(.*\)0$/\11/
s/a\(.*\)1$/\12/
s/a\(.*\)2$/\13/
s/a\(.*\)3$/\14/
s/a\(.*\)4$/\15/
s/a\(.*\)5$/\16/
s/a\(.*\)6$/\17/
s/a\(.*\)7$/\18/
s/a\(.*\)8$/\19/
s/a\(.*\)9$/b\10/
tone
# 十の位
:ten
s/b\(.*\)0\(.\)$/\11\2/
s/b\(.*\)1\(.\)$/\12\2/
s/b\(.*\)2\(.\)$/\13\2/
s/b\(.*\)3\(.\)$/\14\2/
s/b\(.*\)4\(.\)$/\15\2/
s/b\(.*\)5\(.\)$/\16\2/
s/b\(.*\)6\(.\)$/\17\2/
s/b\(.*\)7\(.\)$/\18\2/
s/b\(.*\)8\(.\)$/\19\2/
s/b\(.*\)9\(.\)$/c\10\2/
tten
# 百の位
:hundred
s/c\(.*\)0\(..\)$/\11\2/
s/c\(.*\)1\(..\)$/\12\2/
s/c\(.*\)2\(..\)$/\13\2/
s/c\(.*\)3\(..\)$/\14\2/
s/c\(.*\)4\(..\)$/\15\2/
s/c\(.*\)5\(..\)$/\16\2/
s/c\(.*\)6\(..\)$/\17\2/
s/c\(.*\)7\(..\)$/\18\2/
s/c\(.*\)8\(..\)$/\19\2/
s/c\(.*\)9\(..\)$/d\10\2/
thundred
# 千の位
:thousand
s/d\(.*\)0\(...\)$/\11\2/
s/d\(.*\)1\(...\)$/\12\2/
s/d\(.*\)2\(...\)$/\13\2/
s/d\(.*\)3\(...\)$/\14\2/
s/d\(.*\)4\(...\)$/\15\2/
s/d\(.*\)5\(...\)$/\16\2/
s/d\(.*\)6\(...\)$/\17\2/
s/d\(.*\)7\(...\)$/\18\2/
s/d\(.*\)8\(...\)$/\19\2/
s/d\(.*\)9\(...\)$/\10\2/
tthousand
# リーディングゼロを消去する
s/^0\+//
# 3行目の文字列を結合する
N
s/\n/ /