dcでAtCoder Beginners Selection解いてみた

Last updated at 2024-12-10Posted at 2024-12-10

この記事は理情 Advent Calendar 2024 - Adventarの10日目の記事として書かれました。
dcのコードを読みたくなくなったら、是非他の記事も読んでいってください！

また、この記事は一度完成後、下書きが事故で半分吹っ飛んでいます。そのせいで10日目までに間に合わなくなりそうになりました。¹

はじめに

みなさんはdcという言語をご存知ですか？一時期はコードゴルフに使う言語というイメージでそこそこ有名でしたが、今はNibblesなどのよりコードゴルフに向いた言語の台頭によって、いよいよ取り柄がなくなった言語になってしまいました。

再三「言語」と言っていますが、dcはbashのコマンドの一種で、あながち言語とは言い切れないものです。実際、私はコンテスト中や普段使いでは、ターミナルには常にdcが待機していて、結構日常的に便利な計算機として使っています。余談ですが、私はかつて割と真面目にcdをdcにエイリアスすることを検討したことがあります。

例えばコンテスト中に、2^22がいくつかを調べたくなる時がありますね？その時にターミナルでdcを開いてから

2 22 ^ p

と打ち込むと、

とすぐに帰ってきて、とても嬉しいです。
タイプ数もわずか10個程度で済みます。

こんな便利なdcで、AtCoder Beginners Selectionを10問を解いてみました。²

言語の特徴

dcの大まかな特徴は、

スタックマシンで、メモリは基本的にスタックの形で保存されます。
コマンドの数は他の言語に比べて非常に少なく、
文字列を扱うことはほとんどできません
- 特に文字列の入力を受け取ることはできません。³
任意精度の整数を扱うことができます。
ループは再帰を用いて書きます。

また、AtCoderの使用上、

低速です。ループは10^6回程度しか回りません。
qコマンド⁴を使うことができません。⁵

よく使うコマンドは次の通りです。
基本的にはスタックのtopから「引数の数」だけpopして、コマンドの内容を行います。
なお、簡単のため、これ以降スタックのtopからa, b, c, ...とします。
また、誤解が生じる可能性があるときは、このスタックのことをメインスタックとこの記事では呼称します。

コマンド	引数の数	内容
+	2	a + bをスタックに積む
-	2	b - aをスタックに積む ⁶
*	2	a * bをスタックに積む
/	2	b / aをスタックに積む⁶
%	2	b % aをスタックに積む
^	2	b ^ aをスタックに積む
r	2	a bの順でスタックに積む⁷
d	1	aを2回積む
k	1	小数精度をa桁にする
x	1	aをdcのコマンドとして評価する
s*	1	aをレジスタ*に保存する⁸
l*	0	レジスタ*をスタックに積む
?	0	標準入力を一行そのまま?に埋め込んだと想定してdcで実行する
p	1	aを出力して改行し、aを再度積む
P	1	aが数字ならascii文字として解釈して出力、そうでないならその中身を出力
n	1	aを出力(改行なし)
f	0	スタックの中身をtopから全て表示する

サンプルコマンドとしては次のとおりです。

[HelloWorld!]P # HelloWorld!
[2^]sf 7 lfxp # 49
10k 22 7 / p # 3.1428571428

その他コマンドは、各問題で登場した時に改めて解説します。

では、実際に問題を解いていきましょう!

PracticeA - Welcome to AtCoder

早速入力に文字列が含まれているので無理です。(悲しい)⁹

ABC086A - Product

a * b % 2を計算すればよく、この値が1ならOdd、0ならEvenを出力すれば良いので、次のコードでACとなります。

ACコード

[Odd][Even]?*2%1+Rp

ここでRコマンドは次のようなコマンドです。

コマンド	引数の数	内容
R	1	スタックのtopからa番目の要素をtopに持ってくる

これを利用すると、次のように簡易的な条件分岐が簡単に実装できます。

5 4 3 2 1 3Rp # 3が出力
5 4 3 2 1 2Rp # 2が出力

今回は、スタックに[Odd][Even]を積み、Rによってどの文字列を一番上に持ってくるかを選んでいます。

ABC081A - Placing Marbles

普通に実装しようとすると大変ですが、実は入力を9で割った余りがそのまま答えになります。

ACコード

?9%p

ABC081B - Shift only

問題としては単純で、各A_iを2で割れるまで割って、その回数のminを取れば良いです。
先の問題みたいな簡略化はできないので、頑張ります。

ACコード

# rはスタックの入れ替え
# mはmin(a, b)を積む
[r]sr[d3Rd3R>rS_]sm

