の締め切り終わったら頑張った自分へのご褒美（笑）であれとこれとそれをやる時間をとるぞー！ ……みたいなことを思っていたはずなのに、いざ提出し終わると気が抜けて何一つやる気がでない問題。
困った困った。
たくさん人がいらしてる今のうちに 「ナイトメア☆チルドレン」新装版 面白いよみんな買おうぜ！ などと書いてみる。
自分のマンガの趣味はわりと平凡だと思ってて、 流行ってるマンガは大抵好きだし自分の好きなのはだいたい流行ってるし。 なのになぜだか藤野もやむ作品だけは唯一の例外で、とっても不思議でならない。 100回くらいアニメ化されてて然るべきだと思う。 何回か書いてますがとにかく最終話が好きで、 そこまでのシナリオが一気に集まって一つ一つのセリフが３倍の重みを持つように収斂していく幕引き。 あれは良い。
第一回はこちら。 シリーズ化なんて考えてなかったんですけど、まあ勢いで。
さて許される計算量のオーダーは推測できた、ではアルゴリズムを考えよう……、 という時に、自分は、どうも３種類くらいの方法でアルゴリズムの設計を試みているように思います。 今回はそのうちの一つをまとめてみます。
題材は "Small Change"。 どういう問題かというと、『Anarchygolfania という国で流通している貨幣(コイン)の一覧と、 払いたい金額が与えられます。できるだけコインの枚数が少なくなる払い方を答えましょう』です。 たとえば、Anarchygolfania には1円玉と7円玉と12円玉だけがある場合、14円を払うには、 7円玉2枚で払うのが最適です。
現実の貨幣では、たいてい単純に大きい額のコイン/紙幣から順に使っていくと最適になるものですが、 この例の場合は、それをやると 12+1+1 の3枚になっちゃって、ダメです。 というわけで、最適解を見つけるにはいささか工夫が必要です。 ええと、問題を整理しましょう。こうですね。
いくらでも解き方は考えられますが、さてさて…。
自分はよく、ちょっとだけ問題を「小さく」して考えてみます。
たとえば、入力 T を小さくしてみる。 コインの金額は同じままで、T-1 円 の最適な払い方をまず計算してみよう。 そしたらそこから簡単に T円 の最適な払い方も求まったりしないでしょうか…？ 残念ながら、難しそうです。T-1円の払い方を応用してT円を払うなんて、 あとに1円玉を付け足すくらいしか手がありません。けど、それが最適になるとは限りません。
諦めずに問題を小さくしまくります。 T-1 円 の最適な払い方と T-2 円 の最適な払い方と、(中略)、 3 円 の最適な払い方と 2 円 の最適な払い方と 1 円 の最適な払い方と 0 円 の最適な払い方を全部計算したらどうだ！
今度はなんとかなります。たとえば、コインが 1円玉、7円玉、12円玉だったら、 T円の最適な払い方は、 「T-1円の最適な払い方 + 1円玉」 か 「T-7円の最適な払い方 + 7円玉」 か 「T-12円の最適な払い方 + 12円玉」 のどれかしかありえないので。 コードで書くとこうです。
opt[T] = # T円の最適な払い方は
C.select{|c| opt[T-c]}.
map{|c| opt[T-c]+[c]}. # T-c円の最適な払い方 + c円玉
min_by{|p| p.size} # … のうち一番枚数少ないヤツ
よし、でき…てないですね、まだ。 T-1 円の最適な払い方とT-2 円の最適な払い方と（中略）の最適な払い方を全部計算しておかないと、 このコードだけではうまくいきません。計算しましょう。ハイパーコピペタイム！
...
opt[T-2] = # T-2円の最適な払い方は
C.select{|c| opt[T-2-c]}.
map{|c| opt[T-2-c]+[c]}. # T-2-c円の最適な払い方 + c円玉
min_by{|p| p.size} # … のうち一番枚数少ないヤツ
opt[T-1] = # T-1円の最適な払い方は
C.select{|c| opt[T-1-c]}.
map{|c| opt[T-1-c]+[c]}. # T-1-c円の最適な払い方 + c円玉
min_by{|p| p.size} # … のうち一番枚数少ないヤツ
opt[T] = # T円の最適な払い方は
C.select{|c| opt[T-c]}.
map{|c| opt[T-c]+[c]}. # T-c円の最適な払い方 + c円玉
min_by{|p| p.size} # … のうち一番枚数少ないヤツ
嘘ですすみません。ループしてください。
opt = {} # opt[t] は t円の最適な払い方。これから求めるよ！
opt[0] = [] # 0円 はコイン0枚で最適に(?)払えます
1.upto(T) do |t|
opt[t] = # t円の最適な払い方は
C.select{|c| opt[t-c]}.
map{|c| opt[t-c]+[c]}. # t-c円の最適な払い方 + c円玉
min_by{|p| p.size} # … のうち一番枚数少ないヤツ
end
p opt[T]
これが答えその１。
「なんで T を小さくしたの？ 他の部分を小さくするのはダメなの？」 と思ったので、N を小さくしてみましょうか。
「C[0] .. C[N-2] のコインだけを使ったT円の最適な払い方」をまず計算してみよう。 そしたら簡単に「C[0] .. C[N-1] のコインを使ったT円の最適な払い方」も求まるのではないか。 ……これもやっぱり、そのままでは上手くいかなそうです。どこに C[N-1] 円玉 を挟み込んだものだかよくわからない。
今度は N を減らしまくって C[0] .. C[N-3]でのT円の最適な払い方、 C[0] .. C[N-4]でのT円の最適な払い方、 （中略） C[0] だけでのT円の最適な払い方、 を全部計算するのでもうまい方法が思いつきません…少なくとも私には。
めんどうになったのでTの方も同時に小さくします。 「C[0] .. C[N-2] のコインだけを使った0円と1円と2円と（中略）T-1円とT円の最適な払い方」 がわかればなんとかなるだろう！
opt = [[]] # コインを1種類も使わない場合、0円だけは払えます。他は払えません
C.each_with_index do |c, n| # c==C[n] 番目までのコインだけを使う0円と1円と（中略）T円の払い方は…
opt = (0..T).map do |t|
(0..t/c).select{|k| opt[t-c*k]}.
map{|k| opt[t-c*k] + [c]*k}. # C[n-1]までを使った t-c*kの最適な払い方 + c円玉をk枚
min_by{|p| p.size} # … のうち一番枚数少ないヤツ
end
end
p opt[T]
こんな感じで。答えその２でした。
たとえば C[1] を小さく、というのは流石に上手く行かないような気がするのですよ。 7円玉の代わりに6円玉がある世界での最適解がわかっても、そこで6円玉が7円玉に変わったらちょっとどうしようもない。 話が違いすぎる。（……と私が思っているだけで、上手い手があるかもしれません。みなさん考えてみて下さい。）
ということで、入力パラメータ C[i], N, T の減らし方は全部ひととおり考えてみたので、 もう小さくする他の方法はありません！ なんてことはありませんね！！ 出力、M を小さくしてみちゃいます。
ちょっと発想の転換が必要です。元々の問題では M は、「T円を払うのには最低M枚コインが必要」 という値でした。逆に言うと、これは「M枚あればT円払える」ということです。
さて、減らしにかかりましょう。「M-1枚 あれば T 円を払える」かどうかわかれば、 M枚あればT円を払えるかどうかもわかるのではないでしょうか？ ……やっぱり、今度も、ちょっとわかりません。 「0枚では払えない、1枚では（中略）、M-1枚では払えない」とだけ言われても、 その次、M枚で払えるか払えないかは判断つきません。
仕方がないので、また T の方をいじります。「M-1枚 あれば払える金額一覧」 があれば「M枚あれば払える金額一覧」も計算できます。
payable_by_m = {0 => []} # 0枚で払える金額一覧 == 0円:[]
0.upto(T) do |m|
if payable_by_m[T] # Tがm枚で払えるならそれが答え
p payable_by_m[T]
break
end
payable_by_m_plus_1 = {} # m+1枚で払える金額一覧を計算…
payable_by_m.each do |money, howto| # m枚あればmoney円を払えて
C.each do |c| # c円玉が存在するならば
payable_by_m_plus_1[money+c] = howto+[c] # m+1枚でmoney+c円を払える
end
end
payable_by_m = payable_by_m_plus_1
end
答えその３でした。ただし、実際には、いくつか高速化の余地があります。
「T円より大きい金額が払えるか払えないか計算しても無駄なので、money+c > T
の時にはpayable_by_...に記憶しない」とか「最適解じゃないmoney, howtoペアを考えてもしかたが無いので、
すでに払い方が求まってるmoneyのリストを別に覚えておいて、それが出てきたらpayable_by_...に記憶しない」
辺りですかね。
問題をみたらとりあえず
「パラメータ１個小さくした問題を先に解いておけば、そこから簡単に元の問題の答えも求まるんじゃない？」
と考えてみる、というのが今回紹介したやり方でした。
こうやって作ったアルゴリズムは、基本的には 動的計画法 (DP / Dynamic Programming) と呼ばれるものになります。 （ただし、答えその３みたいなのは微妙なところで、普通は幅優先探索などと呼ばれると思う。） 今回の例でループで書いた部分を、再帰 (+メモ化) で実装するという方法もあります。関数型大好きっ子はたぶんそっちの方が楽だと思います。 いずれにせよ、「パラメータをひとつ小さくしてみる」のがポイント。 大抵のアルゴリズム設計の本に載ってると思うので、詳細は書籍等で熟知すべし。
「どのパラメータを小さくすればいいか？」の判断や、 小さくしてみてダメだった時に「話をさらに進めてみる（今回だと、Nと同時にTも小さくしてみる / 払える金額一覧を計算する、のような拡張）」判断は、ある程度慣れるしかないかもしれないです。 今回はたまたまどの方向も上手く行きましたが（…といっても、どれも結局 T をいじってるので、 T を減らす方法以外は上手く行ってないと言う見方もできるかもしれませんけど）、 問題によっては、減らす正解のパラメタは一つで、 しかも、適度に求めるものを調整してやらないと全然ダメだったりします。 もちろん、この手段では解けない問題も当然あります。
ただ、でも、漠然と考えるよりは、「ひとまわり小さい問題の答えから大きな問題の答えを作れるかどうか」 に焦点を絞って考えた方が、答えが見つかりやすいんじゃないかなーと思うのでした。
『迷宮街クロニクル 生還まで何マイル？』 っと、あの 和風Wiz (跡地) がついに本になるらしい！ Amazon 曰く大幅な加筆修正らしいので大幅に期待しています。 トーナメント編すっごい楽しかったんですが、あれはどういう扱いになるのかなー。
あと最近は、本と言えば 米澤穂信 の作品にハマってます。 とりあえず文庫になってるものは全部読みました。 推理物としては『愚者のエンドロール』が一番かなあ。"犯人"の"動機"にちょっと意表をつかれたというか、 してやられた感。 お話としては『春季限定いちごタルト事件』の "For your eyes only" のラストシーンが好きで、 これを読んだときに、他の作品全部読まねばならないと心に決めました。 この人の作品に限らず、日常の謎系の話に時折混じる暗さは割と好きなのですが、あれはなんだろう。 たとえば小説の中の"殺人事件"と比べて特別戯画化されていないとかそういうことも別にないと思うのだけれど。
というわけで、5日ほど前に日本に戻ってきてました。そしていきなり熱出して倒れるなどしていました。
なにかしらこの10ヶ月ちょいを総括して感想書き残しておこう……と思ったんですけど、 別に特に書くようなこともないな。うーん。 Sebastian とご家族が良い人でほんと良くしてくれて、 いくら感謝してもし足りないとはこのことだなあ…というのが一番の感想です。うん。 シドニーは暑くもないし寒くもないし住みやすいところでした。また何度も行きたいと思う。 アジアン系のコンビニに置いてある甘い緑茶とか懐かしい。 研究は思ったより少しは進んだような気がします。 あ、あとあれですね、 どれだけ必要にせまられようとも特に英語は上手くならないということはわかりました。 はてさて。
昨日一昨日は ぱきらぽん研、じゃなくて 小林・住井研 にお邪魔して発表してきました。 この前のチーム名の由来でもある "Macro Tree Transducer" というものに関して性質を調べるときの計算量はどんなものになってるでしょうか調べてみました、というお話でした → [PPT]。 あとは小林先生の最近の研究のお話を聞かせていただいたりしました。
そういえば、それで気づいたのですが POPL の Accepted Papers 出てるんですね。Morihata-Matsuzaki が ICFP→POPL 連覇を達成してらっさる。すごい。 タイトルだけ見て気になるのは "Bidirectionalization for Free!" だなー。 この方の発表は 去年 のの中で一番記憶に残ってます。
m0h1canさんのTwitter で知った "Little Big Computer" って動画、かっこいいなあ…。
Little Big Planet という PS3 のゲームの面エディタでもって
"electronic" (not "mechanical")
な「計算機」を作ってしまったらしい。
このゲームのことを知らないので "electronic" とか "magnetic switches" と言ったときに
それがどういうレベルで現実のそれに対応するのかは分からないんですが、
なんにせよ、そういうのができるような物理シミュレーションの世界というのはすっごいなーと思う。
先日の "Clueless Crossword" は、「要するに日本でいう ナンクロ？」 と皆様に指摘いただきました！ほんとだ！ ナンクロって名前しか聞いたことなかったけど、そういうものだったのか！ 日本語でもやってみると、文字を推測するよりは単語全体を推測する要素が大きいように感じられました。 って、それは自分の英語/日本語の語彙の差の問題かも。
ところで昨日、Windowsの時計を見て「もう9時か。帰ろう」 と思って研究室を出て携帯電話の時計を見たら8時でびっくりしました。 何を言っているかおわかりと思いますが、サマータイム再び。 半年前には逆向きの切り替えは経験しない予定と思っていたのに、 まさか法律が変わってるとは予想外でした。
というわけで予定とはズレました（？）が、来週末から東京に戻ります。 短かったような短かったような。