AtCoderに登録したら解くべき精選過去問10問をJelly言語で解いてみた

Jellyは、コードゴルフを得意とするプログラミング言語です。その性質上、Jellyは非常に短いコードで複雑なプログラムを書くことに特化しています。

JellyはそのGitHubリポジトリが公式サイトみたいなもので、インタプリタの挙動が言語仕様という感じのなかなかロックな言語です。しかもインタプリタはPythonで書かれているため、言語仕様の細かい部分がPythonの仕様そのままという愉快な特徴を持ちます。

自分もまだJellyを0.05%くらいしか理解していませんが、その愉快さの一端を皆さんに知ってもらうべく、今だに色褪せないプログラミング練習問題集の金字塔・AtCoderに登録したら解くべき過去問精選10問をJellyで解いてみました。なお、当然ながらAtCoderはJellyに対応していませんので、書いたコードは手元で適当に試しています。

各回答の解説もありますが、筆者もJellyを全然理解していないので突っ込みは大歓迎です。あと、筆者が問題を解き進めるにつれてJelly力が上昇していくのが見て取れますのでぜひそこを楽しんでください。途中のB問題あたりが一番コードがごちゃごちゃしており、C問題になると逆に洗練されていきます。

まず問題に入る前にJellyの概要を説明してもいいのですが、とりあえずひとつ具体的なプログラムを見ながら解説したほうが分かりやすいでしょう。ということで、さっそく1問目を解いていきます。

ABC 086 A - Product

2つの整数が標準入力から与えられるので、それらの積が偶数かどうか判定せよという問題です。偶数ならEvenを、奇数ならOddを出力します。

Jellyによる回答コードは次の通りです。

ɠḲV×/ị“Odd“Even”

ほとんどの方が🤔という顔をしているかと思いますので、何をやっているのか理解するためにJavaScriptにざっくりと翻訳したバージョンを載せておきます。inputは標準入力の内容だと思ってください。

JavaScriptに翻訳したバージョン

const line = input.split('\n')[0];
const ints = line.split(' ').map(x => parseInt(x, 10));
const prod = ints.reduce((a, b) => a * b);
console.log(["Odd", "Even"][(prod - 1) % 2]);

さすがコードゴルフ用言語だけあって、JavaScriptバージョンに比べて随分短いですね。

とはいえこれだけ見てもJellyを知らない方には何が何だか分からないと思いますので、上のJellyプログラムを順番に解説していきます。

まず、Jellyプログラムにおける基本的な概念はlinkです。これは関数のようなもので、0〜2個の引数を受け取ってひとつの値を返します。あとで解説しますが、このプログラム全体がひとつの0引数linkになっています。linkを作る方法のひとつはいくつかのlinkを並べることです。linkを並べたものをchainと呼びます。

また、Jellyのプログラムの基本単位となるのがatomです。これは組み込みlinkであり、ほとんどのatomは記号1文字によって表されます（たまに2文字で表されるものがあります）。

atomは引数の数によって分類されます。0引数のものをnilad、1引数のものをmonad、2引数のものをdyadと呼びます。また、linkについても同様の分類があり、0引数のものをniladic link, 1引数はmonadic link, 2引数はdyadic linkと呼びます。

もうひとつ重要な要素がquickです。これはlinkを作るための組み込み構文です。quickもまた大抵が記号1文字で表されます。

プログラムを分解する

さて、上のプログラムは次のように分解できます。それぞれがlinkであり、プログラム全体はこれらのlinkを繋げてできたchainです。

• ɠ 標準入力から1行読んで文字列を返すnilad。
• Ḳ 文字列をスペースで区切った配列を返すmonad。
• V 文字列をJellyプログラムと見なして実行した結果を返すmonad。
• ×/ 乗算を行うdyadである×にquick/が付いたもの（後述）。これ全体で一つのmonadとして扱われる。
• ị リストの指定したインデックスの値を返すdyad。
• “Odd“Even” 文字列リテラル。この場合["Odd", "Even"]という文字列の配列を返すniladとなる。

ちなみに、chainはその各構成要素のarity（引数の数）を並べた名前で呼ぶこともあります。この場合はプログラム全体は0,1,1,1,2,0-chainとなります。

ちなみに、このようなchainのarityはいくつかということは、chainを見ただけでは分かりません。chainを使う側がそのchainのarityを指定することになります。

今回はこのchainがプログラム全体でした。プログラム全体のchainのarityがいくつになるかというのは、プログラム（を実行するインタプリタ）がいくつのコマンドライン引数を渡されたかによって決まります。我々は入力をコマンドライン引数ではなく標準入力から受け取るのでコマンドライン引数はありません。よって、このchainはniladic chain（引数0個のchain）として扱われます。

プログラムの実行を追う

では、このプログラムはどのように実行されるでしょうか。Jellyの評価規則は複雑ですが、基本的には左から右にパイプライン的に計算していきます。

今回の場合、プログラム全体のchainの最初はɠというniladです。この場合、これが返した値、すなわち標準入力から受け取った文字列から計算を進めます。例えば、標準入力が3 4という文字列だったとしましょう。

chainの次はḲというmonadが控えています。chainの先頭がmonadのときは普通にそのmonadを現在の値に適用します。すると、現在の値は["3", "4"]になります。

次はVというmonadです。これは文字列を受け取ってそれをJellyプログラムとして実行する、いわゆるevalです。なぜここでこんな命令を用いるかというと、これは文字列を数値に変換することが目的です。Jellyは数値リテラルを持つため、数値のみの文字列をJellyプログラムとして実行すると文字列を数値に変換できるのです。

