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

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

まず、なんだか分からなかった原因は、「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』をわたす」という操作は自然である」ということになった。

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

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

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

f:id:sle:20150628013937p:plain

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

写像を分解すると、結局全射 B\subset Aのときの、ABのところをそのままの元に写し、残りは出鱈目に送る写像が典型的なので、そのときだけを考えることにする。そうすると上の図の下段のように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\}となるから。

Atomでのforward searchとinverse search

最近はSyncTeXで、書いているTeX文章とプレビューア(SumatraPDFがメジャーだそうで)との間を行き来できるようにするのが流行りだそうですね。
ぼくはこの度メインのテキストエディタEmacsからAtomに移そうと画策していたのですが、inverse searchは簡単にできてもforward searchには結構手間取ったのでここに過程とか解決策を書いておこうと思います。まとめると、Windows上でテキストエディタとしてAtomを、プレビューアとしてSumatraPDFを使ったときのinverse searchとforward searchについて書きます。

Atomでinverse search

inverse searchは、プレビューアの文章のほうで選択した箇所に対応する
位置に、テキストエディタ上でジャンプする機能です。できたPDFを読んでいて「あ!誤字だ!」となったときに、対応する場所にテキストエディタ上で簡単にジャンプできて便利です。

これは、エディタにコマンドライン引数でファイルを指定して起動するときに、一緒に開く行数を指定すればいいだけなので簡単です。このとき、「それってファイルを二重に開いてしまうのでは」という気もして、実際そういうエディタもありますがAtomはデフォルトで今開いているファイルをアクティブにするようにできているようなので大丈夫でした。
この設定はSumatraPDFの側で行います。

1. まず、SumatraPDFで何か適当なSyncTeX対応のPDFファイルを開きます*1
2. 「設定」→「オプション」と画面を開きます。
3. 「逆順検索コマンドラインの設定」を開きます。もしもそのような項目がなければ、1の「SyncTeX対応の」を満たしていない可能性があります。SyncTeX対応にするには、LaTeXファイルのコンパイル時にオプションをつける必要があるので、http://oku.edu.mie-u.ac.jp/~okumura/texwiki/?SyncTeXここで確認しましょう。
4. テキストボックスに「(Atomのパス)\atom.exe %f:%l」と入れます。Atomは「(ファイル名):(行番号)」で行を指定したファイルが開けるようです。AtomにPATHが通してあるならパスはわざわざ書かなくていいと思います。ぼくは「C:\Users\(ユーザ名)\AppData\Local\atom\app-0.187.0\atom.exe %f:%l」となりました。

これで完了です。SumatraPDF上でジャンプしたい箇所をダブルクリックすると、
それに対応した位置にAtom上でジャンプが起こります。

Atomでforward search

今度は逆に、テキストエディタから、対応する位置にPDF上でジャンプする機能です。あんまり使わないかもしれませんが、例えば「あるコマンドで書いてた数式を別の書き方をしてみた」というときに、その出来上がりを確認するとか…?

結論だけ言ってしまうと、sumatra-forwardsearchというAtom拡張を作ってみたのでよかったら使ってみてください。飛びたいところでコマンドパレットを開いて(Ctrl+Shift+P)「forwardsearch」というコマンドを叩けばOKです。その際、対応するPDFファイルをSumatraPDFで開いている必要があります。

forward searchは、プログラムと別のプログラムとの間で通信する仕組み*2としてWindowsが提供している超古代テクノロジーのDDE(Dynamic Data Exchange)を利用しています。SumatraPDFがDDEのために開放している窓口に、

[ForwardSearch("(TeXファイルのパス)",(行番号),(列番号),(新規ウインドウにするか),(フォーカスを合わせるか))]

というコマンドを送ればよいようです。これが超古代テクノロジーなのでDDEのコマンドを送る方法を探すのに大分難儀したのですが、NDdeという.Net用ライブラリがあって救われました。150DLぐらいしかありませんがサンプルもたっぷりついててとても使い易かったです。これで、

というC#のプログラムを書きました。DDE通信の部分は本当にこれだけです。あとはこのプログラムをAtomから呼び出してやればいいだけです。そのために、Atom拡張を書く羽目になりました。AtomCoffeeScript(JavaScriptの派生)+LESS(CSSの派生)+Node.JS(JSでブラウザ上に限らない「普通の」プログラムを書けるようにしたソフトウェアという認識でいる)で拡張します。
Web系の技術は移ろいが激しくて真剣に勉強する気になれなかったので、
CoffeeScript入門(前編) ― CoffeeScriptの基本構文 - Build Insiderを10分ぐらいで読んで、Atom
固有の拡張機能の書き方については3.1 Hacking Atom : Tools of the Tradeを読んで、チュートリアルをこなしてから書きました。バージョンアップが激しいので最新のを読むように気をつけましょう。結局Atomから外部のプログラムを起動したいので、メインは
Atomこれを使うことです。あとは現在のカーソルの行番号をAtom上で取得できればいいのですが、Atomチュートリアルの「Word Count」をこなしているうちに「atom.workspace.getActiveEditor()」でなんとかなるだろうという当たりがついて、
あとはAtomの「View→Developer→Toggle Developer Tools」で開ける
対話型のJSコンソールの入力補完をたよりにいろいろやってたらできました。
Atom開発をするときにここをうまく使うというのは1つコツになるでしょう。
基本的にDeveloper ToolsはChromeのやつなので、慣れてない人は
ChromeでDevelper Toolsを使いながらJSを触ってみるということをやってみるといいと思います。
ネット上にそういう記事が多分あると思います。
拡張自体はCoffeeScriptで書くのにコンソールではJSを書くというのは
結構いろいろやる羽目になって大変だなあという気はします。結局、

という風になりました。「__dirname」でこのスクリプトの位置が分かるというのは「Node.js カレントディレクトリ」でぐぐったんだったと思います。「Node.js (やりたいこと)」でぐぐるのも1つコツになりそうです。コンパイルした先のC#プログラムは、このcoffeeファイルと同じディレクトリに入れておきます。

あとはチュートリアル通りこれをコマンドで呼び出せるようにして完了になります。完成品はGithubashiato45/sumatra-forwardsearch · GitHubに置いてあるのでよかったら見てみてください。

参考文献

*1:というか「SyncTeXデータが同じディレクトリにある」と言うべきなのかもしれない

*2:プロセス間通信