秋分コンテスト Commentary (JAPLJ side)

秋分コンテスト

解説・コメント (writer: JAPLJ の問題)

D: ゴーストバスターズ

ちょっとだけ問題文が長い以外は、まったく普通の競プロの問題ですね。通常よりごく僅かに長いだけの問題文をよく読んで解けばいいと思います。

問題自体は拡張ダイクストラとか bit DP の練習問題みたいなものなので、特に解説しません。

他の問題でも大量の日本語を書く必要があった (必要は、ないだろ) ため、推敲作業などを全く行っておらず、勢いだけで書かれた一万文字となっています。内容や体裁などに色々と粗があると思いますが、ご容赦下さい。

E: Soup, Abandoned

本来不要な日本語をたくさん書きました。

問題としては、過去に出題した「ウミガメのスープを行って問題内容を当てる」やつのリベンジです。当時は全て手動で質問への対応を行って本当の地獄を見たので、ARTIFICIAL INTELLIGENCE に質問応答を任せることで楽をしようという発想でした。

結果としては、質問対応でコンテスト中に地獄を見るか、インテリジェントな bot を作り上げるためにコンテスト準備中に地獄を見るかの違いでした。

正直、まともな問題内容を bot 相手に特定するのはかなり無理があると分かったので、問題自体は OEIS の特定の数列を出力させるだけのシンプルなものを選びました。それでも融通の利かないスープ相手に内容を訊き出すのは結構大変だと思います。

スープ解説としては、こいつは微妙にステートを持っているので (たとえば問題文について話していると、次の発言が問題文に関するものと解釈されやすくなる、など)、問題文について質問したいときはまず問題文ステートに確実に入るようにしておくと進みやすいです。あとは「数列」「OEIS」「秋分」など特定のキーワードに辿り着ければ問題が見えてくると思います。

H: 手紙 1

本来不要な日本語を書きました。

さて、画像を見ると、知っている人はこれが変体仮名であるとすぐに気づくかもしれません。現代でもたとえば蕎麦屋の暖簾や看板に使われていることがあり、今回の画像にも蕎麦屋で見かける「そ」が入っています。

変体仮名であると分かれば、あとは読むだけです。調べれば一覧が色々と出てくるので、それを使って頑張りましょう。整数列が与えられ、隣り合う二要素が互いに素なのが何箇所あるかを数える問題になります。

I: 手紙 2

本来不要な日本語を書きました。E, H, I は共通の世界観なのかもしれません。秋分を、大事にしよう。

問題文が万葉仮名で書かれています。これも調べて頑張って読んで下さい。文字列が与えられ、それを好きな箇所でふたつに切って最長共通部分列の長さを求めて、すべての箇所についてその和を計算する問題になります。

J: J

J 言語を読み解いて同じプログラムを作る問題……のようでいて、実はほとんど J 言語を読む必要はありません。手元に処理系を入れて動作を見てみれば、何のプログラムか察せる課題が結構あります。

以下、各課題の簡単な説明です。

  1. Anagram Index ですね。順列をソートしたとき何番目に来るかを答えます。
  2. 引き算 a-b-c-d-... をやっていきます。ただし J 言語は全ての演算子が右結合なので a-(b-(c-(d-...))) を計算することになります。
  3. 調べると 32-bit CRC の計算であることが分かります。やりましょう。
  4. 適当であまり意味のないプログラムです。手元で動作を確かめて再現することを想定しています。プログラムを要素ごとに分解して動かしてみましょう。
  5. f1, f2, f3 と三種の操作を x に行っているので、それぞれの動作を見てみましょう。f1 は (x[i], i) 要素だけが 1 で他が 0 の行列を作ります。f2, f3 はそれぞれ反射閉包と推移閉包をとります。つまり、三種合わせて、辺 (x[i], i) があるグラフでの到達関係を計算しています。あとは、ある頂点から到達可能な全ての頂点に対応する y の値の総和を求めるだけです。
  6. 今度は操作が多すぎるし組み合わせ方も複雑なので、とても読めません。手元で動作を確かめることを想定しています。実は f1 から f9 は FFT を使った畳み込みを実装しているので、x と y の和と積による畳み込みを計算して下さい。
  7. 実行するだけに見えますが、時間がかかりすぎて終わりません。f の正体は特に意味のない複雑な再帰関数です。$: が再帰を意味しているので、再帰関数であることはすぐに分かります。また、引数が整数ひとつのようなのでメモ化すれば早くなりそうです。f の定義の末尾に M. とつけるとメモ化してくれるので、これで十分高速になります。
  8. Dixon's identity による 3F2 (hypergeometric function) の計算について、条件が満たされているときにその値を求めるプログラムであることが頑張って読むと分かります。なので Dixon's identity に従って計算をして下さい。複素数に対するガンマ関数を計算する必要があり、標準ライブラリでは出来ないと思うので Lanczos approximation とかを使うとよいです。

W: 嗚呼、恍恍惚惚　曠古、杲杲煌煌、兀兀甲骨

この問題に言及する時は「ああこうこうこつこつこうここうこうこうこうこつこつこうこつ」と正しく呼んで下さい。

