読者です 読者をやめる 読者になる 読者になる

Brainf**kコード解説 BBQ Easy ( AGC001-A )

はじめに

Brainf**k講座そのものは第8回で終わっているのですが、これからちょくちょく、Brainf**kのコードを取り上げてざっくりと解説して行こうかと思います。今回はAtcoder Grand Contest 001-AのBBQ Easyという問題です。

一般的な解法

問題の詳細は上のリンクをたどってご覧ください。が、この問題の解法としては、

  • 入力の2行目の数値 ( 空白区切り ) の小さい方から1つおき ( 1番目、3番目、… ) に和を計算し出力する

というものになっています ( 1行目は要素数なので無視しても構いません )。例えばRubyの実装だと次が考えられます。

gets
puts gets.split.map(&:to_i).sort.each_slice(2).reduce(0){|s,(x,d)|s+x}

BF実装のポイント

さてそうすると、BFで実装する上で次のポイントが出てきます。

  1. 空白区切り、改行終了の数値の解釈
  2. ソート
  3. 総和

1.はある意味典型の処理なので、一度こなしておけばあまり悩まないと思います。
今回ポイントとなるのは 2. のソートですね。ただし、これは2要素のソート ( swap ) さえできれば、それを繰り返すことでバブルソートが実装できますので、それほど難しくはありません。
さて。残るは3.です。これはideoneのbffであれば、セルの最大値が$2^{32}-1$なので特に問題にならないのですが、AtcoderのBF実行環境は、ubuntuのbfというインタプリタであって、セルサイズが$2^8-1$です。つまり、そのまま足し算すると簡単にオーバーフローしてしまいます。なので、ここはBCD演算が必要です。面倒ですね!

実装

というわけで、コードの全体は次のようになります。

入力ループ

1行目は改行まで読み飛ばすとして、2行目の入力については、数字、空白 ( 区切り文字 )、改行 ( 終端文字 ) の3種類を捌く必要がありますので、状態遷移ぽく処理しています。Rubyでの疑似コードは次の通りです。

a=[-1,-1,0] # 終端
while c=$<.getc
  q,r=c.ord.divmod(12)
  case q
  when 0 # 改行
    break
  when 2 # 空白
    a.push(0)
  when 4 # 数字
    a[-1]=a[-1]*10+r
  end
end

なお、多段if-else(switch)のelse用制御変数は、divmodでできる非ゼロのdを流用しています。q=2,4の「値の追加」「ループからの脱出」は、いずれもセルの位置をずらすだけです。( 値の追加は2セル右に、脱出は1セルずらして空白に出るようにしておく )

バブルソート

バブルソートについては、2要素のソート ( swap ) を繰り返すことになりますので、その部分を見ていきます。

まず、入力が完了した時点では、数字は1セルおきに格納しているのですが、ソートを行う前に右端を1つ右にずらして2セル間を空けるようにします。ソートが進む毎に各数値は1セルずつずれていき、最終的にまた1セルおきになる ( 全体が1セルずれる ) 寸法になっています。

43:  * memory layout: a_tb_
~~
48: a[>>t+>b[->]<<<a_?[a[->>>b+<<<]a+>>t-<_]<a-]

ソートの部分を抜粋すると、上のようになっています。
このコードは一種の大小比較になっています。a,bを1ずつ減らしていき、最終的にa,bどちらが先に尽きる ( 0になる ) かで挙動を変えるものです。Rubyによる疑似コードは次の通りです。

while a>0
  t+=1
  if b>0
    b-=1
  else
    b+=a
    a=1
    t-=1
  end
  a-=1
end

elseの処理は、bが先に尽きる、つまりbの方が小さい場合です。ループはaを制御変数としていますので、ループを終わらせるためにaをクリアしています ( 1にしているのは、a-=1でゼロになるようにするため )。

結果的に、tには min(a,b) が、bにはabs(a-b)が保存されますので、t を左隣 ( 元のaの右隣 ) と、元の b のセルに足し込むと、a,bが1つおきの位置でソートされた状態になります。

なお、今回は1つ1つの値が100以下ですから、この2要素間のソートが100ステップオーダ、要素数が100なので、バブルソートとして5,000回程度の比較、全体として0.5Mステップオーダなのでなんとかなりましたが、もっと規模が大きくなると実行時間的に耐えられなくなると思います。

総和処理

最後に総和処理です。セルに保持できる値が十分に大きければ、本当に足すだけで済むのですが…。
仕方がないのでBCD演算にします。手順としては次の通り

  1. 最初の数 ( 一番右の数値 ) を divmod 10 の繰り返しでBCDに変換する
  2. 次の数をBCDの1の位に足す。もう数がなければ終了
  3. 繰り上がり ( carry ) がなくなるまで、divmod 10 による繰り上がり処理を行う
  4. BCDの桁を全体的にずらして 2 に戻る

最上位の桁を0にしておいて桁の拡張に備えるのは、以前の講座の第8回にあるのと同じテクニックです。が、今回違うのは片方が非BCDなので、 carry をどこまで処理して良いか分からないところです。両方がBCDであれば全桁処理すれば良いだけなのですが。
そこで、divmod 10 の商を上位への繰り上がりとして足すだけでなく、「繰り上がり発生フラグ」としても保存し、フラグが立っているなら次の桁の処理も行うようにしています。ここが以前とは少し異なるところです。

終わりに

本当は図も付けたかったのですが、それなりに面倒ではあるので、今回は文章のみにしました。もし挙動を確認したい場合は、Brainf**kインタープリタで、ダンプ機能を使って、処理の時々のセル状況を確認して頂くと良いかと思います。