プログラミングコンテストチャレンジブックの分割数について

「分割数」でぐぐると同様の記事がいろいろ出てくるのだけれど、やっぱりよく分からなかったので考えたらようやっと納得がいった。なので、その記録をしておく。

まず、なんだか分からなかった原因は、「jのi分割数」というのは「jを1以上の自然数i個の和でかきあらわしたときの(順序を無視した)書き表しかたの個数」であるはずなのに、0の和も考えているようにも読めて何を考えているのだかよく分からなくなるところにあったと思う。そういうわけで、式と向き合っていたところ意図がわかった。

「jのi分割」は「jを1以上の自然数i個の和でかきあらわしたときの(順序を無視した)書き表しかた」で、これらのなす集合である「jのi分割のなす集合」を考える。
この集合を、「jのi分割のなす集合のうち、2以上のみを(1個以上)使うもの」と「jのi分割のなす集合のうち、1を(1個以上)使うもの」の2つに分ける。
すると、この2つの部分集合は交わりがなく、しかもこの2つの集合の結びは「jのi分割のなす集合」となるので、「jのi分割数」であるdp[i][j]を求めるには、この2つの部分集合それぞれの元の個数を数えればよい。

まず、「jのi分割のなす集合のうち、2以上のみを(1個以上)使うもの」の個数を考える。実は、「jのi分割のなす集合のうち、2以上のみを(1個以上)使うもの」と「(j-i)のi分割のなす集合」との間には同型対応が作れる(つまり、余りもダブりもなく、2つの集合から1つずつ選んできたペアを作ることができる)。具体的にどうするかというと、「jのi分割のなす集合のうち、2以上のみを(1個以上)使うもの」の元「2をa_2個、3をa_3個、…」に対して*1「1をa_2個、2をa_3個、…」と割り当てる。いま、i分割を考えていることから、a_2+a_3+\dots = iが成り立っており、この対応は確かにi分割をi分割に写している。さらに、jの分割を考えていることから\sum_{i\ge 2} i a_i = jとなっており、よって \sum_{i\ge 2} (i-1)a_{i}= \sum_{i\ge 2} i a_i - \sum_{i\ge 2} a_i = j - iとなる。よって、確かにjの分割を(j-i)の分割に写している。以上のことより、この対応は確かに「jのi分割のなす集合のうち、2以上のみを(1個以上)使うもの」から「(j-i)のi分割のなす集合」への写像になっている。逆の対応は明らかなので省略し、それが全単射になっていることも省略する*2。よって、「jのi分割のなす集合のうち、2以上のみを(1個以上)使うもの」の個数はdp[i][j-i]である。

次に、「jのi分割のなす集合のうち、1を(1個以上)使うもの」の個数を考える。「jのi分割のなす集合のうち、1を(1個以上)使うもの」は、その使っている1を取り除いて考えれば「jの(i-1)分割」になり、逆の対応もつけることができて同型であることがわかる。よって、「jのi分割のなす集合のうち、1を(1個以上)使うもの」の個数は「jの(i-1)分割」の個数であり、これはdp[i-1][j]である。

以上で、dp[i][j] = dp[i][j-i] + dp[i-1][j]である。

集合の分け方が一番のミソでした。

*1:「2以上のみを～」という定義から、「1を0個」使っているということに注意。つまり、「1をa_1個～」と書く必要はない。

*2:だんだん飽きてきた

米田の補題のしょうもない使用例

マクレーンを読んでて米田の補題を示したはいいが何やってるか全然わからないし、議論する階層も深すぎて何を扱ってるのかもよくわからなかったのでしょうもない
例を作った。式は
y\colon \bf{Nat}(D(r,-),K) \simeq Krだが、右の Krから何か元をとってきてそこからどんな自然変換ができるかを見てみることにした。

それぞれの登場人物は、以下のようにする。

  • 圏 D: モノイドの圏。 D=\bf{Mon}
  • 関手 K: \bf{Mon}から\bf{Set}への忘却関手
  • r: 「 \{a,b,A,B\}という4文字のアルファベットを並べた文字列」というモノイド

そして、 Krの元として文字列「 AabB」をとり、これが y^{-1}でどんな自然変換を生むかを見る。

「AabB」を使って、モノイド dを固定したときに自然変換 \alpha_dを作りたい、つまり
モノイド準同型 f\in D(r,d)が \alpha_dで Kdのどこに写るかを定めたい。
そのためには以下の図式を使うのだった。

f:id:sle:20151130011539p:plain

ここで、この図式の左側はモノイドの圏の図式で、右側が集合の圏の図式なことに注意する。
ここで、右の四角の左上に恒等写像 1_rを流せば、図式の可換性より
\alpha_d(f) = (\alpha_d \circ (f\circ ?) )(1_d) = ( (Kf)\circ (\alpha_r) )(1_d) = (Kf)(\alpha_r 1_d)
となるが、この \alpha_r 1_d \in Krを今は文字列「 AabB」と定めるというのが y^{-1}
の定義だった。つまり、
(Kf)(\alpha_r 1_d) = (Kf)("AabB")であり、
\alpha_d(f) = (Kf)("AabB")ということになる。