また、Vの引数は文字列なのに今持っている値は文字列の配列です。このような場合は自動的にmapされます（これをvectorizeといいます。vectorizeするかどうかはatomごとに決まっています）。よって、Vを評価した後の値は[3, 4]となります。

次は×/です。これは2文字で1つのmonad（より正確にはmonadic linkですが、以降は適当に混同します）として振る舞いますが、その中身は×というdyadに/というquickがくっついたものです。

先に説明したようにquickは制御構文のようなもので、それぞれが特殊な構文を持ちます。/の場合は、dyadに続けて/を書くという構文でした。

/は一言でいうとreduceです。×/の場合、渡された配列を×でreduceした結果を返すというmonadになります。

よって、今の値が[3, 4]だったのでこれに×/を適用した結果は12です。

次はịというdyadです。dyadの評価は複雑なのですが、dyad niladという順で並んでいる場合は簡単です。今回はちょうど次に“Odd“Even”というniladがありますね。この場合は現在の値をịの左辺、“Odd“Even”を右辺としてịを評価します。

ịは右辺の配列の左辺番目の要素を返すdyadですが、2つ注意すべき点があります。ひとつは、インデックスは1始まりということです。もうひとつは、左辺が配列のインデックスに収まるように配列の要素数でmodを取られるということです。

