3匹の猫

みみねこの競プロ精進メモ

Brainfuck縛りのバーチャルコンテストを開いた

※この記事は、「Brainf*ck Advent Calendar 2019」 2日目の記事です。
Brainf*ck Advent Calendar 2019 - Adventar

この記事は?

タイトルにもある通り、「難解プログラミング言語Brainfuckのみを使用する」という縛りでAtCoder上の問題を解くバーチャルコンテストを開きました。コンテストサイトのリンクを貼っておきます。
not-522.appspot.com

Brainfuckとは

8つの記号だけで書けるプログラミング言語です。メモリが無限に使える仮定があれば、なんでも記述できるらしい。つよい。

なぜこんなコンテストを開こうと思ったのか

僕がBrainfuckという言語を初めて知ったのは、AtCoderで開催されたいろはちゃんコンテスト Day1のA問題「一問目」です。
atcoder.jp
文字列の先頭文字を出力せよという問題です。しかしこの問題、Brainfuckを書ける方ならたった2バイトでACできるということがお判りでしょう。ACコードは以下の通りとなります。

,.

一文字受け取ってそのまま返すというシンプルなものですが、その時まだBrainfuckを知らなかった僕は衝撃を受けました。なんてすばらしい言語なんだ…!
そこから僕はBrainfuck沼にハマっていったのです。そして「Brainfuckの面白さをもっと多くの人々に伝えたい!」と思い、AtCoderで過去に出題された問題の中でも特に簡単に書ける問題を集めたバーチャルコンテストを開こうと思いました。

各問題の簡単な解説とコメント

ここからは出題した問題についてコメントを書きます。全10問で、Brainfuckで解くことを前提とした難易度順に並んでいます。コードは載せません。

一問目

先ほど紹介した問題です。一文字だけ受け取ってもいいし、そこまで効率化しなくても、メモリ上に文字列をすべて格納してから先頭文字だけ出力してもいいです。Brainfuckの基本仕様を理解していれば難なくACできると思います。問題タイトルも「一問目」で、まさに一問目にピッタリ!な問題です。

ABCxxx

ABCという文字列の後に入力される3桁の整数をそのまま返す問題です。制約より整数は必ず3桁なので、4文字目から6文字目までをオウム返しすればACできます。Ratedコンテストの中で(Brainfuck的に)最も簡単な問題だと思っています。

Diagonal String

3×3のマス目に文字が書かれています。対角線上にある3文字を抜き出して出力します。
ここで、改行文字も一つの文字であることに着目すると、1文字目、6文字目、11文字目を出力すれば良いことがわかります。

12/22

この問題から、入力をそのまま出力するだけでは解けない問題になります。4桁の整数のうち、「2」という数字は何回出てくるかカウントする問題です。ある桁を見たとき、その桁の数字が「2」であるかどうか判定するif文を書く必要があります。「2」の個数をカウントしたら、その数字にASCIIコードで'0'の値を足して出力すればよいです。

お茶

ここからの3問はYes/No判定問題です。文字列の最後の文字が「T」かどうか判定します。文字列の長さがわからないので、どの文字を判定すればいいかわかりません。…と言いたいところですが、最後の文字の後ろには必ず改行文字が入力されるはずなので、入力された文字が改行文字ならば一つ前に入力された文字が「T」かどうか判定する、というようなif文を書けばよいです。
また、この問題では「YES」「NO」という文字列を自ら生成しなければいけません。「Y」という文字のASCIIコードの値は10進数で89で、「E」という文字のASCIIコードの値は69で…と地道にやっていくとできます。

abc of ABC

3文字の文字列を並び替えて「abc」とすることが出来るか判定します。効率よく解くためには少し考察がいる問題で、Brainfuckでの色々な解法が見られました。
str[i]で文字列のi番目の文字を指すとします。各文字は「a」「b」「c」のいずれかであるという制約をうまく使うと、if(str[0] != str[1] && str[1] != str[2] && str[2] != str[0])という条件分岐を書けば解けることがわかります。また、str[i] -= 'a' としたうえで、if(str[0] + str[1] + str[2] == 3)をしても解けます。さらに一般化して、if(2^str[0] + 2^str[1] + 2^str[2] == 7)としても解けます!
ちなみに、こちらの問題でも「Yes」「No」を生成する必要がありますが、ASCIIコード上では大文字と小文字は区別されるので前問で書いたコードは使えないということになります…。

September 9

2桁の数字に「9」という数字が一つ以上含まれるか判定します。この問題もif文を書くだけではありますが、実装の仕方に個性が出る問題だと思います。前の桁から見ていって、条件を満たすことが確定したら次の桁は見ないように実装するとシンプルに書けるかもしれません。

Restricted

ラスト3問はさらに難易度が上がります。一桁の正整数の和を出力しますが、和が10以上なら「error」と出力しなければいけません。10をあらかじめ用意しておき、計算結果と大小比較します。brainfuckでは「今見ている値が0が0で無いか」しか判定できないので、大小比較するためには少し凝ったコードを書く必要があります。出力については、もし計算結果の方が小さいなら出力は必ず1桁の整数となり、出力時の繰り上がりを考慮しなくても解けるのでBrainfuck的には楽です。

Ringo's Favorite Numbers

このコンテスト中で唯一の200点問題です。100でちょうどD回割り切れる整数のうち、N番目に小さいものを出力します。たとえばD=1なら、条件を満たす数は小さい順に100、200、300、…と続いていきます。ただ、100番目の数は10000ではなく10100であることに注意してください。一般化すると、N<100のとき答えは N * 100^D なので、BrainfuckではNをそのまま出力した後「0」を2*D回出力すれば良いです。N=100なら、Nに1を足してから出力し、「0」を2*D回出力します。
僕が知る限りでは、この問題が200点の中でいちばんやさしいかなと思っています(多分もっと簡単なものもあります)。

Welcome to AtCoder

最後の問題は超難しいです。3つの整数の和と入力された文字列を出力するだけですが、Brainfuckで整数の和を計算するのはとても複雑で大変です。正直なところ僕も理解していません。コンテスト時間の90分間で2人も通しているのはなぜでしょうか…震えます…
余談ですが、この問題はAtCoderチュートリアルで出てくる問題です。ある作品のチュートリアルとして出てきたモンスターが、別の作品のラスボスとして登場したら興奮しませんか?みんなこういうの好きでしょ!僕は好きです。

締め

というわけで、バーチャルコンテストを開いたよというお話でした。難易度調整が上手くいったと思っていて、たくさんの人が参加してくれたおかげもあってか順位表の傾きがキレイな三角形になったので載せておきます。
f:id:mmnkblog:20191130212036p:plain

また機会があったらやりたいです!終わり!