AtCoderに登録したら解くべき精選過去問10を漢文プログラミング言語「文言（Wenyan）」で解いてみた

はじめに

本記事は 文言 wenyan-lang アドベントカレンダー 2020 20日目の記事です。
そして誰もやってなさそうな言語で競プロをやるシリーズ第7弾¹、AtCoder Beginners Selection の問題²を、漢文プログラミング言語「文言」で解いてみた記事となります。

なお、詳しい文法の解説をしているとAdCの期限に間に合わなそうなのでまたの機会にして大まかな解法の説明だけにとどめます。

対象は何かしら他の言語でAtCoder の200〜300点程度の難易度の問題が理解できる人くらいを想定しています。

文言とは

文言（Wenyan）は漢文風に記述できるプログラミング言語です。
基本的にaltJSとして動作しますが、Pyhton、Rubyなどにトランスパイルできます。
オンラインエディタが公開されており、気軽に実行することができます。

解法

本記事では標準出入力や文字列↔数値の変換、splitなどの操作をコンソールアプリ用ライブラリとして『控制台應用』というパッケージにまとめ、使用しています。
内部実装は別の機会にまとめますが

• 「輸入」で標準入力をすべて受け取る
• 「分裂」で第2引数の文字でsplitする
• 「刪除空白」で文字列の前後の空白文字を削除する
• 「解析為整數」で文字列を数値にパースする
• 「轉換為字符串」で数値を文字列に変換する
• 「排序」で配列をソートする（現在の公式の配列ライブラリ列經をそのまま使うと辞書順ソートになってしまう³）

という機能となっています。