今回、左辺は12で右辺は["Odd", Even"]という配列でした。12はmod 2で2と同じなので、["Odd", "Even"]の2番目の要素である"Even"が返されます。

以上で評価は終わりです。Jellyではプログラム全体のchainを評価した結果が出力されるので無事にEvenが出力されました。

1問目なので解説が長くなりましたが、ここからはサクサクと進みましょう。

ABC 081 A - Placing Marbles

これは010のような3文字の文字列が与えられるのでその中の1の個数を数えて出力する問題です。

Jellyによる回答はこれです。

ɠċ”1

さっきよりも短くなりましたね。これは0,2,0-chainです。

ɠは先ほどと同じで標準入力から1行読みます。この先もお世話になるでしょう。

ċはdyadであり、左辺のリストの要素のうち右辺と等しいものを数えて返します。ここで、左辺はリストではなく文字列のはずですが、実はJellyでは文字列は文字のリストなので大丈夫です。

最後の”は文字リテラルの記号です。これは直後の文字1つとセットの構文であり、”1は"1"という文字を返すniladとなります。

よって、このプログラムは全体として、標準入力から1行読んでそれに含まれる1の個数を返すというコードになっています。じつに正統派な回答ですね。

ABC 081 B - Shift Only

次はB問題です。果たしてB問題にもJellyは通用するでしょうか。

これは整数の列が与えられるので、全部を2で割るという操作を何回行えるか答える問題です。列のいずれかの数が2で割れなくなったら終了です。例えば8 12 40だったら全部を1回2で割ると4 6 20になり、もう1度2で割ると2 3 10となります。この時点で奇数3が出現したためもう一度2で割ることはできず、結果は2回となります。

入力形式は以下のように、1行目に列の要素数、そして2行目に列の中身という形です。

3
8 12 40

さて、回答のJellyプログラムはこれです。なお、今回から見やすさのために適宜空白を入れていますが、空白は基本的に意味はありません。

ɠɠḲV ÆF µḣ1⁼[2]µƇ€ µị@1ị@2µ0µ¹?€ Ṃ

これは0,0,1,1,1,1,1,1-chainです。部分ごとに解説していきます。

ɠɠḲV ÆF

最初はお馴染みのɠですが、今回は標準入力の1行目は要らないので1回目のɠの結果は捨てています、2つ目のɠの結果が2行目となります。ḲVは1問目と同様にスペースで区切ったあと数値に変換します。この時点で、入力が8 12 40だとすれば結果は[8, 12, 40]となっています。

次のÆFは2文字でひとつのmonadです。これの意味は素因数分解で、与えられた数値を素数とその指数の組に変換します。今回は与えられる値が数値の引数なのでvectorizeが発生し、結果は[[[2, 3]], [[2, 2], [3, 1]], [[2, 3], [5, 1]]]となります。

µḣ1⁼[2]µƇ€

次はµḣ1⁼[2]µƇ€の部分を解説します。まずμは「新しいmonadic chainを開始」という意味の制御構文です。実はプログラムは「chainのchain」になることができ、そのときchainたちがどこで区切られているのかを指示するためにμが使われます。また、前に「chainは使われ方によってarityが決まる」としましたが、μによって区切られたときはそれ以降のchainは既に使われ方がmonadic chainに固定されています。他にniladic chainやdyadic chainを作るための構文もあります。

まずひとつ目のmonadic chainであるḣ1⁼[2]に着目します。ḣは「左辺のリストの最初の（右辺）個の値を取り出したリストを得る」という意味のdyadです。例えば[1, 2, 3] ḣ 2は[1, 2]です。今回はḣの右辺が1なので、最初の要素のみのシングルトンリストを作るという意味になります。その次の⁼は左辺と右辺が等しいかどうかを判定（返り値は0か1）するdyadです。等値判定のdyadは実は=と⁼の2種類があり、前者はvectorizeする、後者はvectorizeしないという違いがあります。今回はvectorizeしないほうを使っています。

まとめると、ḣ1⁼[2]は「与えられたリストの最初の要素が2かどうか判定する」というmonadic chainになります。

残りのµƇ€の部分ですが、実はƇも€もquickです。Ƈの意味はfilterであり、直前のmonadic chain（fと呼ぶことにしましょう）とセットで「配列を受け取り、fの条件を満たす要素のみを抽出した新しいリストを返す」というmonadになります。€の意味はmapで、同様に直前のmonadic chainを配列の各要素に適用するというmonadになります。この場合、直前のmonadic chainとはƇによって作られたmonadic chainのことです。先頭にあるµはƇの「直前のmonadic chain」としてḣ1⁼[2]を参照してもらうために必要です。

ややこしいですが、ḣ1⁼[2]が表すmonadをfと書くことにすると、µḣ1⁼[2]µƇ€は以下のJavaScriptコードに相当するmonadを表現していることになります。

arr => arr.map(arr2 => arr2.filter(v => f(v)))

プログラムの流れに話を戻すと、いま得られている[[[2, 3]], [[2, 2], [3, 1]], [[2, 2], [5, 1]]]にµḣ1⁼[2]µƇ€というmonadを適用すると[[[2, 3]], [[2, 2]], [[2, 2]]]になります。要するに2以外の素因数の情報を除去したかったわけです。

µị@1ị@2µ0µ¹?€

この部分もやはり1つのmonadを作っています。まず、@は「与えられたdyadの左辺と右辺を逆転したdyadを作る」というquickです。今回2箇所の@は両方ともịについています。ịは「右辺の配列から左辺番目の要素を取り出す」だったので、ị@は「左辺の配列から右辺番目の要素を取り出す」というdyadになります。

また、¹は恒等monadです。つまり、与えられた引数をそのまま返します。

ここでのポイントは?というquickで、これは条件分岐のlinkを作ります。?は3つのlinkを受け取って新たなlinkを作るのですが、作られたlinkのarityは受け取った3つのarityの最大値となります。ここでは1なので、?はmonadを作っています。

面倒なのでJavaScirptコードで説明すると、t, f, cをそれぞれmonadとするときt f c ?が表すmonadはvalue => c(value) ? t(value) : f(value)です。すなわち、cが条件部分であり、それに引数を与えた結果が真ならばtの結果を返し偽ならばfの結果を返します。今回cは¹でtはị@1ị@2、fは0です。

最後に€によって、?が作ったmonadをmapで持ち上げています。

ここでやりたかったことは、入力数列の各数値から作った[[2, 3]]のようなリストのリストから3という数値を取り出すことです。そのために、ị@1ị@2というmonadを作っています。これは「与えられたリストの1番目の要素を取り出し、さらにそれの2番目の要素を取り出す」という意味になります。

ただし、実はこのリストが空リストである場合があります。それは元の数値が2を素因数として持たなかった場合です。この場合は代わりに0が得られるようにしました。?はこの処理のために使っています。

例えば入力が8 12 20 3だった場合はこの処理の前の時点で値は[[[2, 3]], [[2, 2]], [[2, 2]], []]となっており、これにµị@1ị@2µ0µ¹?€を適用すると[3, 2, 2, 0]となります。

ここまでの処理で、与えられた数列を、それぞれの数が素因数として持つ2の数に変換できました。問題の答えはこれらの最小値なので、最後に残ったṂ（これは配列の最小値を得るmonadです）を使えばOKです。

ABC 087 B - Coins

手持ちに500円玉、100円玉、50円玉の枚数が与えられるので、それらの一部を使って目標金額ぴったりの金額を作る方法の数を求める問題です。

回答コードはこれです。これは0,1,1,1,1,1,2,0,1,2,0,1-chainです。

3RƓ€ Ż€ p/ F€ ×€[500,100,50] S€ ,Ɠ ċ/

今回の方針は500円玉、100円玉、50円玉の使用枚数の組み合わせを全パターン作り、その金額が目標金額ちょうどになるものの数を数えるというものです。普通ですね。

入力が1行につき数字一つになっているのが少しこれまでと違います。

例えばこの入力を例にとって説明していきます。これは500円玉と100円玉が2枚、50円玉が3枚あって合計100円を作りたいという状況です。

2
2
3
100

3RƓ€

入力を受け取る部分です。これは「標準入力から整数を3行受け取ってリストにまとめる」という意味になります。

今回は入力を受け取る部分で新しいnilad Ɠを用いています。これはɠとVをセットにしたようなもので、標準入力から1行受け取ったあとVで評価します。今回のように1行に1つの数値が与えられるときは、niladを1つ使うだけで数値への変換までできて便利です。

全体の流れとしては、まず3にRというmonadを適用して[1, 2, 3]を得ます。次のƓ€で、このリストの各要素をƓ（標準入力から1行読む）の結果で置き換えます。よって、結果は[2, 2, 3]になります。

Ż€

これはŻをリストの各要素にマップしています。Żは引数が数値かリストかで意味が変わるmonadですが、数値nが引数の場合は[0, 1, ..., n]というリストを返します。Rの0始まり版ですね。

結果は[[0, 1, 2], [0, 1, 2], [0, 1, 2, 3]]です。つまり、500円・100円・50円のそれぞれについて使用枚数の候補が列挙されていることになります。なんとなく全探索っぽさが出てきましたね。

p/ F€

/は前にも出てきたreduceのquickです。pは新規のdyadで、「両辺のリストのcartesian productを取る」というものです。例えば[1,2]p[3,4]は[[1,3],[1,4],[2,3],[2,4]]になります。

今回は3つのcartesian productを取りたいので/を用いてpを2回適用しています。結果はこんな感じになります。

[[[0, 0], 0], [[0, 0], 1], [[0, 0], 2], [[0, 0], 3], [[0, 1], 0], [[0, 1], 1],
 [[0, 1], 2], [[0, 1], 3], [[0, 2], 0], [[0, 2], 1], [[0, 2], 2], [[0, 2], 3],
 [[1, 0], 0], [[1, 0], 1], [[1, 0], 2], [[1, 0], 3], [[1, 1], 0], [[1, 1], 1],
 [[1, 1], 2], [[1, 1], 3], [[1, 2], 0], [[1, 2], 1], [[1, 2], 2], [[1, 2], 3],
 [[2, 0], 0], [[2, 0], 1], [[2, 0], 2], [[2, 0], 3], [[2, 1], 0], [[2, 1], 1],
 [[2, 1], 2], [[2, 1], 3], [[2, 2], 0], [[2, 2], 1], [[2, 2], 2], [[2, 2], 3]]

これで500円玉・100円玉・50円玉の枚数の組み合わせが全列挙できました。例えば[[1, 2], 1]は500円玉1枚、100円玉2枚、50円玉1枚という組み合わせを意味しています。

ただ、pを2回適用しているので[[1, 2], 1]という不均等なリストになっています。そこで、リストをflattenするmonadのFで均します。これにより[[1, 2], 1]は[1, 2, 1]に変換されます。

ここまで実行すると次のリストが得られます。これで枚数の全組み合わせを列挙できました。

[[0, 0, 0], [0, 0, 1], [0, 0, 2], [0, 0, 3], [0, 1, 0], [0, 1, 1], [0, 1, 2],
 [0, 1, 3], [0, 2, 0], [0, 2, 1], [0, 2, 2], [0, 2, 3], [1, 0, 0], [1, 0, 1],
 [1, 0, 2], [1, 0, 3], [1, 1, 0], [1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 0],
 [1, 2, 1], [1, 2, 2], [1, 2, 3], [2, 0, 0], [2, 0, 1], [2, 0, 2], [2, 0, 3],
 [2, 1, 0], [2, 1, 1], [2, 1, 2], [2, 1, 3], [2, 2, 0], [2, 2, 1], [2, 2, 2],
 [2, 2, 3]]

×€[500,100,50]

€はmapを担当するおなじみのquickですが、今回はその前にあるのがmonadではなく×というdyadです。

€でdyadを持ち上げた場合はその結果もやはりdyadになります。そして、左辺に対してmapが行われます。JavaScriptで書くとこうです。

(left, right) => left.map(value => dyad(value, right))

よって、この部分は×€というdyadの右辺に[500,100,50]を渡していると読めます。

今回の場合、上記のリストの各要素に対して×[500,100,50]が実行されます。

×は普通の掛け算のdyadですが、両辺に対してvectorizeします。dyadの評価において両辺のvectorizeが可能で両辺ともリストの場合は、zipmapのような動作をします。よって、例えば[1, 2, 1]×[500,100,50]は内積のような動作となり、1×500, 2×100, 1×50の結果からなる3要素のリスト[500, 200, 50]が生成されます。

つまり、この計算によって各硬貨の枚数を実際の金額に変換したことになります。

S€

これは配列の和を取るSをmapでリストに適用しています。これにより[500, 200, 50]は750になります。

以上の操作で全体は以下のようなリストとなっています。

[0, 50, 100, 150, 100, 150, 200, 250, 200, 250, 300, 350, 500, 550, 600, 650,
 600, 650, 700, 750, 700, 750, 800, 850, 1000, 1050, 1100, 1150, 1100, 1150,
 1200, 1250, 1200, 1250, 1300, 1350]

つまり、硬貨の枚数の全ての組み合わせの金額が列挙できました。

あとは、このうち目的の金額が何個あるか数えれば終わりです。

,Ɠ

,をリストリテラルの外で使う場合は2要素のリストを作るdyadとして振舞います。Ɠはniladであり、4行目の標準入力を読み込みます。

よって、この時点で全体は以下のような値になります。このように、これまでの計算結果を保持しつつ新たな値を持ちたいときに,が便利です。

[[0, 50, 100, 150, 100, 150, 200, 250, 200, 250, 300, 350, 500, 550, 600, 650,
 600, 650, 700, 750, 700, 750, 800, 850, 1000, 1050, 1100, 1150, 1100, 1150,
 1200, 1250, 1200, 1250, 1300, 1350], 100]

ċ/

これが最後の部分ですが、ċも/も登場済みですね。まずċはリストに含まれる特定の値を数えるdyadで、/はreduceです。

今回のプログラムでは、/が作ったmonadの対象となるのは先ほど作った2要素のリストでした。つまり、これは全体としてċというdyadを左辺[0, 50, ..., 1350]、右辺100で評価するという意味になります。

これは[0, 50, ..., 1350] ċ 100になり左辺のリストの中から100を数えるという意味になります。

よってこの問題を解くことができました。

入力によっては普通に2秒を超えますが（この問題の実行時間制限は2秒）、そこはご愛嬌です。

ABC 083 B - Some Sums

与えられた整数N, A, Bに対して、1からNまでの整数のうち10進表記で各桁の和がA以上B以下であるもの全ての和を求める問題です。

では早速、今回の回答はこれです。

4Ż *@ ⁵
:¢ %⁵ S
Rµ,ǵ€
ɠḲV œṖ@2 r/€Ðe µị@1µ€Ðo Ç€Ðo ðị@2fðƇµ/ µị@1µ€ S

これまでとの大きな違いは、プログラムが複数行あることです。Jellyでは空白は意味を持ちませんでしたが改行は意味を持ちます。

この場合1行が1つのlinkの定義となり、最後の行がmain linkとなりプログラムとして実行されます。main以外のlinkは、他のlinkを指し示すquickを使うことで利用できます。このプログラムでは、「直前のlinkをniladic linkとして参照する」という意味の¢と「直前のlinkをmonadic linkとして参照する」という意味のÇが使われています。

このプログラムを解説するわけですが、疲れてきたのでここからは解説のざっくり度を上げていきます。新規の要素は解説しようと思いますが漏れがあるかもしれませんので、不明点がある場合はコメントで質問するか適宜公式リポジトリを参照してください。

4Ż *@ ⁵

1行目のリンク定義は0,1,2,0-chainであり、これは[1,10,100,1000,10000]というリストに計算されるniladic linkです。冪乗を表す*と10を表す⁵が新しいですね。

:¢ %⁵ S

この2,0,2,0,1-chainはmonadic linkとして使われることを意識しており、「与えられた整数の（10進法での）各桁の和を計算する」というmonadになります。この計算は、与えられた整数を1・10・100・1000・10000で割って小数点以下を切り捨てた整数をそれぞれ計算し、それらを全て10で割ったあと和を取るという手順で行っています。今回、与えられる整数は10000以下であるという制約があるためこの方法で各桁の和を計算できます。

Rµ,ǵ€

これは、整数Nを受け取り、1からNまでの各整数に対して[その整数自身, その整数の各桁の和]というペアを作ってそれらのリストを返すという1,1-monadic chainです。
例えば20を渡された場合は以下のリストが返されます。

[[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6, 6], [7, 7], [8, 8], [9, 9], [10, 1],
[11, 2], [12, 3], [13, 4], [14, 5], [15, 6], [16, 7], [17, 8], [18, 9], [19, 10],
[20, 2]]

ɠḲV œṖ@2 r/€Ðe µị@1µ€Ðo Ç€Ðo ðị@2fðƇµ/ µị@1µ€ S

これがプログラムのメイン部分です。複雑ですがよく見ると0,1,1,2,0,1,1,1,1,1,1-chainになっています。

まず入力全体をいつものように[20, 2, 5]のようなリストに変換しています。

œṖは与えられたリストを指定した位置で分割するdyadで、これにより入力が[[20], [2, 5]]のようになります。

次の部分にあるrは与えられた2整数間のrangeを作るdyadで、例えば2 r 5は[2, 3, 4, 5]になります。Ðeがやや難しいquickで、これは「与えられたリストにlinkを適用して新しいリストを作り、偶数インデックスについては新しいリスト、奇数インデックスについては元のリストから値を取り出して作った新しいリストを返す」というlinkを作るquickです。言葉でいうと難しいですが、今回はr/をリストの2番目の要素に適用していると思ってください。r/€Ðeを通すと[[20], [2, 5]]は[[20], [2, 3, 4, 5]]になります。

次の部分に登場するÐoはÐeの仲間で、偶数ではなく奇数インデックスのみ変換します。µị@1µ€Ðoの部分は[20]をリストから出して20にしています。

さらにÇ€Ðoでもう一度Ðoを使っています。これは20に対してひとつ上のlinkを適用するということです。

次のðị@2fðƇµ/で、左のリスト（[[1, 1], [2, 2], ..., [20, 2]]）の要素のうち「各桁の和」が右のリスト（[2, 3, 4, 5]）に含まれているもののみ抜き出す操作を行っています。これにより、問題の条件である「1以上N以下の整数のうち、各桁の和がA以上B以下であるもの」のリストが得られました。

最後のµị@1µ€ Sでそれらの和を計算しています。めでたしめでたし。

ちなみに、今回プログラムが複数行になった理由は、Jellyでは「chainのchainのchain」が書けないという点にあります。µなどの構文要素によりchainのchainを書くことはできますが、Jellyは括弧のような構文を持たないためこれをネストさせることができません。

代わりに、別の行でlinkを宣言しておいてそれを参照するという手段が提供されているのです。

これでやっと半分ですね。1問ずつ実際にJellyプログラムを書いてから解説を書くということを繰り返して記事を書いているのですが、結構つらくなってきました。あっさり解説しているように見えて、実はこの問題ひとつに対して5時間くらい費やしています。

ABC 088 B - Card Game for Two

カードゲームの最適解を求める問題です。詳しいことは問題文を見て欲しいのですが、いろいろな数字のカードが並べてあって、2人が交互に好きなカードを取っていきます。自分の取ったカードの数字の合計が自分の得点となり、得点が多いほうが勝ちです。このカードゲームで2人が最適戦略を取ったときの得点差がいくらになるかを求めよという問題です。

5秒くらい考えると分かる通り、一番数字が大きいカードを取るのが常に一番有利ですね。これを踏まえてプログラムを書くとこんな感じの0,0,1,1,1,1,1,1-chainになります。

ɠɠḲV ṢṚ Œœ S€ _/

ポイントとしては、リストをṢで昇順にソートでき、Ṛで逆順にできます。引き算は-ではなく_なので注意してください。

以上です。

ABC 085 B - Kagami Mochi

これは、円盤系の餅（最大100枚）の大きさ一覧が与えられるので、なるべくたくさん積んだ鏡餅を作ると何段積めるかという問題です。

まあ普通に一番大きいほうから順番に積んでいけば無駄なく積めるのですが、同じ大きさの餅が複数あったら1枚しか使えない点を注意する必要があります。

回答はこれです。これは0,1,1,1,1,1,1-chainですね。

ƓRɠ€ ṢṚQ L

今回、入力の形式が今までと少し違っており、可変長の数値が縦に並んでいます。そのため、最初に与えられる数値の個数の情報を活用しながら入力を読む必要があります。それがƓRɠ€の部分です。

前の問題と同じように降順にソートしたあと、Qでuniqueをかけて重複を取り除いて残った数を数えれば終わりです。

こういう問題ばかりだと楽でいいですね。

ABC 085 C - Otoshidama

いよいよC問題です。さらに難易度が一段階上がった問題にJellyで立ち向かいます。

この問題は整数NとYが与えられ、1000円札・5000円札・10000円札を合計ちょうどN枚使ってY円を作る方法を求めよという問題です。

Nが1以上2000以下なので、まあ解き方としては3種類のうちどれか2種類の枚数を全探索する感じになります。

というわけでソースコードはこれです。

Ḣµ3R-€ µ¹µ? j“ ”
ðṛ,Ɱ _Ż¥ ðⱮ  µ;/
ɠḲV© ị@1 µ,Ż ,ç¥/ ðṛḷḷS _@ḷ ṭ µⱮ/ µ×[ȷ,5ȷ,10ȷ]S = ®ị@2¤ µƇ Ñ

上から1,2,0-chain、2,1-chain、0,1,1,2,0,1,1,1,1-chainです。

今回新登場しているのが©です。実はJellyはレジスタ（別の言い方をすればグローバル変数）を1つだけ持っており、©を付与されたlinkの実行時にその返り値がレジスタに保存されます。レジスタの値は®というniladで取得できます。

今回はまず入力を受け取って[9, 45000]のような配列とし、それをレジスタに保存しています。今回レジスタを使う理由は、入力を受け取ったあと45000を使うのが結構先なのでずっと持ちまわるのが面倒だからです。

他に特筆すべきは¥ですね。これはçの簡易版みたいなもので、直前2つ並んだlinkをまとめて1つのdyadとして扱うものです。別の行に分けてlink定義しなくてもお手軽にひとまとまりのdyadが作れる便利なやつです。

また、main linkの最後に登場しているÑも新規のquickで、これは直前ではなく直後のlinkをmonadic chainとして参照するものです。main linkが一番最後なのにその後とはと思うかもしれませんが、実はこの場合はループして最初のlink定義を参照します。

よって、実はプログラムの最初の行で定義されているリンクが一番最後に使われることになります。

ざっくり動作を解説すると、ɠḲV© ị@1 µ,Ż ,ç¥/ ðṛḷḷS _@ḷ ṭ ðⱮ/までで[[0, 0, 9], [0, 1, 8], ...]のように、1000円札・5000円札・10000円札の使用枚数の組み合わせを全部列挙しています。

その後のµ×[ȷ,5ȷ,10ȷ]S = ®ị@2¤ µƇの部分で、枚数の組み合わせごとにその合計金額を計算し、入力と一致するもののみ残す処理を行っています。

最後の出力は一番上のlinkであるḢµ3R-€ µ¹µ? j“ ”で行っています。これはmonadic linkであり、渡されたリストに対して条件分岐を行っています。これは、リストが空かどうか判定するためのものです。

リストが空でなければその最初の要素（これは[0, 9, 0]のような組み合わせ一つです）を取得し、空なら代わりに[-1, -1, -1]というリストを生成します。そして、最後のj“ ”部分でそのリストをスペースで繋いだ文字列を生成しています。

実行時間は、もはや全く2秒には間に合いません。計算量的には$O(N^2)$なのですが仕方ありませんね。

ABC 049 C - Daydream

与えられた文字列をdream, dreamer, erase, eraserの4種類の文字列のみを繋げて作ることができるかどうかを判定する問題です。前から見るとすこし面倒ですが、後ろから見ていくことで簡単に判定ができるようになっています。

というわけで今回の回答はこれです。

ḣL}¥ ¹ ⁼
çⱮ “maerd“remaerd“esare“resare”
ṫ ị[6,8,6,7]$}
, 2Ŀi1Ɗ 3ŀ/Ñ$ 1 ị@2$?
Ç 2L?
ɠU Ç ị“NO“YES”

