JOI2020 1次予選(1回目) A - 3つの整数(Three Integers) Brainfuck解答

はじめに

この記事では、JOI2020 1次予選(1回目)A問題のBrainfuck解答の解説をします。普通の解説が必要な方は他の記事を見たほうが有益かと思います。

問題概要

整数 A, B, Cが与えられる。この3つの整数はいずれも1か2である。1と2のうち多い方の数を求めよ。

解説

解答コードはページの一番下に載せてあります。

配列

解答において、brainfuckの配列には以下のように変数を当てています。

index	0	1	2	3	4	5	6	7	8	9	10	11	12
	A	(空白)	B	(空白)	C	A2	A3	B2	B3	C2	C3	F1	F2

• A2, A3: Aのコピー(B, Cについても同様)
• F1, F2: 分岐処理に使うフラグ(後述)

Brainfuckの基本テクニック

本コードの解説の前に、解答で使うテクニックをいくつか紹介します。以下、brainfuckの配列のn番目の値をv[n]と表します。

値のコピー

brainfuckでは値を破壊することが多くあるため、値のコピーが必要になります。
下記のコードはv[0]の値をv[1]とv[2]にコピーするコードです。

[>+>+<<-]

値の比較

下記のコードはv[0]とv[1]を比較します。v[0]=v[1]のとき、v[1]=0、そうでない時v[1]≠0となります。(v[0]の値はいかなる場合も0です。)

[->-<]

条件分岐

[]を使用することで、ポインタの指す場所の値が0でないかどうかで条件分岐ができます。他言語でいうelse句は、else句を実行するかを記録するフラグを用意し、then句の中でelse句を実行しないようにします。
下記のコードは、v[0]≠0のとき処理1を、そうでない時処理2を実行するコードです。else句実行フラグはv[1]とします。

[[-]>[-]<(処理1)]>[[-](処理2)]

以上のテクニック()を使うことで、この問題は比較的簡単に解くことができます。

解答コード(Brainfuck)

わかりやすさのためにコメントやインデントを入れています。

,>,>,>,>,<<<<[>>>>>+>+<<<<<<-]>>[>>>>>+>+<<<<<<-]>>[>>>>>+>+<<<<<<-]>>>>>>>+>+<<<<<<< 変数の初期化(詳細は解説の配列の項を参照のこと)
[->>-<<]>> もしA2≠B2ならば
    [<[->>>-<<<]>>> もしA3≠C2ならば
        [<.>>>[-]>[-]<<<[-]] B3を表示し、以下のコードを実行しないようにする(C2, F1, F2を0にする)
    >>>[<<.>[-]>[-]]<<<<<[-]] A3=C2ならば、C3を表示し、以下のコードを実行しないようにする(B2, F1, F2を0にする)
>>>>[<<<<<.[-]] A2=B2ならばA3を表示する