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 以下である。
Brainfuck
Brainfuck の処理系は、整数を要素とする配列と、その配列の要素どれか1個を指すポインタを管理する。
実行開始時、配列の要素はすべてゼロに、ポインタは配列の左端の要素を指すように初期化される。
Brainfuck では、以下の8種類の文字で表される8種類の命令を使用できる。
これら以外の文字は無視される。
| 文字 | 意味 |
|---|---|
+ |
ポインタが指す要素に1を足す (インクリメント) |
- |
ポインタが指す要素から1を引く (デクリメント) |
> |
ポインタが指す要素を1個右の要素に変更する |
< |
ポインタが指す要素を1個左の要素に変更する |
[ |
ポインタが指す要素の値がゼロならば、対応する ] に実行を移す |
] |
ポインタが指す要素の値がゼロでなければ、対応する [ に実行を移す |
, |
入力を1バイト読み込み、ポインタが指す要素に格納する |
. |
ポインタが指す要素を値とする1バイトを出力する |
提出コード
改行に当たるまで、桁数を数えながら最大4桁読み込む
>+++++
>,----------[
<->>,----------[
<<->>>,----------[
<<<->>>>,----------[
<<<<->>>>>,[-]
]
]
]
]
余った桁の分右にシフトし、左端に0に相当するデータを入れる
<[<]
>-[
>>>[>+<-]
<[>+<-]
<[>+<-]
++++++++++++++++++++++++++++++++++++++
<-
]
移動しながら数字を数値に変換する
>--------------------------------------
>--------------------------------------
>--------------------------------------
>--------------------------------------
>
空白に当たるまで、桁数を数えながら最大4桁読み込む
>+++++
>,--------------------------------[
<->>,--------------------------------[
<<->>>,--------------------------------[
<<<->>>>,--------------------------------[
<<<<->>>>>,[-]
]
]
]
]
余った桁の分右にシフトし、左端に0に相当するデータを入れる
<[<]
>-[
>>>[>+<-]
<[>+<-]
<[>+<-]
++++++++++++++++
<-
]
移動しながら数字を数値に変換する
>----------------
>----------------
>----------------
>----------------
>
改行に当たるまで、桁数を数えながら最大4桁読み込む
>+++++
>,----------[
<->>,----------[
<<->>>,----------[
<<<->>>>,----------[
<<<<->>>>>,[-]
]
]
]
]
余った桁の分右にシフトし、左端に0に相当するデータを入れる
<[<]
>-[
>>>[>+<-]
<[>+<-]
<[>+<-]
++++++++++++++++++++++++++++++++++++++
<-
]
移動しながら数字を数値に変換する
>--------------------------------------
>--------------------------------------
>--------------------------------------
>--------------------------------------
3番目の値を2番目の値に加算する
[-<<<<<<+>>>>>>]
<[-<<<<<<+>>>>>>]
<[-<<<<<<+>>>>>>]
<[-<<<<<<+>>>>>>]
3番目の値と2番目の値の和を1番目の値に加算する
<<<
[-<<<<<<+>>>>>>]
<[-<<<<<<+>>>>>>]
<[-<<<<<<+>>>>>>]
<[-<<<<<<+>>>>>>]
一の位から十の位の繰り上がり処理を行う
<<+<[
>>>>+++++++++[
<<<<[->+>]
>[>]<[>]
>>-
]
<<<<[<+>->--------->]
>[>]<[>]<<
]
>[-<+>]
十の位から百の位の繰り上がり処理を行う
+<<[
>>>>>+++++++++[
<<<<<[->>+>]
>[>]<[>]
>>-
]
<<<<<[<+>->>--------->]
>[>]<[>]<<<
]
>>[-<<+>>]
百の位から千の位の繰り上がり処理を行う
+<<<[
>>>>>>+++++++++[
<<<<<<[->>>+>]
>[>]<[>]
>>-
]
<<<<<<[<+>->>>--------->]
>[>]<[>]<<<<
]
>>>[-<<<+>>>]
出力する範囲を決定する
ついでに、百の位、十の位、一の位に1が足されているのを打ち消す
>+>+>+>+>>>>>+<<<<<<<<<<<<<
[>>>>>>>>>>+>+>+<<<<<<<<]>>>>[<]
<<<-[>>>>>>>>>>+>+<<<<<<<<]>>>[<]
<<-[>>>>>>>>>>+<<<<<<<<]>>[<]
<-
決定した範囲に従って出力する
>>>>>>>>>>[<]>
[<<<<<<<<<<++++++++++++++++++++++++++++++++++++++++++++++++.>>>>>>>>>>>]
=====足し算パート終了！あとは文字列パート=====
空白を出力する
++++++++++++++++++++++++++++++++.
読み込んだ文字を出力する
改行を読み込んだら終了する
[,.----------]
提出 #54465309 - AtCoder Beginners Selection
提出コードの解説
数値の読み込み
改行に当たるまで、桁数を数えながら最大4桁読み込む
( 1) >+++++
( 2) >,----------[
( 3) <->>,----------[
( 4) <<->>>,----------[
( 5) <<<->>>>,----------[
( 6) <<<<->>>>>,[-]
( 7) ]
( 8) ]
( 9) ]
(10) ]
(1) を実行すると、配列は以下の状態になる。
配列の最初の要素は、後でポインタの位置合わせに用いるためゼロのまま残しておく。
配列の次の要素に、読み込む最大の桁数に1を加えた5を格納する。
ここがゼロになってしまうとポインタの位置合わせに支障が出るため、最大の桁数を読み込んでもゼロにならないよう、最大の桁数に1を加えた数で初期化する。
(2) で、1桁目を読み込み、10を引いてゼロになるかどうかで読み込んだのが10 (LF) かを判定する。
読み込んだのが LF である場合、この数値の読み込みを終了して次の処理に移る。
そうでない場合、桁数情報をデクリメントし、配列の次の要素に次の桁を読み込む。
(3)～(5) で、これを最大で4桁分繰り返す。
LF 以外を4桁読み込んだ場合は、(6) で次の文字 (LF) を読み込んで捨てる。
処理が完了すると、ポインタは最後の有効な桁の情報が格納された要素の1個右の要素を指した状態になる。
このとき、ポインタが指している要素にはゼロが格納されている。
これは、読み込んだのがLFかを判定する処理で要素の値がゼロになったか、4桁読み込んだ次に読み込んだ値を捨てる処理でゼロにしているからである。
たとえば、72 を読み込んだ場合は以下の状態になる。
余った桁の分右にシフトし、左端に0に相当するデータを入れる
(1) <[<]
(2) >-[
(3) >>>[>+<-]
(4) <[>+<-]
(5) <[>+<-]
(6) ++++++++++++++++++++++++++++++++++++++
(7) <-
(8) ]
まず、(1) でポインタを1個左の要素 (処理内容より、ゼロではなく有効な桁のデータが格納されているはず) に異動し、さらに値がゼロの要素を指すまでポインタを左に動かす。
これにより、読み込んだ桁数にかかわらずポインタが位置合わせ用の一番左の要素を指している状態になる。
続いて、ポインタを桁数情報に移動し、「位置合わせ」は完了したので位置合わせ用に足していた1を引いて相殺する。
すると、桁数情報は4桁になるまであと何桁かを表す値になるので、この回数だけ (3)～(6) のシフト処理を行う。
(4桁読み込んだ場合は、これは0回になる。すなわちシフト処理は行わない)
読み込んだ数値が4桁に満たない場合、左詰めで格納される。
シフト処理は、これを右詰めに変換し、足し算をしやすくする処理である。
1回のシフト処理は、配列の4番目から2番目の要素の値を、それぞれ1個右の要素に移動することで行う。
移動元の要素がゼロになるまで移動元の要素をデクリメントし、デクリメントとしたのと同じ回数だけ移動先の要素をインクリメントする。
この操作は移動先の要素の初期値がゼロであることを前提としている。
移動先の要素の状態は以下のいずれかであり、これらのどの状態でも値はゼロなので、この条件を満たす。
- 値の入力や加減算が行われておらず、初期値のままである
- 入力を読み込む処理において、10を引いてゼロになった (LF を読み込んだ)
- シフト処理における移動処理が完了した
(3)～(5)でこの移動処理をそれぞれ行う。
その後、(6) でシフトにより空いた配列の2番目の要素に、0 を読み込んだときに相当する値を書き込む。
最後に、(7) で残りのシフト回数をデクリメントし、(8) でシフト処理を続けるかの判定を行う。
たとえば、72 を読み込んだあと (8) までの処理を1回行うと、以下の状態になる。
残りのシフト回数は、前の部分の処理が完了した状態での3から (2) で1回、(7) で1回デクリメントされるので、1となる。
移動しながら数字を数値に変換する
>--------------------------------------
>--------------------------------------
>--------------------------------------
>--------------------------------------
>
シフト処理の完了時、ポインタは残りのシフト回数 (ゼロ) を指している。
この部分では、このポインタを数値を読み込んだ部分の右まで移動しつつ、数値を読み込んだ部分から差に相当する値を引くことで、数字 (文字コード) から対応する数値に変換する。
たとえば、72 を読み込んだあと、この処理までを終えると、以下の状態になる。
空白に当たるまで、桁数を数えながら最大4桁読み込む
>+++++
(中略)
移動しながら数字を数値に変換する
>--------------------------------------
>--------------------------------------
>--------------------------------------
>--------------------------------------
ここまでの処理と同様に、2個目および3個目の数値を読み込む。
2個目の数値を読み込む際は、LF (10) ではなく空白 (32) と一致するかの判定により読み込みを続けるかの判断を行う。
3個目の数値を読み込んだ後は、次の処理の関係で、ポインタが「1の位が格納された要素の1個次」ではなく「1の位が格納された要素」を指すようにする。
たとえば、入出力例2の
72
128 256
を読み込むと、以下の状態になる。
各桁の加算
3番目の値を2番目の値に加算する
[-<<<<<<+>>>>>>]
<[-<<<<<<+>>>>>>]
<[-<<<<<<+>>>>>>]
<[-<<<<<<+>>>>>>]
3番目に読み込んだ値4桁それぞれについて、2番目に読み込んだ値の対応する桁に加算する。
加算は、加算元の値をゼロになるまでデクリメントし、同じ回数加算先の値をインクリメントすることで行う。
繰り上がりは後でまとめて補正するので、ここでは考慮しない。
この部分の実行を完了すると、以下の状態になる。
3番目の値と2番目の値の和を1番目の値に加算する
<<<
[-<<<<<<+>>>>>>]
<[-<<<<<<+>>>>>>]
<[-<<<<<<+>>>>>>]
<[-<<<<<<+>>>>>>]
同様に加算を行う。
この部分の実行を完了すると、以下の状態になる。
繰り上がり処理
一の位から十の位の繰り上がり処理を行う
( 1) <<+<[
( 2) >>>>+++++++++[
( 3) <<<<[->+>]
( 4) >[>]<[>]
( 5) >>-
( 6) ]
( 7) <<<<[<+>->--------->]
( 8) >[>]<[>]<<
( 9) ]
(10) >[-<+>]
(1) を実行すると、以下の状態になる。
ゼロだと位置合わせに支障が出るため、「繰り上がり元の値退避用」の値は 1 にしておく。
「繰り上がり元」の値がゼロでない間、以下の (2)～(8) の処理を繰り返す。
これは、「繰り上がり元」の値が9を超えているかを判定し、超えている場合は「繰り上がり元」から10を引いて「繰り上がり先」に1を加える (すなわち、繰り上がりを行う) 処理である。
まず、(2) でポインタが「残り減算回数」を指すようにし、「残り減算回数」を9にする。
この「残り減算回数」を用いて、以下の (3)～(5) の処理を9回繰り返す。
(3) でポインタが「繰り上がり元」を指すようにし、「繰り上がり元」がゼロかを判定する。
「繰り上がり元」がゼロである場合は、何もせず、ポインタは配列の5番目の要素を指した状態である。
「繰り上がり元」がゼロでない場合は、「繰り上がり元」をデクリメントし、「繰り上がり元の値退避用」をインクリメントする。
その後、ポインタは配列の7番目の要素を指した状態になる。ここの値はゼロなので、この処理は必ず1回だけ行う。
(4) でポインタの位置合わせを行う。
配列の6番目の要素は必ずゼロ以外、7番目および8番目の要素は必ずゼロなので、ポインタは以下のように動く。
| 処理 | ポインタの位置 A | ポインタの位置 B |
|---|---|---|
| (4) の直前 | 5 | 7 |
> |
6 | 8 |
[>] |
7 | 8 |
< |
6 | 7 |
[>] |
7 | 7 |
よって、(3) でデクリメント・インクリメントの処理が行われたかどうかにかかわらず、(4) を実行するとポインタは配列の7番目の要素を指した状態になる。
(5) でポインタが「残り減算回数」を指すようにし、「残り減算回数」をデクリメントする。
ここまでの (2)～(6) の処理により、「繰り上がり元」がゼロでない間、最大9回「繰り上がり元」から「繰り上がり元の値退避用」に数を移す。
この処理によって「繰り上がり元」がゼロになった場合はもとの「繰り上がり元」は9以下だった、ゼロにならなかった場合はもとの「繰り上がり元」は9超だった、ということがわかる。
(7) でポインタが「繰り上がり元」を指すようにし、「繰り上がり元」がゼロでない場合 (すなわち、もとの「繰り上がり元」が9超だった場合) は繰り上がり処理を行う。
繰り上がり処理は、以下の処理である。
- 「繰り上がり先」に1を足す
- 「繰り上がり元」から1を引く
- 「繰り上がり元の値退避用」から9を引く
「繰り上がり元」はゼロではないので、1を引いた結果はゼロ以上である。
「繰り上がり元の値退避用」から10を引いてしまうと、ゼロになって位置合わせに失敗してしまう可能性があるので、9だけを引いて残りの1は「繰り上がり元」から引く。
繰り上がり処理を行わなかった場合、ポインタは配列の5番目の要素を指した状態になる。
繰り上がり処理を行った場合、ポインタは配列の7番目の要素を指した状態になる。
そこで、(8) で (4) と同様の位置合わせを行い、さらにポインタを2回左に動かすことでポインタを「繰り上がり元」に合わせる。
「繰り上がり元」がゼロになり、(1)～(9) のループから抜けたら、(10) を実行する。
ここでは、「繰り上がり元退避用」の値を「繰り上がり元」に加算する。
「繰り上がり元の値退避用」には最初に1を入れているので、この加算の結果「繰り上がり元」の値はもとの「繰り上がり元」の値を10で割った余りに1を足した値になる。
ここで1を足した値になるため、処理後の「繰り上がり元」はゼロにはならず、この後の繰り上がり処理における位置合わせに支障が出ないようになる。
ここまでの処理を行うと、以下の状態になる。
十の位から百の位の繰り上がり処理を行う
+<<[
>>>>>+++++++++[
<<<<<[->>+>]
>[>]<[>]
>>-
]
<<<<<[<+>->>--------->]
>[>]<[>]<<<
]
>>[-<<+>>]
百の位から千の位の繰り上がり処理を行う
+<<<[
>>>>>>+++++++++[
<<<<<<[->>>+>]
>[>]<[>]
>>-
]
<<<<<<[<+>->>>--------->]
>[>]<[>]<<<<
]
>>>[-<<<+>>>]
同様に、残りの繰り上がり処理を行う。
「繰り上がり元の値退避用」およびそれより右の要素の位置は変わらず、「繰り上がり先」と「繰り上がり元」の位置が変わるので、それに合わせてポインタを動かす回数 (動かす距離) が変わっている。
また、繰り上がり処理が終わった際ポインタは「繰り上がり元の値退避用」を指しているので、次の繰り上がり処理は「繰り上がり元の値退避用」の値を1にするための加算から始まる。
今回入力される整数は 1 以上 1,000 以下なので、3個足したときの和の最大は 3,000 である。
よって、千の位から一万の位への繰り上がり処理は不要である。
ここまでの処理を行うと、以下の状態になる。
数値の出力
出力する範囲を決定する
ついでに、百の位、十の位、一の位に1が足されているのを打ち消す
(1) >+>+>+>+>>>>>+<<<<<<<<<<<<<
(2) [>>>>>>>>>>+>+>+<<<<<<<<]>>>>[<]
(3) <<<-[>>>>>>>>>>+>+<<<<<<<<]>>>[<]
(4) <<-[>>>>>>>>>>+<<<<<<<<]>>[<]
(5) <-
先頭に余計なゼロを出力せず、必要十分な桁数の出力を行うため、出力を行う範囲を決定し、それに応じて出力フラグを立てる。
(1) を実行すると、以下の状態になる。
1の位は必ず出力するので、あらかじめ出力フラグを立てておく。
(2) により、出力する整数の千の位がゼロでない場合は、千の位・百の位・十の位に対応する出力フラグを立てる。
前半部分で出力フラグを立てた場合はポインタが配列の6番目の要素を指す状態になり、立てなかった場合はポインタが配列の2番目の要素を指す状態になるので、後半の処理によりどちらの場合でもポインタが配列の6番目の要素を指す状態にする。
(3)(4) では、同様に以下の処理を行う。
- (3)：出力する整数の百の位がゼロでない場合は、百の位・十の位に対応する出力フラグを立てる
- (4)：出力する整数の十の位がゼロでない場合は、十の位に対応する出力フラグを立てる
さらにこのとき、それぞれの位がゼロかの判定を行う前にそれぞれの位の値から1を引き、繰り上がり処理の際に1を足したのを相殺する。
なお、出力フラグを立てる処理は重複しても「非ゼロ」になることは変わらず、また非ゼロの位があった際にその位だけでなくその位より下の位に対応する出力フラグも立てるので、最上位以外にゼロがあってもなくても正しい結果が得られる。
(5) では、繰り上がり処理の際に一の位に1を足したのを打ち消す。
一の位は必ず出力するので、出力フラグの判定は行わない。
ここまでの処理を行うと、以下の状態になる。
決定した範囲に従って出力する
(1) >>>>>>>>>>[<]>
(2) [<<<<<<<<<<++++++++++++++++++++++++++++++++++++++++++++++++.>>>>>>>>>>>]
まず、(1) の前半でポインタが出力フラグの一の位に対応する位置を指すようにする。
そして、(1) の後半でポインタが出力フラグが非ゼロになっている最上位を指すようにする。
次に、(2) で数値の出力を行う。
ポインタが指す位置の要素がゼロでない間、以下を繰り返す。
- ポインタを、今指している出力フラグに対応する整数の桁を表す要素を指すように移動する
- ポインタが指している要素に
'0'(文字0の文字コード) を加算し、数値を数字に変換する - 変換結果の数字を出力する
- ポインタを今指している整数の桁に対応する出力フラグを表す要素を指すように戻し、さらに1個右の要素を指すように移動する
この操作により、出力フラグが立っている桁を数字に変換して出力する。
文字列の読み込みと出力
空白を出力する
++++++++++++++++++++++++++++++++.
これまでの処理で、ポインタは値がゼロである要素を指した状態になっている。
そこで、ポインタが指している要素に 32 を加算して出力することで、出力で数値と文字列を区切る空白を出力する。
読み込んだ文字を出力する
改行を読み込んだら終了する
[,.----------]
「空白を出力する」処理により、ポインタが指している要素の値は 32 になり、ゼロではない。
したがって、このループに入る。
このループでは、以下を行う。
- 文字を読み込む
- 読み込んだ文字をそのまま出力する
- 読み込んだ文字(コード)から 10 を引き、読み込んだのが改行 (LF) だったかを判定する。改行の場合はループを終了し、そうでない場合はループを継続する
この処理により、改行を含む3行目の文字列を読み込んで出力する。