Zenn
🧠

Brainf**k講座(応用編) atcoderでの頻出処理

2024/12/06に公開
AtCoder
esolang
Brainfuck
tech

はじめに

背景

本記事は、Qiitaの競技プログラミングなんでも Advent Calendar 2024の、シリーズ2 6日目の記事です。
今回は、Brainf**k講座の応用編ということで、競技プログラミングサイトとして有名な、atcoder で問題を解く際によく使う処理を紹介したいと思います。

処理系の特徴

atcoder では、bf というインタプリタ ( Ubuntuに同名のパッケージがあります ) が採用されており、以下の特徴があります。

  • セルが8bitサイズ
    0～255の範囲の数値しか扱えません。そのため大きな数値を扱う場合は、複数桁の制御が必然となり処理が複雑になります。
    逆にwrap-aroundを利用して、例えば 0 から - 一回で 255 を作る等、セルが32bitの処理系と比較してコードの短縮が図れる場面も多いです。
  • 移動できるセルの範囲
    atcoderでは、bf のデフォルトのセル数 9999 を実行時のオプションで拡張しています。そのため、セル数が不足することは心配しなくても大丈夫です。
    ただ、bf の仕様として、開始セルの左 ( < の方向 ) に進むとエラー終了 ( RE ) となるため、ある程度右に進んでから処理を開始する必要が出てきます。
  • 処理量の上限
    atcoder で Brainf**k を使って挑む場合、大抵は問題の処理時間上限が 2sec になっています。記事執筆時点での atcoder の環境だと、これはざっくり 10億ステップオーダーくらいと見ておくと、見積もりに役立つのではないかと思います。
    なお、bf では同一種の +-<> が連続する場合はまとめて1ステップで処理されます。そのため、例えば +[->+] でのマーカージャンプ ( -1のセルへの移動 ) を +[->>>>>>>>+] のように8セルずつの移動にする等の工夫で、定数倍ながらステップ数を減らすことができます。どうしても特定の処理がボトルネックになって TLE する場合は考えてみても良いでしょう。

実行環境の詳細

今回、処理全体というよりパーツでの紹介となるため、コード中に # を埋め込むことでセル状態がダンプできるAzicore氏のインタープリタを使用し、実行中の状況を見ていきたいと思います。
atcoderの仕様に合わせるには、以下を設定します。

  • バッファの型 … 1バイト
  • 標準入力の終端 … 255

なお、開始セルから左に行っても特に咎められることはないので、それは適宜セルの状況を見て負のアドレスのセルがダンプに含まれてないかで判断してください。また、デフォルトではダンプサイズが限られるので、今回はバッファ要素数1000を上限にしています。

頻出処理

ちょっとした処理

ではまずは肩慣らしにちょっとした処理から

  • 先頭1行のスキップ
    問題のパラメータは標準入力経由で与えられるわけですが、最初の1行 ( N なんかがよく該当します ) は、実は使わなくても良いことが多いです。そんなときの1行スキップのコードです。
    1行スキップ
    +[,----------]
    次の例のように、スキップ後単に入力を出力するコードでも確かめられますが、先頭の1行を読み飛ばせていることが分かります。
  • 長距離右移動
    atcoder の bf では開始セルの左にアクセスできません。となると、左右両方に多くの空きセルが欲しい問題では、まず右に一杯動くという処理が要求されます。そこで分かり易く255移動するのが次のコードです。
    255セル移動
    -[-[->+<]>]
    このコードはBrainf**k講座(3)の実例2にある指定移動距離と同類のものです。ただ、距離255を単発の-で作れるのは1バイトセル環境ならではとなります。
    なお、移動後の状況をダンプしたのが次図です。アドレス255のところに***が付いている ( そのセルにいる ) という状況が分かります。

Yes/Noの出力

続いては、atcoderでありがちな「何かを判定してTruthyなら"Yes"を、Falsyなら"No"を出力する」という処理です。
ごくごく単純な例として、「入力1文字が 0 なら Yes、それ以外なら No を出力する」という問題に対する実装を取り上げてみます。

コード全体
dump付コード
>>>>>>
** YNeos生成 **
+++++<+<++<+<+<
+++++++++++[->[++++++++>]<++<++<+<-<<]
#(dump)
** 判定 **
<,+++>-[-----<->]<[>]
#(dump)
** 出力 **
>>[.>>]