具体的にこの自然性を使ってみる。
いま、「 \{a,b\}という2文字のアルファベットを並べた文字列」というモノイド (\{a,b\}, \cdot)を考える。
また、先のモノイド rは (\{a,b,A,B\}, \cdot)と書くことにする。
さらに、モノイド準同型 {\bf{count}} \colon (\{a,b\}, \cdot) \to (N, +)を文字数を数えるモノイド準同型とする。
ただし、 Nは0以上の自然数。このとき、自然性より次の図式が得られる。

f:id:sle:20151130013459p:plain

ここで、この図式の左側はモノイドの圏の図式で、右側が集合の圏の図式なことに注意する。
ここで、図式の左上に、大文字を小文字に、小文字をそのままにするモノイド準同型
{\bf {lower}} \in {\bf {Mon}}( (\{a,b,A,B\}, \cdot),(\{a,b\}, \cdot) )を入れてみる。すると、
↓→というたどりかたでは、
\begin{align} (\alpha_{(N,+)}\circ ({\bf count} \circ ?) )({\bf lower}) &= \alpha_{(N,+)}( {\bf count} \circ {\bf lower}) \\ &= ({\bf count} \circ {\bf lower})("AabB")\\ &= {\bf count}("aabb")\\ &= 4. \end{align}
一方、→↓というたどりかたでは、
\begin{align} ( (K{\bf count}) \circ \alpha_{(\{a,b\},\cdot)} )({\bf lower}) &= K{\bf count}({\bf lower}("AabB") )\\ &= K{\bf count}("aabb")\\ &= 4. \end{align}

となり、確かに一致する。↓→での "aabb"はモノイド (\{a,b\}, \cdot)の元であり、
→↓での "aabb"は集合 \{a,bからなる文字列\}の元であることに注意する。

つまるところ、「準同型を忘却させて関数を作り、そこに『AabB』をわたす」という操作は自然である」ということになった。

忘却関手を使うとこのへんがごちゃごちゃになるしもうちょっと込み入った関手を使えばよかったのかなあ。

tikzcdが動かなかったけど直った話

TeX

前も似たようなことをやったのに忘れて同じ轍を踏んだので大したことではないが書いておく。

breqnと衝突しているらしく、あれを外したら動いた。黒魔術系パッケージには気をつけましょう。

右可逆写像・左可逆写像・単射・全射

math

2ヶ月に1回ぐらい「あっ！右逆写像と左逆写像と単射と全射の関係の覚えかたを思い付いたぞ！」となってその後忘れるというのをくりかえしているのでこの際きちんと書いておく。

f:id:sle:20150628013937p:plain

写像を分解すると、結局単射は B \subset Aのときの、そのままの元に写す写像 B \to Aが典型的なので、そのときだけを考えることにする。そうすると上の図の上段のようにAのBの部分はそのまま写し、残りは出鱈目に送れば左逆写像が作れる。よって、単射ならそれに対して左逆写像が作れる。

写像を分解すると、結局全射は B\subset Aのときの、AのBのところをそのままの元に写し、残りは出鱈目に送る写像が典型的なので、そのときだけを考えることにする。そうすると上の図の下段のようにBをそのまま写せば右逆写像が作れる。よって、全射ならそれに対して右逆写像が作れる。

ゲームを作りたい人は割とすぐ作りはじめられるのではないか

人生の混沌: システム工学に関するメモ(講演資料作成にご協力お願いします)という記事をサークルの同期が書いたのだが、そもそもゲームを作りたい人があまり情報に恵まれていないというところに賛同できないので、何をすればいいかを書いてみる。

本を読めばいいのではないか

一般論として、はじめての人はできるだけ新しい本を買ったほうがいいのではないかと思う。
なぜなら、古い本だと使っているOSが古かったりプログラミング環境が古かったりする
ために、スクリーンショットが微妙に食い違ったり、メニューを辿るときに
「ファイル→プロジェクト→…」といった辿りかたがずれたりして、
そのために混乱するかもしれないから*1。
ある程度なれれば自分で修正できるのだが、いまはとりあえずゲームが作りたいのだから
そういう力を鍛えようなどとは思わないほうがいい。

また、一般論その2として、よく分からなかったら2冊目を買ったほうがいいと思う。
文体や扱う題材には向き不向きがあるので、2冊目だったら案外すいすい行けたり
することもあるし、根本的に本に書いてあることが間違っていたということは十分ありえるから。

あと、これからいろいろ挙げていくが読んだり読んでなかったりすることはご了承いたあきたい。

HSP

伝統あるかんたんプログラミング言語という感じがする。
プログラミングコンテストHSPプログラムコンテスト2014が定期的に実施されていて、
昔から小学生や中学生の投稿が目立つことからも取っ付きやすいなどと思う。
本も無数に出ていて、関連書籍の紹介本屋さんで
自分の作りたい感じの画面が載っているものを選べばよいと思う。