最近漢字源を買って面白かったので作りました。出題しなかったものにも面白いものが結構あって、いくらでも甲骨クイズができそうですね。

この問題での答えは「呂官不糸眉各上少行阜歩禽癸」です。

X: Legacy A+B Problem

A+B を計算するだけです。が、どうも出力を 7 セグメントで出さないといけないらしいです。さらに Output は "IN A SINGLE LINE"、つまり一行で出力しないといけないらしいです。

一行で 7 セグを表現するなんて、無理では？困ったなあ……。

ところで、2020 年 3 月にリリースされた Unicode 13.0 に Symbols For Legacy Computing というのがあり、ここで 7 セグ表現での 0 から 9 の数字が含まれていますね。というわけでこれで出力して下さい。

Unicode 13.0 の Symbols For Legacy Computing にまともに対応しているフォントは 2020 年の秋分現在ほとんどないので、多分誰も表示はできないと思います。なので親切心からサンプル出力を画像化しておきました。

`: Richard ⅭⅭⅭⅭⅭⅠↃↃↃↃↃⅭⅭⅭⅭⅭⅠↃↃↃↃↃↈↈⅭⅯⅩⅩⅡ

翻訳と日本語業が大変でした。

問題を見てみると、戯曲が書かれており、どうやらシェイクスピアの「リチャード二世」を下敷きにしていることが分かります。

ところで、Shakespeare という、あたかもシェイクスピアの戯曲であるかのようにプログラムが書けるプログラミング言語があります。この「リチャード二千二十万九百二十二世」(を英語にしたもの) が Shakespeare で書かれたプログラムだと思ったときの動作をそのまま提出すれば通ります。

感想 (writer: JAPLJ でないもの、絵しりとりなど)

  • A: Introduction to ESP Returns　過去のお誕生日情報をよく復習しているかという問題。これを A に置くの本当に優しくないですね。
  • B: Self Introduction　KCS が秋分のために改造されて、output checker でユーザ情報がとれるようになって作られた問題。シンプルかつ新しくていいと思います。
  • C: ピクトセンス　たのしかったです。ワールドカップがお気に入り。
  • F: THE EMPTY　KCS でも EMPTY シリーズが実施されて嬉しい。通知欄という新要素なのもよい。
  • G: くそなぞなぞ　簡単なやつはともかく、難しい方はけっこう大変。
  • K: Integer Choice　こういうのは 1 問だけ (かつ配点 100) ぐらいがちょうど面白くていいのかな。
  • L: Sqrt　秋分癒やし枠。どうしても重くなりがちなコンテストなので、清涼剤は嬉しいね。
  • M: I like this　純エスパー枠。こういうのも 1 問ぐらいがちょうどよさそう。出力が三通りなので、エスパーするより提出して入力判別したほうが手っ取り早いと思います。
  • N: |n|　秋分癒やし枠。でも思ってたほど瞬殺されまくりではなかったですね。
  • O: 沖縄　シンプルに面白い。正規表現を使うといいですよ (条件を満たす文字列を全列挙すると、大変なので)。
  • P: Bus Travel　tester として普通に解きましたが、面白かった。一旦正の点が取れるところまでいけば、あとはどこが間違っているか調べながら直していけるので、最初に埋めるまでが大変ですね。
  • Q: Tozangya ソーシャルディスタンス確保版　こういうのは画像から適切な検索ワードを探る問題になりますね。ラウンドアバウトとかは比較的すぐわかったけど、難易度差もかなり人によりそう。
  • R: 私は秋分を知る。　リアルタイム性の高さゆえ、内容について感想を言っている暇がありません。
  • S: Cat nuke' Challenge　KCS 改造で output checker から提出ソースがとれるようになったので、提出ソース制限系。回避は容易な方ですね。
  • T: |あ|み|だ|く|じ|　AdBlock パートはともかく、肝心のあみだくじをどうするか……。思考停止手作業書き起こしで 10 分ぐらいでした。
  • U: 帰ってきた Picture　かなり難しいと思います。元はもっと難しい画像だったとか。
  • V: String Achievement　満点は無理があるけど、試行錯誤を繰り返す系で楽しみが長いですね。
  • Y: A/B Problem　提出ソース制限系 2。これも回避は容易な方。
  • Z: Chess　testing 中に挑戦する暇がなかった……。後でやる。
  • [: Cheat　KCS 改造による最大収穫。本当に面白すぎる。
  • : Date Formatter　"""数"""で表された日付。
  • ]: 数列クイズ　これもまあまあ癒やし枠。題材は、へ～となりました。
  • ^: 🐿　提出ソース制限系 3。これの回避も大変ではないけどちょっと知識が要る。
  • _: Echo　ゴーストバスターズに並ぶ、秋分中でも極めてまともな問題のひとつ。この問題のためにセット採点情報が出るように KCS が改良されたとか。
  • a: Shiritori 2020'　「ンコ文字」を書いてしまい、すみません。いや、直前の絵が「海面」にしか解釈できなかったんだよね、これは真剣に。
  • b: 【クエストキーワード提出用問題】Autumnal Equinox Quest　お馴染みですね。ほとんどの人はしりとりとスープのものをとっていたようです。それ以外のクエストを引き当てた人はすごい！