Jelly力がだんだん増してきたこともあり、これは今回の記事の中でもかなり綺麗に書けたお気に入りのプログラムです。上から順に2,1,2-chain、2,0-chain、2,2-chain、2,1,1-chain、1-chain、0,1,1,2,0-chainです。

¥や$などによるインラインサブchain（？）を多用しておりややプログラムが複雑になっているので、しっかりめに解説します。一番上から見ていきましょう。

ḣL}¥ ¹ ⁼

これは、2つの文字列lとr（dyadの左辺と右辺をlとrで表すことにします）を受け取って、rがlのprefixかどうかを返すdyadic linkです。

dyadic chainの評価規則に従うと、これの評価結果は(l `ḣL}¥` r) ⁼ rとなります（ここでは説明のために`dyad`でdyadを中置演算子のように書く記法を用いています）。ḣL}¥というのはḣ L}という2つのlinkを¥で繋げてできた2,2-chainなので、l `ḣL}¥` rの評価結果はl `ḣ` (l `L}` r)です。}はmonadを右辺だけ使うdyadに変換するquickなので、これはすなわちl `ḣ` L(r)です。

まとめるとl `ḣL}¥ ¹ ⁼` rは(l `ḣ` L(r)) ⁼ rとなります。まずLでrの長さを取得し、ḣでlの先頭L(r)要素のみを取り出します。それがr自身と一致するか比較することでrがlのprefixかどうかを判定できています。

