秋分コンテスト 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 から f9FFT を使った畳み込みを実装しているので、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 お馴染みですね。ほとんどの人はしりとりとスープのものをとっていたようです。それ以外のクエストを引き当てた人はすごい!

Xmas Contest 2019 (JAPLJ side)

おはようございます、JAPLJ です。普段は色々と音楽制作やっています。(隙あらば宣伝)


Xmas Contest 2019 やりました!

ご参加いただいた皆様、ありがとうございます!コンテストはお楽しみいただけたでしょうか。

今年は昨年と同じ面子 (hos, japlj, snuke) での開催となりました。昨年は軽い構築問をひとつ置いたぐらいだったので、今年はもう少し骨のある (意味深) 問題を作りたいなと思っていましたが、さて実際はどうなったかな……。

コンテスト全体としては、提案された問題が何やら設定や問題文の大部分を共有した複数問に分割できることが多く、気がついたら 12 問という過去最大規模になっていました。誰にも解かれないような問題もなく、かつ幅広く取り組み甲斐のあるセットになったのではと自負しています。

この記事では自分が原案を担当した問題の解説(?)をしていきます。

A: Signboard 1

ここに、A問題のすべてが、ある

※「すべて」と言いましたが、インターネットのデータ奔流による混乱や何らかの高次存在の介入などにより収集漏れがあるかもしれません、ご了承ください (連絡を貰えれば追加します)。

少しはちゃんと話をすると、人力 : プログラミング : ツール活用 のバランスをどう取るか?というところが (主に、観戦側の!) 面白味だったと思います。

とはいえ、特にチーム参加で人力を割くコストが相対的に低い場合は、どうしても人力寄りにするのが結局コスパがよくなりそうです。ただ、手作業をする場合でも

  • mspaint や GIMP などのペイントツール
  • PowePoint や Keynote などのプレゼンテーションソフト (画像単位での移動が楽)
  • Finder やエクスプローラーなどのファイルマネージャ (ファイル名の確認が楽)
  • 紙とハサミ (プリンタさえ手近にあれば最も楽?)

など多様なツールがありうるので (感想戦が) 面白くなりますね。

writer は、紙片の端どうしのマッチ度を見るだけで局所的に正しい隣接関係はある程度得られることを利用して、プログラムに適宜手動でヒントを与えつつ解きました。

L: Signboard 2

A とつながっている問題なので、先にこちらの解説を……。

紙に書かれた単語のみを使ってスケルトンを完成させる問題です。言ってしまえばそれだけなのですが、ポイントとしては

  • 紙片をちゃんと大きな紙に復元してから単語リストを拾う必要がある (一つの単語が複数の紙片に跨っていることがある)
  • 紙片を復元するときは A 問題の解答が使えるが、裏面なので左右を反転させて並べる必要がある
  • 紙に書かれた単語 (裏面に書かれた単語、ではない) が単語リストになるので、表に描かれている xmas, contest も当然単語リストに入る

あたりです。

不要な単語たちの数はそこまで多くないので、手動でも十分にスケルトンを解くことは可能です。ただ、肝心の単語候補を拾う部分にひねりがあるので、個人的にはスケルトンソルバーはプログラムで書いておいたほうが楽かなと思っています (適当な全探索で十分高速です)。

ケルトンの解答自体は以下のようになります。

f:id:JAPLJ:20191227001853p:plain

Xmas Contest 大好き Xmas Contest フリークの方ならお気づきかもしれませんが、解答に使われている単語はXmas Contest 2011の (Practice を除く) 問題名に使われている単語から取られています (正確には、それに加えて xmas と contest)。

Xmas Contest 好き好き勢であれば、見覚えのある単語たちだな~という印象からいくつかヒントを得られたかもしれません (問題名の単語だけだと枠数に足りないので、xmas/contest を使うことを着想できるなど)。

B: Set of Integers

加算は可換ですが、減算は非可換なので、一見すると |S| > |D| にするのは無茶な要件に見えます。

Xmas Contest だし……思わず、|S| > |D| のケースは存在しない!としたくなるところですが、実は存在します。というのがこの問題でした。

とりあえず先に |S| < |D| と |S| = |D| のケースを片付けておきましょう。

|S| < |D| のケース

まず、N = 1, 2 の場合は |S| < |D| となるような X は存在しません。逆にそうでなければ存在します。

