CodeFestival2016本戦の問題
この前Code Festival2016に行ってきました．問題はこんな感じでした．
- A問題 Where's sunuke まあ，A問題なのでやるだけ問題です．
#include<iostream> using namespace std; int main(){ int h, w; std::cin >> h >> w; string s; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { std::cin >> s; if(s == "snuke"){ std::cout << (char)(j + 'A') << i + 1 << std::endl; } } } return 0; }
- B問題Exactly N points
どうせB問題もやるだけだろうと思って適当に貪欲解を投げたらWAでびっくり．一応一瞬考えたらにぶたんでできそうだけど，B問題でにぶたんが出るわけないと思い，貪欲解を適当にいじって2回提出してもなおWA．しょうがないからにぶたん書いてACしました．（B問題でにぶたんが出るようになったんだなぁ）
#include<iostream> using namespace std; bool check(int n, int maxi){ for (int i = maxi; i > 0; i--) { if(n >= i){ n -= i; } } return (n == 0); } int main(){ int n; std::cin >> n; int l = 0, r = n, mid = (r + l)/2; while(r - l > 1){ if(check(n, mid)){ r = mid; }else{ l = mid; } mid = (l + r)/2; } for (int i = r; i > 0; i--) { if(n >= i){ std::cout << i << std::endl; n -= i; } } return 0; }
- C問題Interpretation
$M$種類の言語があり，$N$人の人がいます．それぞれの人が喋れる言語が与えられるので任意の人が喋れるかどうかを判定しろという問題です．通訳を頼んでもいいのである人AとBが共通に喋れる言語がなくても，AともBとも喋れるCさんがいればOKという問題です．
これは$N + M$のサイズの二部グラフ作って，グラフの連結性を判定すれば良いので結構簡単．
#include<iostream> #include<vector> using namespace std; void dfs(vector<vector<int> > &g, vector<bool> &used, int v = 0){ used[v] = true; for (int i = 0; i < g[v].size(); i++) { if(used[g[v][i]] == true)continue; dfs(g, used, g[v][i]); } } int main(){ int n, m, k; std::cin >> n >> m; vector<vector<int> > l(n + m); for (int i = 0; i < n; i++) { std::cin >> k; for (int j = 0; j < k; j++) { int tmp; std::cin >> tmp; l[i].emplace_back(tmp - 1 + n); l[tmp - 1 + n].emplace_back(i); } } vector<bool> used(n + m, false); dfs(l, used); bool flag = true; for (int i = 0; i < n; i++) { flag &= used[i]; } std::cout << ((flag == true)?"YES":"NO") << std::endl; return 0; }
- D問題 Pair Cards
この辺から結構難しく感じました．ある種の最大マッチング問題としても解けるけど，一般のグラフの最大マッチングは頂点数$N$に対して，$N^{2.5}$が最速だったと思うので，どう考えても無理．（しかも1，2時間で実装できるわけがない）．なので，制限されたグラフクラスのマッチングなのかと思い，グラフを書いてたりしてたら，整数の和が$M$になるようなペアを作りたいので，与えられた整数を$M$でmodをとって，その値が同じなら同じ整数と考えてもいいことに気づく．なので，後は$M$でmodとった値が$i$の整数と$M- i$の整数をペアにしていけばいいことがわかる．ただし，まだ同じ整数のペアの数は考慮できていないので，この方法でペアを作って，余った整数で同じ整数があったらそのカード同士をペアにする必要がある．
#include<iostream> #include<vector> #include<set> using namespace std; int main(){ int n, m, maxi = 0; std::cin >> n >> m; vector<int> x(n); for (int i = 0; i < n; i++) { std::cin >> x[i]; maxi = max(maxi, x[i]); } vector<int> mod(m, 0); for (int i = 0; i < n; i++) { mod[x[i]%m]++; } int ans = 0, tmp; for (int i = 1; 2*i <= m; i++) { if(2*i == m){ tmp = mod[m/2]/2; ans += tmp; mod[m/2] -= tmp*2; }else{ tmp = min(mod[i], mod[m - i]); ans += tmp; mod[i] -= tmp; mod[m - i] -= tmp; } } tmp = mod[0]/2; ans += tmp; mod[0] -= tmp*2; vector<int> s(maxi, 0); for (int i = 0; i < n; i++) { s[x[i]]++; if(s[x[i]] >= 2 and mod[x[i]%m] >= 2){ s[x[i]] -= 2; mod[x[i]%m] -= 2; ans++; } } std::cout << ans << std::endl; return 0; }
- E問題Cookies
この問題はコンテスト中は部分点しか取れなかったです．制約を見て，dpなら部分点は取れると思い，dpの方針で考えてました．考えたいたdpは「ちょうど$k$枚のクッキーを焼くのにかかる時間は何分か?」というdpを考えました．コードはこんな感じです．
#include<iostream> #include<vector> #include<cmath> using namespace std; typedef long long int lli; int main(){ lli n, a; std::cin >> n >> a; vector<lli> cost(n + 1, 1e9); cost[0] = 0; cost[1] = 1; for (lli i = 2; i <= n; i++) { cost[i] = min(cost[i], (lli)i); for (lli j = 2*i; j <= n; j+=i) { cost[j] = min(cost[j], cost[i] + j/i + a); } } lli ans = n; for (int i = 1; i <= n; i++) { ans = min(ans, (lli)(ceil(n/double(i)) + cost[i] + a)); } std::cout << ans << std::endl; return 0; }
とりあえずこれで$O(N log N)$にはなっているとおもいます（計算量解析はあまりきちんと考えていないけど多分あっている気がする．）コンテスト中はここまでしかわかりませんでした．
コンテスト後，解説を見ながら「頭いいなぁ」と感心しながらコードを書いて次のコードでACしました．コードがpythonなのはC++でオーバーフローを機にするのが面倒だったのでpythonで書きました．
#!/usr/bin/env python # -*- coding: utf-8 -*- def pow(a, b): if b == 1:return a if b%2 == 0: return pow(a*a, int(b/2)) return a*pow(a*a, int(b/2)) def binaryOne(n, multi): l, r = 0, n mid = (l + r)/2 while r - l > 1: if pow(mid, multi) >= n: r = mid else: l = mid mid = (r + l)/2 return r; def binaryTwo(n, maxi, multi): l, r = 0, multi mid = (l + r)/2 while r - l > 1: if pow(maxi, (multi - mid))*pow(maxi - 1, mid) >= n: l = mid else: r = mid mid = (r + l)/2; return l n, a = map(int,raw_input().split(" ")) ans = 1e18 for i in xrange(0, 40): maxi = binaryOne(n, i + 1); subt = binaryTwo(n, maxi, i + 1) ans = min(ans, a*i + maxi*(i + 1) - subt) print ans
今年もパーカーをゲットできたので非常に良かったです．今年はパーカーラインが去年より高めで，半分くらいの人しかパーカーをもらってなかったぽいです．
ビームスタックサーチ
この前，ビームサーチを書いてみたので，今度はビームスタックサーチを書いてみました．この辺のサイトを参考に勉強しました．
このサイトに載っているchokudaiさんのスライドが（ビームサーチをわかっている人なら）結構わかりやすいと思いました．ビームスタックサーチは僕なりの理解として，ビーム幅を増やしながら何回もビームサーチを行うのだが，今までのサーチ中で探索したノードを記憶しておいて，一度探索した部分は探索しないようにしているようなビームサーチという感じです．ビームサーチで厄介（らしい）ビーム幅の設定を色々頑張らなくとも，探索時間をこちらで設定すればその時間内で，頑張れるだけ勝手にビーム幅を増やしてくれるので，楽ができるという利点があるようです．
解いた問題はナップサック問題で，計算時間を2秒で設定して計算しました．コードはこんな感じです．
確かにビームスタックサーチの方が計算時間を設定できる分使いやすそうだという印象でした．
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}$
と表示されてストレスフリーにメモが取れるようになりました．
あとは，ヘッダーに毎回マクロをコピペするのも面倒なので，どうにかしてマクロをまとめたファイルをヘッダーに読み込ませればもっと楽にメモ取れて良さそうです．