çⱮ “maerd“remaerd“esare“resare”

これは、"maerd", "remaerd", "esare", "resare"という4つの文字列（問題に出てくる4つの文字列を逆にしたものですね）のそれぞれに対して、与えられた文字列lがそれをprefixとして持つかどうかをひとつ上のlink（ç）を用いて判定するmonadic linkです。Ɱはdyadを右辺に対してmapするdyadに変換するquickです。

例えばこのlinkに"maerdesare"という文字列を与えると[1,0,0,0]というリンクが返ってきます。

ṫ ị[6,8,6,7]$}

これは文字列lと数値rを受け取り、lの先頭[6,8,6,7][r]文字を除いた文字列を返すdyadic linkです。rとしては1から4の整数を期待しています。l `ṫ ị[6,8,6,7]$}` rはl `ṫ` (r `ị` [6,8,6,7])と評価されます。

, 2Ŀi1Ɗ 3ŀ/Ñ$ 1 ị@2$?

ここがこのプログラムの肝となる部分です。これは入力として文字列lを受け取り、その文字列が問題の条件を満たすなら2を、満たさないなら1を返すというmonadic chainです。一気に挙動が複雑になりましたが、実はこれはひとつ下のlink（Ñ）との相互再帰を行うlinkです。

このlinkは全体として、,, 2Ŀi1Ɗ, 3ŀ/Ñ$ 1 ị@2$?という3つのlinkからなる2,1,1-chainでした。評価規則に従うと `, 2Ŀi1Ɗ 3ŀ/Ñ$ 1 ị@2$?`(l)は `3ŀ/Ñ$ 1 ị@2$?`(l `,` `2Ŀi1Ɗ`(l))と評価されます。