というか、加算が可換で減算が非可換なので、大抵の場合 |S| < |D| となります。

どういう作り方をしてもいいですが、X = {0, 2, 3, 4, ..., n} が分かりやすい例でしょうか。

|S| = |D| のケース

これも案外すぐに見つかります。分かりやすいのは X = {0, 1, 2, ..., n-1} だと思います。

一般に、X の要素が等差数列をなす場合も |S| = |D| になります。

さらに一般に、X が対称なとき (ある a が存在して、x ∈ X なら必ず a-x ∈ X であるとき) も |S| = |D| となります。

|S| > |D| のケース

さて、本番です。先にネタばらしをしておくと、このような条件を満たす集合 X は MSTD set (More Sums Than Differences set) と呼ばれており、探せば多くの論文が出てきます。この名前を知らなくても、たとえば "set of sums and differences" などで Google 検索すると MSTD set に関する文献が多くヒットします。

これらの文献を色々と眺めると、N ≦ 7 では解なし、N ≧ 8 では構成可能 であることがわかります。更に、実際に簡潔な構成法を紹介している文献も出てくるので、それだけで解けます。

コンテスト中に解くだけならそれだけ分かっていれば十分なのですが、ここではもう少し詳しく見ていくことにしましょう……。


といいつつ、N ≦ 7 で解なしであることについては深くは触れません。Hegarty (2007) が次の定理を示しています:

Theorem. 大きさ 7 の MSTD set は存在しない。さらに、大きさ 8 の MSTD set は線形変換によって移りあうものを同一視すれば A_1 = {0, 2, 3, 4, 7, 11, 12, 14} が唯一である。

論文を見てみると分かりますが、証明はずいぶんマッシヴです。細かく追うのは大変なので、ここは先人を信じておくことにしましょう。

コンテスト中には (文献を発見しなかった場合は) 小さい方から探索をぶん回していけばどうも無さそうであることが分かり、あとはもう提出してみるしかないでしょうか。


MSTD set の構成方法も調べると色々と出てきますが、ここでは実際にプログラムで実装しやすくシンプルな Nathanson (2007) による方法を紹介します。

X が対称である場合 (また特に等差数列をなす場合) に |S| = |D| であることを先程見ました。ふつう |S| < |D| となるものを |S| = |D| まで持ってこられるということは、これは非常に惜しいです。対称な集合を少しいじることで |S| > |D| にできないか?ということを考えます。

ところで、最小の MSTD set は N = 8 のときの A_1 = {0, 2, 3, 4, 7, 11, 12, 14} でした。よく見るとこれはとても対称に近いです。具体的には 4 さえ抜けば対称 になっています。

A_1 から 4 を抜いたものを観察すると、 0 2 | 3 7 11 | 12 14 と、差が 2 の部分と 4 の部分に分けることができます。たとえばこれを次のように伸ばすとどうなるでしょうか?

  • A* = {0, 2} ∪ {3, 7, 11, ..., 4k-1} ∪ {4k, 4k+2}

A* は対称なので、この状態では |S| = |D| です。ここに A_1 のときと同様 4 を加えると……?

  • A = A* ∪ {4}

まず、|S| はどう変わるか考えると、4 + 4 = 8 は A* の要素だけでは作ることができません。なので少なくとも |S| は大きくなる ことが分かります。

では、|D| はどうなるでしょうか? A* の各要素から 4 を引いたものたちを考えてみると

  • 0 - 4 = -4 は公差 4 の部分で作れます
  • 2 - 4 = -2 は 0 - 2 で作れます
  • 3 - 4 = -1 は 2 - 3 で作れます
  • それ以降の (4m-1)-4 たちは、そもそも自身が A* に入っているので (4m-1)-4 - 0 で作れます
  • 4k - 4 は (4k-1) - 3 で作れます
  • (4k+2) - 4 は 4k - 2 で作れます

以上より、|D| は変わりません。すなわち A は MSTD set です。お疲れ様でした。


実際には、他にも様々な構成法があると思います。たとえば、X が MSTD set のとき、十分大きい整数 M を持ってくると

  • { a*M + b | a, b ∈ X }

も MSTD set になります。

ある程度小さい MSTD set であればうまく探索したり乱択すると手に入れられるので、それらをこの方法で組み合わせたりいじったりして、より大きい MSTD set を得ることもできます。