?sn
?
# Aが答えとなり、とりあえずinf = 99にしておく
99 sA
[
    # aは各数字が何回2で割れるか
    _1sa
    [
        la 1+ sa
        2~0=x
    ]dsxx # xのループはナイーブに2で破り続ける
    
    s_ # A_iを2で割った後の残りを_レジスタに捨てる
    lA la lm x sA # Aをmin(A, a)で更新

    z0<y # スタックにまだ数があるならループ
]dsyx # yのループで各A_iについて処理

lAp # 答えの出力

色々と初見の命令があると思うので、補足します。
なおコマンドではないですが、負の数のリテラルは-ではなく_を用いて_1のように書きます。

コマンド	引数の数	内容
>*	2	a > bならレジスタ*を実行¹⁰
~	2	a / bとa % bをスタックに積む
z	0	スタックに積まれている要素数をスタックに積む

dcのループは基本的に

[
    処理...
    (ループを続けたいなら*を実行)
]ds*x # ds*xは複製して一つをレジスタ*に保存して、その後実行するイディオム

のような形になっています。これに慣れればこの問題の実装は難しくはありません。

ABC087B - Coins

3重for文を頑張って回します。ループの書き方に慣れればなんとかなります。

ACコード

?sa
?sB
?sC
?sn

fはdをインクリメントする関数
[ld1+sd]sf

[
    lBsb
    [
        lCsc
        [
            # 足してnに等しかったらdをインクリメント
            500la* 100lb* 50lc* ++
            ln=f

            # ループ処理
            lc1-dsc0!>z
        ]dszx

        # ループ処理
        lb1-dsb0!>y
    ]dsyx

    # ループ処理
    la1-dsa0!>x
]dsxx

ldp

ABC083B - Some Sums

N = 10^4程度ならループが回るので回します。
a <= x <= bの判定が難しいので、なんとか頑張ります。
(下のコードでは複雑なことをしていますが、マクロで愚直に組むこともできます。)

ACコード


# 変数類の保存
?sbsasn

# Aが答えで、Aにnを足す関数
[lAln+sA]sh

# 5桁の数の桁和を計算する関数
[
    10000~
    1000~
    100~
    10~
    ++++
]sf


[
    # 桁和をxとすると、
    lfx

    # (x - a)とmax((x - a) % (b - a + 1), 0)を計算する
    la-d
    lbla-1+
    %kK
    
    % 二つの値が等しいならa <= x <= b
    =h

    # kのリセット
    0k
]sg

# 1..nでループする
[
    lnlgx
    # ループ処理
    ln1-dsn0<x
]dsxx

# 答えの出力
lAp

ここではkKというイディオムを使っています。Kは次のような命令です。

コマンド	引数の数	内容
K	0	現在の小数精度をスタックに積む(デフォルトは0)

ここで、小数精度は0以上であることがミソで、負の数をk命令で小数精度にしようとすると小数精度は変更されず、0となります。これを利用してkKはスタックの先頭の要素について0とmaxを取る操作として応用できます。

ABC088B - Card Game for Two

難問です。大きい方から奇数番目の総和から偶数番目の総和を引かなくてはなりません。

ACコード

?sn
# 0は番兵
0?
# rはスタックの入れ替え
[r]sr

# 0は番兵
0St
# 一番大きいもの以外tに追いやる
[
    # 小さい方をスタックのトップに持ってくる
    d3Rd3R<r
    # 一番大きくないものはtに追いやる
    St
    z2<o
]so

# tからメインスタックに戻す
[
    Ltlt0<i
]si

# 入力が奇数個の時のための処理
[
    # 2Qでループを脱出
    lA+sA2Q
]se

# メインのループ
[
    # 最後の一個は個別に処理
    z2=e
    # メインスタックの先頭を最大の要素にする
    lox
    # 値をAに足す
    lA+sA
    # tスタックから値を戻す
    lix

    # ほぼ同様
    lox
    lAr-sA
    lix
    z1<x
]dsxx

# 答えの出力
lAp

今回はtレジスタをスタックとみなして最大の要素以外を入れて出すことを繰り返すことでこのような操作を再現しています。ここで、レジスタをスタックとして利用するために、次のような命令を用いています。

コマンド	引数の数	内容
S*	1	メインスタックの先頭の要素を*レジスタをスタックとみなして積む
L*	0	*レジスタをスタックとみなしてpopし、メインスタックに積む

また、Qという命令を用いることでbreakを再現しています。

コマンド	引数の数	内容
Q	1	a段階のマクロを終了する

例えば、2Qとすることで一段階のループのbreakを再現できます。

ABC085B - Kagami Mochi

先ほどの問題と同様にソートすることでも解くことができますが、配列を用いると簡単に解けます。
ここでは配列を用いる解き方を紹介します。

