AtCoder に登録したら解くべき精選過去問 10 問を難解言語 Befunge-93 で解いてみた #競技プログラミング

問題を解くにあたって、デバッグには HTML5 Befunge93 Interpreter を、実行テストには AtCoder のコードテストを利用しました。

HTML5 Befunge93 Interpreter は AtCoder のジャッジと一部動作の異なる部分があるのでご注意ください。

• 命令 p, g で指定する行・列の順番が逆
• p で値を書き込んだとき、その値を $\bmod 65536$ したものが書き込まれる
• スタック内の値は JavaScript の Number 型
• ……etc

提出 : https://atcoder.jp/contests/language-test-202505/submissions/65718451

&&&++. > ~ : 1+ v
       ^      , _ @

和を求める部分は 3 回数値を受け取って足すだけで OK です。数値受け取り & は改行区切り/空白区切りどちらでも機能するのでラクチン。

文字列を受け取る部分が少し厄介です。文字列の長さが与えられないため、実際に受け取った文字を見ながら終点を判定する必要があります。
今回は、入力を最後まで受け取った後さらに ~ で文字を受け取ろうとすると $-1$ がスタックに積まれるのを利用して判定しました。

提出 : https://atcoder.jp/contests/language-test-202505/submissions/65699062

&&*2%v
"Odd"_"nevE",,,,@,,,

問題文の通りに実際に積を計算して、偶奇で左右に分岐させます。
奇数のとき 2 行目で左に移動しながらコードの左端に辿り着きますが、左端からさらに左に移動した場合は同じ行の右端に移動します。いわゆるトーラス形状ですね。

提出 : https://atcoder.jp/contests/language-test-202505/submissions/65695562

数値として受け取って $ \bmod 9 $ するだけです。先頭に余計な 0 がついていてもそれを取り除いて数値として読んでくれます。

提出 : https://atcoder.jp/contests/language-test-202505/submissions/65736723

v
&  > 00g .@
v _^# : -1                  0&v
   > :2% #v_ 2/ \ 1+ \ 
          >$ :00g ` #v_ 00p ^
                     >$     ^

ループや分岐が入ってきて一気に Befunge らしいコードになってきました。
分岐の命令だけでは _ の左右か | の上下にしか分けることができませんが、> #v_ と書くことで右と下への分岐をコンパクトに書くことができます。

この問題をスタックだけで解くのは厳しかった⁴ので、コード上の座標 $ (0, 0) $ に答えをメモしています。
$ (0, 0) $ の値を初期化していないためコード内の文字 v が最初に入っていますが、これは数値としては $ 118 $ で、解の上限を上回っているため問題なく AC できます。

提出 : https://atcoder.jp/contests/language-test-202505/submissions/65737334

&&&&v
   v> 30p 20p 10p 00p
v  >  552** :21p 2* :11p 5* 01p 0 90p
            > 90g.@
> 20g v -1 _^# :g22  $ 22p 10g v -1 _^# :g21$   12p 00g v -1 _^# :g20                                   02p 22g 21g * 12g 11g * 02g 01g * + + 30g - #^ _

うまくやれば多重ループを減らせますが、今回は愚直に 3 重ループで書きました。

== のような比較演算はありませんが、引き算 - した結果が $0$ になるかで判定可能です。（右下端、=X?の部分）

最終行の答えに 1 を足す部分が右端からはみ出してしまったので、左側に続きを書いています。1 行の文字数上限 80 文字は意外と厳しい……

提出 : https://atcoder.jp/contests/language-test-202505/submissions/65742290

&&& 25* 50p 1+ 20p 1- 10p 0 00 p v  > 00g.@
          v : p090               $ 90g 10g ` #v_                        ^
                  > 20g 90g ` #v_           ^
                               > : 00g+ 00p ^

比較演算子が ` の $\gt$ しかないため、$\ge$ の比較をしたいときは一工夫必要です。今回は $ s \ge A $ の代わりに $s \gt A-1 $ としましたが、$ \neg (s \lt A)$ とした方が自然ですね。⁵

提出 : https://atcoder.jp/contests/language-test-202505/submissions/65720829

v

  //00: temp, 0x:1-51, 1x: 52-100, 20: 52, 21,22: tempxy, 23: 100
v
> 69*2-02p 455**:32p v
 g00 0 p00 _ v#     : $$ 0 00p v
   +1 g00_ v# -g23   32g 00p v
 - p00 -1 _ v# : g00 $.@

恐らくこの 10 問の中で一番実装が難しいです。ソートする部分を自前で実装する必要があります。
定番はバブルソートと思いますが、Befunge は 1 行に 80 個しかデータを置けないため、100 個のデータを比較ソートするのも実装がそこそこ面倒です。そこで今回は代わりにバケットソートを使って実装してみました。

整数 $ n $ の出現回数を座標 $(n \bmod 52, n/52)$ へ記録することにして、記録に使う部分を全て値 $ 0 $ に初期化 (6 行目) → 出現回数をカウント (8 行目) → 整数 $ n $ を昇順に見てそれぞれ出現回数分スタックに積む (10 行目) という流れで、$ a $ をソートしたものがスタックに乗るようにしています。

最後にソートされたデータを交互に足し引きを繰り返す部分ですが、降順かつ末尾に $ 0 $ が並んだ数列 $ a $ に対して ans ← a[i] - ans を $ 100 $ (偶数)回実行することにより、カウントや偶奇による分岐をサボりました。⁶

