Code Festival 2016に参加しました
今年もCode Festivalを開催していただけて（しかも，本戦まで行けて）本当に楽しかったです．問題セットも良問ぞろいでした．下の方に今回解いた問題セットがあるのですが，どのコンテストでも1問以上はこの問題考えた人頭いいなと思う問題があってすごかったです．結果は220人中98位だったのでかなりいい感じかと思います．しかも，今回はいつも負けている人に初めて勝つことができたのがいい記念になりました．（しかもきちんとパーカーもゲットした）．実は問題文を読んですらいない問題や，制約見てできそうだけどよくわからんといって投げた問題が結構あるので，後で解いて自分なりの解説をしてみたいです．問題セットはこんな感じでした．
今年は壇上で表彰されたいなぁとかひそかにに思ってたので，一番可能性たかそうなcsenryuにbrute force attackしてみたけど，DEGwerさんに大賞を取られてしまったのはちょっと悲しい．
初めての機械学習
なんやかんやあって初めて機械学習のアルゴリズムを実装しました．機械学習アルゴリズムの実装といっても大したことなくて，PRLMという教科書の最初にある多項式フィッティングというものを実装してみました．点が$N$点与えられるので誤差関数$E(\vec{w})$を最小化する$M$次多項式求めるというアルゴリズムです（入力は$N$個の点$x$と，整数$M$，出力はベクトル$\vec{w}$）．誤差関数$E(w)$は次の二乗誤差の関数を使いました．
- $E(\vec{w}) = \Sigma_{n = 1}^{N} (y(x_n, w) - t_n)^{2}$
解説は次のページがわかりやすかったです．（僕が読んだ教科書と同じ教科書を読んで解説記事を書いていてくれたので，）
点(2 4), (9 1) ,(3 8), (-1 3) (4 -2) (-3 2) (-9 4)で，
$M = 7$の場合
$M = 5$の場合
$M = 3$の場合
$M = 5$がなんか一番いい感じですね．
ビームサーチ
研究室の後輩がマラソンに出るというので一緒に参加してみようかと思いました．ただ，まだ運営がvisualizerを用意してくれないので，とりあえず練習のため，ビームサーチを実装してみました．ビームサーチは名前は聞いたことがあるけどよくわからないアルゴリズムという印象でした．
ググると色々情報が出てくるのでとりあえずこの辺りのサイトを参考にしました．
要は幅優先探索をするんだけど，ただやると計算が終わらないから，それぞれの探索木の深さで評価値がTOP $k$のノードだけ探索を続けようという結構簡単なアルゴリズムでした．練習用にAOJの0-1ナップサック問題をビームサーチで解いてみました．コードはこんな感じです．
数十秒の計算時間がかかるくらいにビーム幅を設定すると最適値*0.9くらいの答えを出してくれるのでそんなに悪くない印象を受けました．ただ，この問題は評価関数簡単だからいいけどもっと複雑な問題は色々厳しそう．
あとはビームサーチをランクアップさせた探索アルゴリズムとしてchokudaiサーチ(正式名称 beam stack search)というのがあるのでそれも勉強しておこう．．．
アルゴリズムは実装してみると色々発見があって面白いです．
マークダウンでtexマクロを定義したい
最近マークダウンの書き方を少し覚えて，メモをとるのにマークダウンを使い始めました．基本ペンで文字を書くのを面倒臭がるのですが，PCでメモを取るのは苦じゃないので，マークダウンを使ってメモを取ることにしました．
でも，メモとるのに結構数学の記法を使うのでtexが使えると便利だと思い，少しググってみると，マークダウンエディタの機能（僕はmacdownというエディタを使っています）で"$"で挟んだ区間はtexのように表示してくれるみたいです．なので，この機能を使って書いていたのですが，自分のメモの中には中かっこがたくさん出てきて，これを表示させるのがめちゃくちゃ面倒です．（"\{ hoge \}"というように書かないといけない）こんなんやってられないと思ったので，texのマクロ機能が使いたいという気持ちになりました．
しかし，ググってもマークダウンでのtexマクロの使い方が出てきませんでしたので，適当にいじっていたら次のような解決法を見つけました．
- ページの最初に"$\newcommand{ hoge }$"と入れる
この対応がいい方法かはよくわかりませんが，とりあえずこれでtexマクロを定義できたっぽいです． 実際僕はこんな感じで使ってます．
- "\$ \newcommand{\set}[1]{{#1}} \$"(なんかバックスラッシュ表示されていますが，実際には必要ありません)
これを入れておくと集合とかを書くときに"\$\set{x, y}\$"と書けば
$\set{x, y}$
と表示されてストレスフリーにメモが取れるようになりました．
あとは，ヘッダーに毎回マクロをコピペするのも面倒なので，どうにかしてマクロをまとめたファイルをヘッダーに読み込ませればもっと楽にメモ取れて良さそうです．