まず2Ŀi1Ɗですが、これは2Ŀ, i, 1という3つのlinkをƊによってまとめたインライン1,2,0-monadic chainです。2Ŀというのは「上から2行目で定義されたlinkをmonadic linkとして参照する」という意味のquickです。実は直前直後ではなく任意の位置のlinkを参照できるのです。とても嬉しいですね。 `2Ŀi1Ɗ`(l)の評価は、まず文字列lが2Ŀによって[1,0,0,0]のようなリストに変換されます。その後i1によって、リストに含まれる1の位置を探しています。iはリストに与えられた値が含まれていればそのインデックスを返し、含まれていなければ0を返します。

ということは、l `,` `2Ŀi1Ɗ`(l)は文字列lに、その文字列が"maerd", "remaerd", "esare", "resare"のうちどれをprefixとして持つのか（あるいはどれも持たないのか）という情報を付与したペアに変換していることになります。例えばlが"maerdesare"ならばここまでの結果は["maerdesare", 1]になります。

最後の3ŀ/Ñ$ 1 ị@2$?ですが、これは?quickによって作られた条件分岐monadです。条件部分はị@2$、すなわち「リストの2番目の要素を取り出す」というmonadです。これは先ほど作ったリストの2要素目が0かどうか、すなわち文字列全体が4種類のいずれかをprefixとして持つかどうかを判定していることになります。

