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 → ∞ で正である など、意外な結果もあります。