Sed で Welcome to AtCoder を解いてみた

[Qiita Engineer Festa 2024（キータ・エンジニア・フェスタ 2024） - Qiita](https://qiita.com/official-campaigns/engineer-festa/2024)
において、約1ヶ月で38記事という大量の記事の投稿を要求されることがわかった。
そこで、あまりコストをかけずに記事数を稼ぐ方法を考えた結果、「Welcome to AtCoder を様々な言語で解く」ことを思いついた。
単に解くだけでなく、使用する言語仕様の解説を入れれば、記事として一応成立するだろう。

# Welcome to AtCoder

[PracticeA - Welcome to AtCoder](https://atcoder.jp/contests/abs/tasks/practice_1)

Welcome to AtCoder では、以下の形式で整数 $a$, $b$, $c$ および文字列 $s$ が入力として与えられる。

```text
a
b c
s
```

この入力をもとに、与えられた整数の和 $sum = a + b + c$ および文字列 $s$ を、以下の形式で出力することが求められる。

```text
sum s
```

整数 $a$, $b$, $c$ は 1 以上 1,000 以下である。

# 今回用いる sed の機能

[sedでこういう時はどう書く? #Linux - Qiita](https://qiita.com/hirohiro77/items/7fe2f68781c41777e507)
[sed(1) - Linux man page](https://linux.die.net/man/1/sed)
[regex - sed error: "invalid reference \1 on `s' command's RHS" - Stack Overflow](https://stackoverflow.com/questions/16637799/sed-error-invalid-reference-1-on-s-commands-rhs)

## コマンド

sed では、以下のコマンドを用いることができる。
コマンドは1行に1個ずつ書く。
基本的に、入力の各行について、コマンドを上から下に順に実行していく。

|コマンド|意味|
|---|---|
|`# コメント`|コメント (何もしない)|
|`s/置換対象/置換先/`|処理中のデータ中の<br>**最初の「置換対象」1個**を「置換先」に置換する|
|`s/置換対象/置換先/g`|処理中のデータ中の<br>**「置換対象」すべて**を「置換先」に置換する|
|`N`|入力の次の行を処理中のデータに加え、<br>コマンドを実行する対象から外す|
|`:ラベル`|ラベルを設定する|
|`tラベル`|前回の `t` の実行 (`t` を実行していない場合は、実行開始)<br>以降に `s` による置換を適用できているならば、<br>次に実行するコマンドを `:ラベル` の位置にする|

:::note info
sed には他のコマンドもあるが、ここでは今回使ったコマンドのみを紹介した。
:::

## 正規表現

sed の `s` による置換では正規表現を用いることができるが、Perl などで用いられる正規表現とは一部の書き方が異なる。
今回は、以下の構文を使用した。

|sed|Perl|意味|
|---|---|---|
|`\n`|`\n`|改行文字|
|`^`|`^`|行頭|
|`$`|`$`|行末|
|`[文字リスト]`|`[文字リスト]`|リスト内の文字どれか1個|
|`\+`|`+`|直前の文字などを1回以上繰り返す|
|`\{数\}`|`{数}`|直前の文字などをちょうど「数」回繰り返す|
|`\(`…`\)`|`(`…`)`|グループを設定する|
|`\1`, `\2`|`$1`, `$2`|設定したグループに相当する文字列 (置換先で用いる)|

# 提出コードの戦略

## 最後以外の数値を加算指示に変換する

まず、

```text
a
b c
```

の形式になっている数値の入力について、2行目を取り込み、さらに改行を空白に置換して

```text
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/ /
```

[提出 #54720914 - AtCoder Beginners Selection](https://atcoder.jp/contests/abs/submissions/54720914)