この条件を満たすならば、このリストは3ŀ/Ñ$で評価されます。これはリストの1要素目と2要素目を左辺と右辺として3ŀ、すなわち3番目のlinkで評価し、その結果をさらにÑで評価するものです。つまり、3番目のlinkで文字列の既知のprefixを消したあと、1つ下のlinkに相互再帰するということです。

一方、条件を満たさないときに評価されるのは1です。つまり、文字列がいずれもprefixとして持たないことが判明した場合は1を返して終了です。

Ç 2L?

さて、相互再帰先はこれです。これもやはり文字列を入力として受け取るmonadic linkです。これは、与えられた文字列が空文字列なら2を返し、そうでなければひとつ上のlinkに相互再帰するだけです。

つまり、一つ上のlinkとこのlinkで相互再帰することによって、文字列が空になるまでループする処理を実現しています。この条件分岐で文字列が空になった場合は問題の条件を満たす（4種類の文字列のいずれかを繰り返し取り除くことで文字列を空にできた）ことが分かったので2を返します。まだ文字列が残っているなら次のprefixを探すために上のlinkに戻るのです。

ɠU Ç ị“NO“YES”

これがプログラムのmain部分ですが、やっていることは難しくありません。ɠで標準入力から1行読み、Uでリストを反転させます。文字列もリストなので反転できるのでしたね。Çでメインの計算を行い文字列を1か2に変換します。あとはそれをị“NO“YES”で"NO"か"YES"に変換して終わりです。

ABC 086 C - Traveling

いよいよ10問目ですね。なんとか最後まで行けそうです。

これは2次元平面上の旅行プラン（時刻と位置の組たち）が与えられるので、その旅行プランが可能かどうかを判定する問題です。入力例はこんな感じです。

2
3 1 2
6 1 1