さて、B 問題の解説は以上です。が、MSTD set 自体は他にも色々と面白いことが知られています。たとえば Iyer, Lazarev, Miller, Zhang らによるサーベイ論文 を参照してみてください。

一見すると全然存在しないように思える (そして実際コンテスト中にも多くの方が構成に苦労した) MSTD set ですが、実は {0, 1, ..., n-1} の 2n 通りの subset のうち、MSTD である割合が n → ∞ で正である など、意外な結果もあります。

Xmas Contest 2018 ひとこと感想 (ネタバレ有り)

Xmas Contest 2018 ご参加ありがとうございました!

各問題についてひとことずつ重大なネタバレをしていこうと思います (ちゃんとした文章を書くには睡眠時間が足りなさすぎる)。

ちゃんとした文章は……、書くかもしれないし書かないかもしれません。







…(ネタバレ回避用余白)…







…(ネタバレ回避用余白)…







…(ネタバレ回避用余白)…








…(ネタバレ回避用余白)…








  • A: いいよねこれ。手作業してもいいし、解答キー生成スクリプト (Javascript) を読むとグラフが埋め込んであるのでそれを使って探索してもいい。
  • B: 思ったより解かれなかった感
  • C: WA を出さずに書くのは結構たいへん……ですが、けっこう素直に実装すれば一番取りこぼしがなくて WA を出しづらいみたいなところがあって良い。
  • D: びっくりするほど解かれなかった……。賢ければちゃんと構成できる (hogloid すげー) んですが、賢くなくても実は多少頑張って探索すれば爆速です。
  • E: これはびっくりです。
  • F: 唯一の原案。軽めの構成枠がほしいなと思って。
  • G: 超締切間際にこういうのが生えてくるのすごいよね。
  • H: これも思ったより難しかったっぽい (難易度推定無理すぎる〜)
  • I: 想定解はなんかやばかったです。人々が気合の入れた解をたくさん書いて (通して) くれてなんかいい問題っぽくなってて面白い。
  • J: 日本語実はそんな大変じゃなくて (実装は多少めんどいけど)、ふつうに計算するパートが意外とむずいよね……。

あんまネタバレせんかったな。

(2n-1)!! (奇数階乗) を mod 2^64 で求める

いろいろ忘れないようにメモ✍しておくとよさそうなので書いておきます。

やること

 n \geq 1 に対して  2n-1 以下の奇数をすべて乗算した奇数階乗 (奇数に対する二重階乗)

\begin{align}
(2n-1)!! = 1 \cdot 3 \cdot 5 \cdot \cdots (2n-3)(2n-1)
\end{align}

\mod 2^{64} で高速に求めます。具体的には  w=64 として  O(w^2 \log n) 時間です。

ここで  w^2 の部分は多項式の乗算と平行移動 ( P(x) の係数から  P(x+k) の係数を求める) にかかります。

やりかた

ソースコードです。Petrozavodsk Camp の問題で出たんですがジャッジがどこか分からない……。いちおう  n \leq 10^6 の範囲で愚直なのと比較して verify してあります。

uint64_t oddfact(uint64_t n) {
  if (n == 0) return 1;

  static uint64_t comb64[64][64];
  if (comb64[0][0] == 0) {
    for (int i = 0; i < 64; ++i) {
      comb64[i][0] = comb64[i][i] = 1;
      for (int j = 1; j < i; ++j) {
        comb64[i][j] = comb64[i - 1][j] + comb64[i - 1][j - 1];
      }
    }
  }

  using poly = array<uint64_t, 65>;
  poly p = {1};
  uint64_t k = 0;

  for (int b = 63 - __builtin_clzll(n); b >= 0; --b) {
    if (n & (1ULL << b)) {
      for (int i = 63; i >= 0; --i) {
        p[i + 1] += 2 * p[i];
        p[i] *= 2 * k + 1;
      }
      ++k;
    }
    if (b == 0) break;

    poly q = {}, r = {};
    for (int i = 0; i < 64; ++i) {
      uint64_t pk = 1;
      for (int j = i; j >= 0; --j) {
        q[j] += p[i] * comb64[i][j] * pk;
        pk *= k;
      }
    }
    for (int i = 0; i < 64; ++i) {
      for (int j = 0; i + j < 64; ++j) {
        r[i + j] += p[i] * q[j];
      }
    }
    p = r;
    k *= 2;
  }

  return p[0];
}

やってること