3Dプログラミングやネット対戦対応もできたと思うので、
込めた愛情でそこらの同人ソフトを凌駕することは十分可能だと思う。

なでしこ

日本語プログラミング言語。英語がどうしてもいやだという人がやると良い。
使っているうち英語がわからないままでも、「ああ、『もし』を単に『if』で置き換えればいいだけなんだな」ということで、英語ベースの言語にも馴染んでいけると思う。
本はほとんどないが、公式のマニュアルが絵がたくさんついていて楽しく読める。
基礎編プログラミング基礎編で文法を学んで、
ゲーム編ゲーム製作編まで用意してある。
ただ、描画機能がそんなに優れているわけではないので
あまり長居はしたくない気がする。

ゲームプログラマになる前に覚えておきたい技術

一昔に話題になった名著。セガの研修で使われている(いた)らしい。
C++の知識は仮定するが、そんなにヘビーではなかったと思うので
「ゲーム作るにはC++だと聞いてC++の本を読んでいたが飽きて半分で投げた」
というぐらいでもそのC++の本を傍らに置けば読めると思う。
あと、高校数学がすこし必要になるので、自信がなければ手頃なサイトを見つけておくか、
「大人のための高校数学を復習～」という類の本を手元に置いておいたほうがよい。

ただ、大問題として確かVisual Stuido 2008 + DirectX9で進んでいくので、
いま読むには結構古い感じがある。

作るものは本当に本格的だし、作っていく過程の話も文中に織り交ぜてきたので楽しく読めるのではないか。

[普及版]ジェネラティブ・アート―Processingによる実践ガイド

最近の私の一押し。
使う言語はProcessingで、デザイナに人気があると言われている。
綺麗な模様を出しながら短い行数でifやforの基本構造を学べるので、
飽きずにどんどん進めるはずである。

全然そういうテーマではないのだが、ジェネラティブということで
短いルールで複雑な模様を出すということを扱っているので、
絵が描けない人がアブストラクトで意味深な画面を作れるようになるという意味でも
ゲーム作りには良いのではないか。

言い忘れたが、ゲームそのものを作る本ではない。

「14歳からはじめる～」シリーズ

Amazon.co.jp： 14歳からはじめるC言語わくわくゲームプログラミング教室 Visual Studio 2013編: 大槻有一郎: 本が例えばある。
全然読んでないが伝統あるシリーズなのできっと楽しく読めると思う。
「なか見！検索」したが、絵がかわいい。

ぐぐろう

プログラミングをする人でも、そのプログラミング言語のことが全て頭に入っている
人というのは多くなくて、大体わからなくなる度に調べているものだと思う。

例えば、「セーブデータを作りたい」と思ったときは
「C# ファイル書き込み」などと調べることになる。ここで、
「C# セーブデータを作る」と書くのはあまりいい手ではないという意味で
ぐぐるというのも難しいのだが、その辺のキーワードの選び方は
入門書を一冊読んで、なんとなくぐぐることをくりかえすうちに身に付くのではないか。

Unityについて

いま流行りのゲームエンジンで、なんだかコードを書かずにゲームが作れるような
謳い文句だが、流石にコードは書かないとまずい。

Unityは画面のなかにどんどん物を置いていくのだが、
例えばその制御を何にまかせるのかや、物理エンジンを手書きしたほうがよいのか、
Unity内蔵のもの使ったほうがいいのかなど、使い方の幅が広く、はじめての人だと
かえって途方に暮れることが多いのではないかなあと思っている。
実際Twitterで流れてくるツイートを見ても、Unityの使い方はユーザーの数だけあるという
感じだし、Unityが真価を発揮するのはエディタ拡張でどんどん環境を変化させていってから
という感じがする。

はじめてやるのが悪いというわけではないが、決して簡単ではないので、
「Unityで駄目なら俺には駄目なんだ」と悲観するのは不味くて、
是非上に挙げたような古典的な方法を試してみていただきたい。

おわりに

文章が雑だなあ。

*1:特に環境変数の設定なんかWindowsがアップグレードする度にやり方が変わってしまって困りますね。

今日の英語

今日の英語

  • 何かを示すことを予告する
    • We must show that A.
    • What has to be shown is A.
  • 定義する
    • A are said to be B if C.
    • A is B defined by C.
    • A is referred to as B.
  • 仮定する
    • Suppose that A.
  • 話を進める
    • A means that B
    • This follows from the fact that B.
    • This means A.
    • Then,
  • そのほか
    • The identity map (theなんだねそうだね。)

今日の豆知識

有限群の準同型f\colon A\to Bについて、|A|と|B|が互いに素なら、Aの部分群
Hは\ker fに包まれる。なぜなら、Bの部分群f(H)の位数は|A|と|B|の両方を割りきらなければならず、互いに素なので|f(H)|=1となり、f(H)=\{1\}となるから。