この場合旅行プランは2行あり、1行目は時刻3に位置(1, 2)にいるという意味、2行目は時刻6に位置(1, 1)にいるという意味です。旅行の初期状態は時刻0で位置(0, 0)にいて時刻位置単位ごとに横（X軸方向）か縦（Y軸方向）に距離1だけ動くことができます。

解説は調べればいくらでも出てくるので適宜補完していただきたいですが、現在位置(x, y)に対してx+yの偶奇が時刻1ごとに必ず入れ替わるのがポイントです。また、時刻2を消費することでその場に留まることができるのもポイントです。よって、時間tをかけて点1から点2に行かないといけないとき、そのプランが可能かどうかは「2点のマンハッタン距離がt以下である」ことと「tの偶奇と2点間のx+yの偶奇の差が等しい」ことの2つを確かめれば判定できます。

というわけで回答コードはこれです。

ị@1 ị@ ¹ ạ ị@2ị@ɗ
,µ ç2 + ç3$
,1ŀ1ɗ  Ḃ=Ḃ}ɗ 2ŀ
,1ŀ1‘ʋ > 2ŀ
ƓR µɠḲVµ€ ;@[[0,0,0]] 3ŀaçɗ2\ Ạ ị“Yes“No”

上から順に2,0,2,1,2,2-chain、2,1-chain、2,2,2-chain、2,2,2-chain、0,1,1,2,0,1,1,2,0-chainです。

今回もだいぶ整理されたコードが書けました。今回は旅行プランひとつを[3,1,2]のように[t,x,y]の形のリストで取り回すことにします。

ざっくりめに解説していきますが、まず1行目のị@1 ị@ ¹ ạ ị@2ị@ɗはリストlと数値rを受け取って「l[1][r]とl[2][r]の差の絶対値」を返すdyadic linkです。これは以降のlinkでよく使うので抜き出しました。ạが差の絶対値を計算してくれる便利なdyadです。

2行目の,µ ç2 + ç3$は、2つのリストlとrを受け取って「l[2]とr[2]の差の絶対値」と「l[3]とr[3]の差の絶対値」の和を返すdyadic linkです。ここでlとrがそれぞれ[t,x,y]の形のリストだったとすると、これは2点間のマンハッタン距離を計算していることになります。

3行目の,1ŀ1ɗ Ḃ=Ḃ}ɗ 2ŀは、2つのリストlとrを受け取って「l[1]とr[1]の差の絶対値」と「lとrのマンハッタン距離」の偶奇が等しいかどうかを判定するdyadic linkです。lとrが[t,x,y]の形なので「l[1]とr[1]の差の絶対値」というのはlからrへの経過時刻ですから、このdyadic linkで上記の解説にある「tの偶奇と2点間のx+yの偶奇の差が等しい」の部分を判定していることになります。

4行目の,1ŀ1‘ʋ > 2ŀはもう半分の条件、すなわち経過時刻tに対して「2点のマンハッタン距離がt以下である」ことを判定しています。

そして5行目がプログラムのmain linkです。ƓR µɠḲVµ€の部分までが入力を読む処理で、これで[[3,1,2],[6,1,1]]のような旅行プランのリストが手に入ります。

次の;@[[0,0,0]]の部分は、このリストの先頭に[0,0,0]を付け足しています。これが初期状態のつもりです。

次の3ŀaçɗ2\が処理の本体です。\が特徴的なquickで、その前の2と合わせると「リストの全ての隣り合った要素同士にdyadを適用して新しいリストを作る」という意味のmonadになります。これにより、隣り合った全ての旅行プランにたいしてその移動が可能かどうかの判定を行っています。

判定部分の3ŀaçɗは、3ŀ（3行目のlink）とç（4行目のリンク）の結果をa（logical and）した結果を返すdyadです。ここで上述の2つの判定を行い、その結果を詰めたリストを生成しています。

これで、全ての旅行プランが可能なら[1,1,1]のように全てが1のリストが手に入り、途中でだめなところがあれば[1,0,1]のようになります。

問題は全ての旅行プランが可能かどうか判定することだったので、リストが全て1かどうか判定しなければなりません。それを行うのがẠで、リストの中身が全て真なら1を、そうでなければ0を返してくれます。あとは最後のị“Yes“No”でこれを文字列に変換して終了です。

まとめ

ということで、無事にJellyでAtCoderの精選過去問10問を解くことができました。コードゴルフ言語を名乗っているだけあって、どの回答もそこそこ短いプログラムで書くことができました。

今回は筆者のコードゴルフ力が足りないため最短にはほど遠いはずです。興味がある方はプログラムのさらなる最適化に挑戦してみてください。

Jellyによるプログラミングは常にatom一覧・quick一覧・そしてchainの評価規則とのにらめっこです。これらを使いこなすのは簡単なことではありませんが、きれいな解法を思いついたときの達成感・爽快感はやみつきになります。

実際、問題の解法はどれもループを回せば大概なんとかなるものでしたが、Jellyではそれでも各問ごとに違った考え方が要求されました。

頭の体操と思って皆さんもぜひJellyによるプログラミングに挑戦してみてましょう。

• Jellyチュートリアル（インタプリタもここから手に入ります）
• Jelly - Try It Online Playgroundです。手軽に試したいときに。

おまけ：1から100の偶数の和

少し前に1から100までの偶数の和を求めるプログラムがTwitterなどで話題になりましたが、もちろんJellyでも書けます（Twitterに載せたやつの再掲です）。

³RŒœṪS