ACコード

?sn
[
    # 配列Vの(標準入力)番目を1にする
    1?:V
    # ループ処理
    ln1-dsn0<x
]dsxx

# i = 1..100でループさせる
100si
[
    # V[i]の取得
    li;V
    # 答えを表すレジスタAに足す
    lA+sA
    # ループ処理
    li1-dsi0<y
]dsyx

lAp

まずは配列を扱うための命令を紹介します。なお、配列は全て0で初期化されています。

コマンド	引数の数	内容
:*	2	*のa要素目をbにする
;*	1	*のa要素目を取得し、スタックに積む

今回はVを配列とみなして、vector<bool>のように扱い、その後要素が1になっている要素数を数えています。

ABC085C - Otoshidama

ABC087B - Coinsと同じようにループを回したいですが、愚直に回すと計算時間が足りません。ここで、5000円札は8枚以下であればよく、かつ10000円札は2000枚以下で探索すれば十分なので、このようにします。すると計算時間も間に合います。

実装は複雑ですが、Qを上手に用いて頑張りましょう。

ACコード

?sYsN
# 5000円札は9枚以下、10000円札は2000枚以下

# ループ中のcontinueを2Qで再現する
[2Q]sq

# 答えの出力
[
    # 負の数が含まれていたら答えを出力せずに元のループに戻る
    la0>q
    # 32はスペースのASCIIコード
    lan32P
    lbn32P
    lcp
    # 全プロセスを終了
    4Q
]sf

# プロセス終了するためにマクロ内で実行
[   
    # 5000円札は8枚以下
    8sb
    [
        # 10000円札は2000枚以下
        20000sc
        [
            # aに1000円札の枚数とする(負でも気にしない)
            lNlblc+-sa
            
            # お金を足してYに等しかったら出力へ
            la10000*lb5000*lc1000*++
            lY=f
            
            # ループ処理
            lc1-dsc0!>y
        ]dsyx
        
        # ループ処理
        lb1-dsb0!>x
    ]dsxx
    
    # 最後までこのマクロが終了されなかったら解なし
    [-1 -1 -1]P
]x

ABC049C - 白昼夢

文字列を受け取れないので、無理です。

ABC086C - Traveling

10^5回のループはなんとか回るので、あとは頑張って条件分岐を実装します。

ACコード

?sn
# 絶対値
[d*v]sA
# qはNoを出力してプロセス終了するマクロ
[[No]p3Q]sq

[
    [
        # 変数類の保存
        ?sYsXsT
        
        # xの距離の計算
        lXlx-lAx
        # yの距離の計算
        lYly-lAx
        # dはマンハッタン距離
        +sd
        
        # 時間の差よりも距離が大きかったらNo
        ldlTlt-<q
        # 時間の偶奇と距離の偶奇が違ったらNo
        ldlTlt-+2%1=q
        
        # 値の更新
        lXsxlYsylTst
        
        # ループ処理
        ln1-dsn0<f
    ]dsfx
    
    # 最後まで実行されたらYes
    [Yes]p
]x

さいごに

ここまで読んでくださり、ありがとうございます。

完走した感想ですが、今回可能な限り可読性の高いdcのコードを書こうとした結果、自分自身のdcコードを書く速度が上がったことが実感できました。¹¹

終盤は長いコードしかなくて、dcであることが重荷になる問題しかありませんでしたが、軽い計算程度ならdcは非常に役に立つツールだと思います。もしよかったら、たまにdc君のことも思い出してあげてください。

最後に一言、競プロはC++¹²でやりましょう。

[最上級の罵倒]!! ↩
「全て解けた」ではないことに注意です。 ↩
入力に未定義の文字が含まれているだけでエラーを標準出力に出力しやがるので、確定でWAが出ます。 ↩
プログラムを終了するコマンドですが、謎にREが出てしまいます。 ↩
どうしても使いたい場合は、[処理]xとし、「処理」内でqの代わりに1Qを使うと良いです。 ↩
一見a, bが逆で非直感的ですが、実際には6 4 -で6-4が計算されるので、人間的にはかなり自然だと思います。 ↩ ↩²
つまりスタックのtop二つの順が入れ替わります。 ↩
*には(制御文字含む)任意のascii文字が使えます。 ↩
実はdcでは!コマンドからbashの任意コードを呼び出すことで解くことは可能ですが、これはdcというよりbashなので省略します。 ↩
<, =, !<, !>, !=はこれの逆や等号、あるいは否定バージョンなので説明を割愛します。 ↩
そのため書き直したコードが何個かあります。 ↩
あるいはPython, Java, Rust等あなたの好きなdc以外の言語 ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up