多項式  P_k(x) を以下のように定めます。要は  2x+1 から始まる  k 個の奇数の積です。

\begin{align}
P_k(x) = (2x+1)(2x+3)\cdots(2x+2k-1)
\end{align}

すると求めたい  (2n-1)!! P_n(0) になるので、これを計算すればよいです。ここで、すべての  x の出現に  2 が掛かっていることから、 \mod 2^{64} で考える場合  x^{64} 以上の高次の係数はすべて  0 になります。したがって  0 次から  63 次までの係数を持っておけば  P_k(x) を評価するには十分です。

この多項式  P_k(x) (の係数) は典型的な繰り返し二乗法の形で効率よく計算できます。

  •  P_{2k}(x) = P_k(x) \cdot P_k(x+k)
  •  P_{k+1}(x) = P_{k}(x) \cdot (2x+2k+1)

よって上のような多項式の計算を  O(\log n) 回やれば目的の  P_n(x) (の係数) が求められ、全体で  O(w^2 \log n) 時間で  (2n-1)!! が計算できました。

Xmas Contest 2017 D 問題 Inversion Number 解説

Xmas Contest 2017 D 問題「Inversion Number」の解説です。

問題概要

素数 N の順列であって、その転倒数を K で割った余りが m であるようなものの個数を 10^9 + 7 で割った余りを求めよ。

制約

  • 1 ≦ N ≦ 10^18
  • 0 ≦ m < K ≦ 10

解説

まず、N がさほど大きくない場合の解法を紹介します。この場合、

  • dp[n][k] := 長さ n の順列で、その転倒数を K で割った余りが k になるものの個数

という DP を行うことができます。長さ n の順列に新たに n+1 を挿入することを考えると、その挿入位置から転倒数の増分がすぐにわかるので、全体として以下のような DP になります。

dp[0][0] = 1;
for (int i = 0; i < N; ++i) {
  for (int j = 0; j < K; ++j) {
    for (int pos = 0; pos <= i; ++pos) {
      dp[i + 1][(j + pos) % K] += dp[i][j];
    }
  }
}

ここで、ちょうど K 番目の要素を挿入するときの DP 配列に注目しましょう(つまり、N=K となる場合の答えに注目します)。このときだけに注目すると DP 配列は次のように更新されています。

for (int mod = 0; mod < K; ++mod) {
  for (int pos = 0; pos < K; ++pos) {
    dp[K][(mod + pos) % K] += dp[K - 1][mod];
  }
}

これは、dp[K-1][mod] の値が、dp[K] の mod 番目、 (mod+1)%K 番目、(mod+2)%K 番目、……、(mod+K-1)%K 番目に足されているということで、結局 dp[K] の全体に1回ずつ足しているだけです。つまり、

  • dp[K][mod] = Σ_p dp[K-1][p]

が成り立ちます。この値は mod に依存していないので、N=K となる場合の答えは m に依存せずすべて同じであることがわかります。すなわち、N=K となる場合の答えは N! / K に他なりません。

さらに、このことに注意しながら N>K の場合を考えましょう。DP の更新式から、dp[n][mod] の値は dp[n-1] から n 個の値を持ってきて足し合わせたものになっていることがわかります。N=K のときに dp[K] の値はすべて同じになることがわかっているので、dp[K+1], dp[K+2], ..., もすべて mod に依らず同じ値を持つことになります。結局、N≧K となる場合の答えは N! / K であることがいえます。

ここまでくれば次のような解法でこの問題を解くことができます。

  • N < K のとき、N < K ≦ 10 なので DP や全探索によって解く。
  • N ≧ K のとき、N! / K を求める。

残った問題は N ≦ 10^18 のときに N! mod 10^9+7 をどう高速に求めるかという部分です。

N ≧ 10^9+7 のとき N! は 10^9+7 の倍数なので、当然 N! mod 10^9+7 = 0 となります。

N < 10^9+7 のとき、まだ O(N) かけていては間に合いません。そこで、N が何か適当な定数 (たとえば 500万とします) の倍数のときの N! mod 10^9+7 の値をあらかじめ求めてプログラム中にその結果をすべて埋め込んでおきます(これは手元で数秒〜数十秒程度の計算でできるはずです)。すると、任意の N < 10^9+7 に対しての N! の計算が高々 500 万回の掛け算で行えることになります(N 以下の 500 万の倍数で最大のものの階乗の値が埋め込んであるので、あとはそこから N までひとつずつ掛け算していく)。