提出 : https://atcoder.jp/contests/language-test-202505/submissions/65717630

v

& //00:ans, 0x:1-51, 1x: 52-100, 20: 52
v                  > 00g.@
> 000p 69*2-02p v _^# :-1                         & :02g/12p 02g%22p  22g12gg2% #^ _ 122g12gp 00g1+00p ^

先ほどと同様に、整数 $ n $ の出現済みフラグを座標 $(n \bmod 52, n/52)$ に記録していきます。

初めて出現した整数に出会う度に答えに 1 を足すだけなので、先ほどの問題よりもやることが少ないです。

提出 : https://atcoder.jp/contests/language-test-202505/submissions/65722186

vNYmgs // 01: N, 02: Y, 03: m, 04: g, 05: s
                     > 01-:.:..@
> & 10p &8/5/5/5/ 20p 9 40p v
      v p04 -1 g04 _ ^# g04  20g       10g     - 40g 4* - : 0 \` #^ _ : 9% #^ _ 9/ 30p
    v>> 52* 10g * 5 40g * - 20g    - : 0 \` #^ _ : 9% #^ _ 9/ 50p
    > 30g. 40g. 50g. @

4 問目の ABC087B – Coins と違って、こちらではしっかり連立方程式を解く方法で実装してみました。
シンプルに 2 重ループで解いても間に合うとは思います。（未検証）

提出 : https://atcoder.jp/contests/language-test-202505/submissions/65723621

<_v>$$                                                              v
                        >      "SEY",,,@
vp06p05p04p03p02p01p00 _^# :                                       "dream"   00g-#v_ 10g-#v_ 20g-#v_ 30g-#v_ 40g-#v_ 60g     50g     ^
v               >     $ >     $ >     $ >     $ >
>"dreamer" 00g-#v_ 10g-#v_ 20g-#v_ 30g-#v_ 40g-#v_ 50g-#v_ 60g-#v_ ^
v               >     $ >     $ >     $ >     $ >     $ >     $ >
>"erase"   00g-#v_ 10g-#v_ 20g-#v_ 30g-#v_ 40g-#v_ 60g     50g     ^
v               >     $ >     $ >     $ >     $ >
>"eraser"  00g-#v_ 10g-#v_ 20g-#v_ 30g-#v_ 40g-#v_ 50g-#v_ 60g     ^
v               >     $ >     $ >     $ >     $ >     $ >
>"ON",,@

スタックなので後ろから処理する操作は実装しやすいです。

見ての通り同じような処理をしている部分が多いので、for ループのように書いたり移動方向の >v を書き換えたりして圧縮するのも面白そうです。

提出 : https://atcoder.jp/contests/language-test-202505/submissions/65723944

vNtxytxydt
& @,,,"Yes" 020p 030p 040p v
       v _ ^#  :  &50p &60p &70p
      > 30g 60g - : 0 ` #v _ 0\- v
                         >       > 40g 70g - : 0 ` #v _ 0\- v
      v                                             >       > + 80p
     v> 50g 20g - 90p
    v> 80g 90g - 2 % #v _
    > 80g 90g `      #v _ 50g20p 60g30p 70g40p^
               @,,"No"

今更ですが、コード上の処理が走らない部分には自由に文字を書けます。
このコードでは 1 行目に変数を $N, t’,x’,y’,t,x,y,d,dt$ の順で格納する予定であることをメモしています。

スタックをあまり使わず、変数のような感覚で命令 p g を使うようにするとかなり実装しやすくなります。代償として、Befunge らしさが損なわれます。

精選 10 問ではありませんが、インタラクティブ問題でも動かしてみたくなったのでこちらの問題も解いてみました。
インタラクティブ問題では 出力の末尾に LF (10 進で 10) を入れ忘れると TLE する ので気をつけましょう。

提出 : https://atcoder.jp/contests/language-test-202505/submissions/65830775

v (n, 0): data area : 31bit x 80 = 2480bit
v (n, 1): 2^n
v (n, 2): 0: N, 1: loopcount, 23: nb
> & 02p 1 0 v +1 g21 *2 p1g21 :  : 12p 48* -       |
        > : 0\ 0p 1+ v        $  12g 1+ :12p      :: 48*1-/ 22p 48*1-% 32p 22g0g 32g1g / 2% |
^ p0g22 + g1g23 g0g22 p23 %-1*84 p22 /-1*84 : _@# : & ,*25 . 

$ N $ が最大 $ 1000 $ と大きく、$ 2N+1 = 2001 $ 個の整数の使用フラグを $ 80 \times 25 = 2000 $ 文字しか使えないコード領域に記録するには工夫が必要です。

今回は 1 つの座標に 32bit の情報を入れられることを利用して、整数 $ x $ の使用フラグを $ x/32 $ 文字目の $ x \bmod 32 $ 桁目に保存するような方法で実装しました。⁷

難解プログラミング言語というと簡単な計算でも実装が難しくわかりにくいコードになる印象でしたが、Befunge は数値の入出力と基本的な演算が命令として用意されていて、比較的書きやすく感じました。

また、処理を 2 次元グリッド上に配置していくのは shapez⁸ などの工場建設ゲームを彷彿とさせて、とても面白かったです。

• Befunge 実行環境について

• AtCoder Beginners Selection を難解プログラミング言語で解いてみた記事たち