それぞれの解答は手元(Ubuntu20.04LTS on WSL2, WENYAN LANG 文言 Compiler v0.3.4）で実行し動作確認をした後、JavaScriptにコンパイルしてAtCoderに提出しています。

0. practice contest A - Welcome to AtCoder

※当然QiitaのMarkdownではシンタックスハイライトが効かないのでコードは公式オンラインエディタの画像を貼付します。
ソースコードはGitHub https://github.com/Yukishita26/abs-solve/tree/master/Wenyan/source にアップロードしてあるので合わせてご利用ください。

入力が「輸入」で全行まとめて取り込まれる⁴ので、それを改行で分割(l 4)、
1行目を数字に変換(l 5)、
2行目は空白で分割してそれぞれ数字に変換(l 6-8)、
3つの文字の和を取って結果を文字列に変換(l 9)、
3行目とともに出力(l 10)
という流れです。

計算結果を其で再利用できるので、これをうまく使えるかがスマートに書けるかどうかの分かれ目になってくる気がします。

提出結果 AC / 1893 Byte / 57 ms / 29452 KB
https://atcoder.jp/contests/abs/submissions/18839381

1. ABC 086 A - Product

入力から最後の改行を削除、空白で分割、1番目と2番目を数値に変換してそれぞれ「甲」``「乙」とします。
この積を2で割った余り⁵が0なら『Even』、そうでなければ『Odd』を出力します。

条件分岐は若<条件式>者 …… 也のようにします。else節がある場合は若<条件式>者 …… 若非 …… 也となります。
else ifの構文は用意されていないのでどんどんネストさせていくことになります。

提出結果 AC / 1755 Byte / 68 ms / 29604 KB
https://atcoder.jp/contests/abs/submissions/18839436

2. ABC 081 A - Placing Marbles

3桁入力だと決まっているので1,2,3桁目がそれぞれ文字『1』と一致するかどうか判定し、一致するなら「回答」を1つ増やすことで「1」の数を数えます。

文字列や配列のインデックスアクセスは夫<オブジェクト>之<インデックス>の形で行います。
1-indexedなことに注意です。

なお、物オブジェクト（JSの「Object」に相当。Hash、Mapとして使える）は同様に夫<オブジェクト>之<キー>のようにアクセスできます。

提出結果 AC / 1824 Byte / 60 ms / 29500 KB
https://atcoder.jp/contests/abs/submissions/18839439

3. ABC 081 B - Shift Only

まず入力の1行目を数値に変換して「甲」に、2行目を空白で分割し、それぞれを数値に変換しながら配列「編號順序」にpushしていくことで入力配列を受け取ります。
その後、配列をすべて2で割っていき、「すべてが2で割り切れる」限りループします。これが続かなくなる回数が答えです。

無限ループは恆為是 …… 云云、
回数指定のループは為是「甲」遍 …… 云云（ループインデックスにはアクセスできないのでカウンタを用意する必要がある）、
foreachは凡<コンテナ>中之<key> …… 云云
の形で使用します。

提出結果 AC / 2090 Byte / 198 ms / 29580 KB
https://atcoder.jp/contests/abs/submissions/18856518

4. ABC 087 B - Coins

4行の入力を「甲」``「乙」``「丙」``「目標」に数値に変換して受け取りますが、甲、乙、丙は1を加えておきます。
500円、100円、50円が0～A、0～B、0～C枚のすべての場合を調べるのでループ回数はそれぞれA+1、B+1、C+1となるためです。
カッコ等で計算順序を変えたりできないため煩雑ですが金額の和が目標と等しくなる度に「回答」を1ずつ増やしていけば求める場合の数がわかります。

提出結果 AC / 2544 Byte / 136 ms / 32432 KB
https://atcoder.jp/contests/abs/submissions/18857532

5. ABC 083 B - Some Sums

VSCode に文言の拡張があるのに気づきました。こっちのほうが文字列や数値も色分けされていて若干見やすい気がするのでここからこっちを使用することにします。

「各位の桁の和」を求める関数を定義した後、1～Nで各位の桁の和がA以上B以下となる数値を「回答」に足していき答えを求めます。

関数定義は

吾有一術。名之曰「<関数名>」。欲行是術。必先得<引数の数><引数の型>。曰「<引数名>」。 …… 乃行是術曰。
    …… 
    乃得<戻り値>。
是謂「<関数名(再掲)>」之術也。

の形になります。

if文中で条件の論理和/積を取るには 若<条件1>(中有陽乎/中無陰乎)<条件2>者 …… 也。とすればよいようです。
というのも公式Wikiには真偽値同士の演算夫「甲」「乙」中有陽乎。の形しか記載されておらず、何故この場合だと中置にすると動くのかはよくわかりません。

提出結果 AC / 2445 Byte / 64 ms / 33096 KB
https://atcoder.jp/contests/abs/submissions/18857909

6. ABC 088 B - Card Game for Two

3.と同様に配列にpushしていくことで数列を受け取った後、ソートして反転させます。
反転には公式ライブラリの『列經』パッケージ「倒序」を使用していますが、同「排序」は上述の通り辞書順ソートになってしまうため自作ライブラリのもの（JavaScriptのx.sort((a,b)=>a-b)を呼び出している）を使用しています。
大きい順に奇数番目（1-indexedに注意）がアリス（愛麗絲）、偶数番目がボブ（鮑伯）が取るようにしていけば最適の場合になります。

提出結果 AC / 4637 Byte / 55 ms / 29640 KB
https://atcoder.jp/contests/abs/submissions/18858292

7. ABC 085 B - Kagami Mochi

物型は{key:value}の組を保持できます。keyが一意になることを利用して重複を除いた「餅」の数を数えて答えになります。

物型の操作は『格物』パッケージを使用します。「置物」で値の割り当て、「取物」で値を取得します。
「列物之端」でkeyの配列を取得できるので、凡<keys>中之「key」。でkeyを甞めてループの回った回数を数えて答えとなります。

提出結果 AC / 2733 Byte / 56 ms / 29752 KB
https://atcoder.jp/contests/abs/submissions/18858859

8. ABC 085 C - Otoshidama

4.と同様ですが、一番内側のループはループで全部調べなくても紙幣の数がNであることから計算できるので計算量をへらすことができますね。

ローカルで実行した際は2秒以上かかっていた気がしますが、JSで提出したらかなり速かったです。
JS上でさらにインタプリタ実行していたらそりゃ遅いですよね……

提出結果 AC / 2400 Byte / 64 ms / 32528 KB
https://atcoder.jp/contests/abs/submissions/18876786

9. ABC 049 C - Daydream

頭から調べていくとdreamerを使うべきかdreamで切ってeraserを当てるべきか、などという迷いが発生して調べきれなくなってしまいますが、逆順にするとmaerd,remaerd,esare,resareはそれぞれprefixなので貪欲法で調べていって判定できます。

else ifがないおかげで条件判定を先に計算してから条件分岐をする、などとして無駄に長くなってしまいましたが各々と部分文字列が一致するかを調べていくだけです。

提出結果 AC / 5815 Byte / 88 ms / 38768 KB
https://atcoder.jp/contests/abs/submissions/18897133

10. ABC 086 C - Traveling

一手前の位置から現在地まで到達できるか、を判定します。
これには時間的に間に合うかどうか（距離<時間差）と、時間差-距離が偶数（偶数だけ時間が余ればジグザグして時間を潰せばいい）という条件を満たせばよいです。

提出結果 AC / 50667 Byte / 136 ms / 47720 KB
https://atcoder.jp/contests/abs/submissions/18894777

あとがき

如何せん日本語資料がまだ少ないので貧弱な英語力で公式ドキュメントを頑張って読まなければいけなかったのですが、公式も工事中なところが多く、結局サンプルとJavaScriptへのコンパイル結果を見比べて実験していくことでなんとか11問解くことができました。
変数がスタックに積まれていって関数適用で呼び出されていくという仕様なんかは日本語プログラミング言語「プロデル」⁶とも似ていてちょっとおもしろかったです。自然言語っぽくするとこうなるんですかね？
9.で使った配列のスライスが実は閉区間指定だったとか1-indexedなのを忘れてバグらせたりとかいろいろと大変でした。
いつか改めて日本語版CheatSheetをちゃんと書きたいと思います。
というか公式Wikiが歯抜けすぎるので埋めてしまいたいんですがこれメンテ続いてるんでしょうかね。4ヶ月前でCodeの更新止まってますが……

1. AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～(@drken さん) にて紹介されている過去問題。現在は常設コンテストAtCoder Begginers Selectionとして公式にまとめられている。 ↩

2. 過去の記事は https://github.com/Yukishita26/abs-solve にまとめてあります。 ↩

3. 公式WikiにはArray.sortと等価，と書いてあるが内部実装はWenyanでのマージソート（？）。しかし比較はJSに従うので辞書順になってしまう。 ↩

4. 行ごとではないのは内部実装がJavaScriptだからです。JSの標準入力は面倒……(参考: Node.jsの標準入力と) ↩

5. 中身がJSなので余り大きい数字だと整数演算でも誤差が発生してしまうので先に剰余を取ったほうが安全ですがこの制約なら問題はありません。 ↩

6. 以前に本記事のプロデル版 AtCoderに登録したら解くべき精選過去問10をプロデルで解いてみた も書いたので見てみてください。 ↩