次の図は0入力時(Yes出力)の実行例です。

さて、基本的な方針は、出力文字を作る→Truthy/Falsyを判定する(問題により変化)→出力するという段階を踏むもので、出力文字をパックして YNeos とまとめることで両対応にするのがミソです。

  • 文字列の整備(YNeos)
    Yes, No を1文字ずらしでまとめて YNeos として作ります。
    文字コード 89, 78, 101, 111, 115 を 11×(8+0)+1, 11×(8-1)+1, 11×(8+1)+2, 11×(8+2)+1, 11×(8+2)+5 とみて、+8 部分を共通化した周期11のループで生成します。
    YNeos生成
    +++++<+<++<+<+<
+++++++++++[->[++++++++>]<++<++<+<-<<]
    (負のアドレスを避けるために) 最初に6右移動してから生成した直後のセルのダンプ状況は次のようになります。
  • 文字の出力
    そして文字出力です。が、その前段のTruthy/Falsyの判定で、TruthyならYの文字の2つ左、Falsyなら1つ左に出るようにします。その上で1文字おきに出力していきます。
    出力
    >>[.>>]
    Yes出力の場合の判定直後のdump状況は次の通りです。
    No出力の場合は次の通りです。
    このようにしてYes/Noの出力に両対応できる組み方ということで、ここで紹介しました。

複数の数値の入力

atcoderでは、1行あるいは複数行を問わず、複数の数値が空白区切りで入力される問題がよくあります。パターンとしては N 等で個数指定されるもの、個数が固定されているもの、EOFまで可変個読むもの、色々ありますが、結局のところ空白・改行区切りによる複数の数値の入力というのは頻出処理と言えるでしょう。
例えばEOFまでの可変個読み込みの処理の実装として、次のようなものが挙げられます。

EOFまで読み込む例のコード全体
dump付EOFまでの数値入力処理
>,+[
 ** compare **
 ++>>+>-[----<<<[->]>>-]
 #(dump)
 <[-
  ** greater: number: update **
  <<<[->++++++++++<]>[-<+>]
 ]
 >>[[-]
  ** less: space or newline: next **
  >
 ]
<<,+]
#(dump)

実際に 5, 207, 69 の3数+改行を読み込んで、1セルおきに保存した状況は次の画像のようになります。

  • 比較処理による数字/区切り文字判定
    どのようなケースになるにしても、数字と区切り文字(空白・改行)の判別は必須となります。それに数字→数値変換も兼ねた処理を考えます。
    そのような場合、2セル間を挟んだ2数で大小比較・差の計算を行う [<<<[->]>>-] が典型的ですが、そうすると比較用の48 ( '0'のASCIIコード ) やその近くの数字を用意する必要があります。
    そこで、これを応用して 255 を 5刻み、入力文字の文字コードを1刻みで減らすように差をつけ、比較用の数値の簡略化を行ったのが , → +++>>+>-[----<<<[->]>>-] です。
  • 判定後の分岐
    判定後どうするかは、数値の扱いやセルの構成によって様々ですが、数字が来た場合は蓄積してた数を10倍して足して書き戻す、区切り文字が来た場合はセルを移動して次の入力に備えるといった分岐になります。なお、セルの上限は255なので、それより大きな数を扱う場合は「10倍して足して…」ではなく、複数セルで数値管理することを考えなければなりません。
    さて、EOFまで読むケースであればただセルを進めていけば済みますが、指定の個数を読み込む場合は個数用のカウンタを設けカウントダウンしていく処理も併せるような形になります。以下に5個の数値を読み込む例も載せます。
    5個の数値を読み込む例
    dump付数値5個入力処理
    +++++[
 ** compare **
 >>,+++>>+>-[----<<<[->]>>-]
 <[-
  ** greater: number: update **
  <<<[->++++++++++<]>[-<+>]
 ]
 >>[[-]
  #(dump)
  ** less: space or newline: next **
  <<<<<-[->>+<<]
 >>>>>>]
<<<<]
#(dump)

    区切り文字の場合の分岐ではカウンタをスライドしつつデクリメントさせる処理を組んでおり、このカウンタを全体のループの条件変数とすることで丁度5個分の数値入力を実現しています。

おわりに

ということで、幾つかの処理を取り上げました。問題のコアな部分に注力するために、こういった定型的な処理は使い回せるようにすると楽ができるのではないかと思います。

Discussion