以上でこの問題を十分高速に解くことができました。

Xmas Contest 2017 C 問題 Revenge of Kurousa 解説

Xmas Contest 2017 の C 問題「Revenge of Kurousa」の解説です。

問題概要

a〜z の 26 個の 8bit 整数型の変数がある。はじめ a に入力の値が入っており、b〜z は 0 である。できる操作は

  • ビットごとの論理演算: 16 種類ある論理演算のうち好きなものを選び、ビットごとの論理演算を行える(実質 Z = X NAND Y ができるのと同じ)。
  • 加算

の計 17 種類。この操作だけを使って a の値をインクリメントする(255 は 0 にする)ようなプログラム(操作の列)を書け。

加算を使う回数が最小に抑えられていれば 100 点、最小の2倍以下に抑えられていれば 30 点が得られる。

解説

最初にネタバレをすると、必要な加算の最小回数は 1 回です。よって、30 点をとるためには 2 回の加算でインクリメントする必要があります。

部分点解法(加算2回)

最初に 1 を作って、それを a に加算することを考えます。よって、1 を加算 1 回で作れれば十分です。

1 を作るには、たとえば以下のようにします。

  • 11111111 を作る(b = b 1111 b など)
  • 11111110 を作る(c = b + b)
  • 00000001 を作る(d = b 0110 c、つまり d = b xor c)
満点解法(加算1回)

以下では整数は全て mod 256 で考えます。要は 255 (2進数で 11111111) のことを -1 とか書きます。

まず、ビットごとの論理演算だけで入力値 A と 0 だけから作れる数はほとんどありません。具体的には以下の 4 種類しか作れません。

  • 0
  • A
  • -1 (b = b 1111 b などとして作る)
  • -A-1 (255-A と同じ、要は not A)

なので、ここで 1 回加算を行う必要があります。0 と何かを足しても意味がなく、A + (-A-1) = -1 はすでに -1 が作れる以上意味がないので、加算した結果として意味があるのは

  • A-1
  • -A-2

のいずれかです。

ここで not X が 255 - X = -X - 1 だったことを思い出せば

  • not (-A-2) = 255 - (-A-2) = A + 1

となりインクリメントができました。

Xmas Contest 2017 B 問題 Hello, Xmas Contest 2017 解説

Xmas Contest 2017 の B 問題「Hello, Xmas Contest 2017」の解説です。

問題概要

長方形グリッドの各マスに文字を書いて(書かないマスがあってもよい)、そのグリッドを 0 度・90 度・180 度・270 度のいずれの角度に回転した場合でも "XmasContest2017" という文字列が読み取れるようにせよ。ただし文字列の読み取りは以下のように行われる。

  • 上の行から順番に一行ずつ見ていく。
  • 見ている行に文字が書かれたマスが1個もなければ無視する。
  • 見ている行に文字が書かれたマスがあれば、そのうち最も左にあるものに注目する。そこに書かれた文字がアスタリスク '*' なら、この行を無視する。そうでなければ、その文字を読み取る。

グリッドのサイズも 100x100 を超えない範囲で自由に決めてよい。文字の書かれたマスが 32 個以下で満点 (100点)、100個 以上なら 0 点で、その間は 100 点から 0 点まで線形に点数が得られる。

解答

64 文字解答
17 17
*7102tsetnoCsamX*
X...............7
m...............1
a...............0
s...............2
C...............t
o...............s
n...............e
t...............t
e...............n
s...............o
t...............C
2...............s
0...............a
1...............m
7...............X
*XmasContest2017*

どう回転しても、各行の最初の文字に読ませたい文字を置いておけばそれを読んでくれることを使えば、四辺に読ませたい文字列を書くことで条件を満たす看板が作れます。

32 文字回答
16 16
*7..............
X.1.............
.m.0............
..a.2...........
...s.t..........
....C.s.........
.....o.e........
......n.t.......
.......t.n......
........e.o.....
.........s.C....
..........t.s...
...........2.a..
............0.m.
.............1.X
..............7*

文字列を斜めに並べることで、1 つの文字列を 2 つの方向から読み取らせることができるようになります。

そのほか

共通する文字を頑張って省く、斜めに一本だけ文字列を置いて残りを辺で埋めるなど、32文字と64文字の間の解もコンテスト中にいくつか見られました。