ARC 041 AとB
この前のACM-ICPC国内予選で（主にコーディング面で）全然貢献できなかったという悔しい思い出を機に競プロモチベが若干上がっている昨今。CFの問題をSolver順に解いたりRoundに参加したりしてますが、久しぶりにARCに真面目に参加しました（WORKING'!!一挙放送を見ながらではありましたが）。
A問題 コインの反転
表向きのコイン（ 枚）と裏向きのコイン（
枚）を複数枚渡されて、「ちょうど
枚ひっくり返せ」と言われた時にどれだけたくさんのコインを表向きにできるか。
のとき：裏向きのコインを
枚ひっくり返せばいい→表向きのコインは
枚になる
のとき：とりあえず裏向きの
枚は全部ひっくり返す・表向きのコインのうち被害を受けるのは
枚→表向きのコインは
枚
公式解説スライドは絶対値を使って に依らない想定解を出してたけどたぶん場合分けして展開したらこうなるんだと思います（適当）。実際2つ目式の括弧の中の符号を反転すれば1つ目の式になるっぽい。雑魚だからコンテスト中に絶対値の中の正負がとか考えてる余裕はない。
import std.stdio; import std.string; import std.algorithm; import std.conv; import std.range; import std.math; void main() { int x, y; readf("%d %d\n", &x, &y); int k = readln.chomp.to!int; if (k <= y) { writeln(x + k); } else { writeln(x + 2 * y - k); } }
B問題
「わっ！」ってやると四方に分裂するアメーバがいる。「わっ！」って言った後の盤面が与えられるので、「わっ！」って言う前の盤面を出力する。
「あるセルの上下左右全てにアメーバがいたらそのセルにはアメーバがいた」と考えられる。左上から右下に向かって順番に「上下左右のアメーバのうち一番少ない数（ とする）をそのセルにいたアメーバの数にし、上下左右から
を引く」操作を続けると矛盾なく解ける。
import std.stdio; import std.string; import std.algorithm; import std.conv; import std.range; import std.math; void main() { int n, m; readf("%d %d\n", &n, &m); int[][] b; for (int i = 0; i < n; i++) { b ~= readln.chomp.split("").map!(to!int).array; } int[][] a = new int[][](n, m); for (int i = 1; i < n - 1; i++) { for (int j = 1; j < m - 1; j++) { int up = b[i][j - 1]; int down = b[i][j + 1]; int right = b[i + 1][j]; int left = b[i - 1][j]; if (up > 0 && down > 0 && right > 0 && left > 0) { int min_am = min(up, down, right, left); a[i][j] = min_am; b[i][j - 1] -= min_am; b[i][j + 1] -= min_am; b[i + 1][j] -= min_am; b[i - 1][j] -= min_am; } } } foreach (e; a) { e.map!(to!string).join("").writeln; } }
C
RRR....LLLL的なセグメントに分けるところまでは思い付いたけど「常に多い方を少ない方に寄せればいい」という簡潔な最適解まで思いつけなかった。
D
読んでない。
Sublime Text 3のD言語開発パッケージDKitを使う
概要
Sublime Text 3 で D言語を開発するためのツール DKit を Mac で導入します．結構前に出たパッケージだし紹介記事ぐらいあるだろうと思っていたのですが，UNIX 系の物は無かったので一応．
手順
DKit は D Completion Daemon（通称DCD）と連携して動作します．Homebrew にいるので brew install dcd で入ります．
README にもありますが，DKit はまだ開発途中のため，Package Control からインストールすることはできません．そのため，Packages ディレクトリに直接展開します．
# Packages ディレクトリの在処はメニューの Sublime Text → Preferences → Browse Packages... から分かります $ cd ~/Library/Application\ Support/Sublime\ Text\ 3/Packages $ git clone https://github.com/yazd/DKit
次に，設定ファイルを変更します．例によって Sublime Text → Preferences → Package Settings → DKit → Setting − User をいじります．Default に設定されている値を上書きするだけですが，DMD を Homebrew でインストールした場合は以下のようになります．
{
"dcd_path": "/usr/local/bin",
"include_paths": [
"/usr/local/include/d2/"
]
}
これで準備完了です．D 言語のファイルを開いてみます．
おお……．続けて見ていきましょう．
ちゃんと名前空間を考慮して補完されていきます．まあここらへんは全部 DCD から来た値を受け取っているだけだと思いますが．
スニペットも用意されています．
関数もちゃんとインポートされたものの中からのみ補完されます．
ファジィ検索もお手の物．
実行する時は Super + B，D - run を選択すると rdmd で実行するので標準出力を確認できます．
キーバインドで Shift + Super + G が Default の方で用意されており，関数の定義元に一瞬でジャンプできます．当然ローカルで定義した関数にもジャンプできます．
たまに Tab を押しても何も起こらないことがあるのですが，補完したかった場所でもう一度 Tab を押すとちゃんと補完されます．どうしてこういうことが起こるのかよく分かりませんが．また，現状 DCD の方で UFCS に対応していないので，Ruby のように気持ちよくメソッドチェーンするみたいなことはまだ出来ませんが，Sublime Text 2 が出た頃に D 言語のスキーマが用意されていなかったことを思えばずいぶん遠くに来たなあと思います．大学に入ってから Emacs 一辺倒だったのですが，移行しない理由の半分が D 言語が書けないことだったので，ここまで出来るとなるとうっかり移行してしまいそうです……．
AOJ CGL_1_A 射影
大学の図書館に入っていたのでこの本をざっと読んでいました．AOJにある幾何の問題を全然解いていないことに気付いたので着手しました．簡単な問題から．
問題
平面上にある点からある直線に下ろした垂線の足を求める．
解釈
幾何的にも解けるけど線形代数を使って解いてみる．下図の が分かれば
より求められる．
は点
を通る直線上にあるため，
と表せる．そのため
である（ の正負は
の値によって変わる）．また，
と
の内積を考えると
だが，図中の直角三角形に着目すると
であることが分かる．したがって
より
である．式(1), (2)より，
よって
だから，
の係数がスカラーであることに気付かないと一見「あれ？」ってなる．とにかくここまで来れば最後の式を実装するだけ．
import std.stdio; import std.string; import std.algorithm; import std.conv; import std.range; import std.numeric; void main() { auto point = readln.chomp.split.map!(to!double).array; auto p1 = point[0..2]; auto p2 = point[2..4]; int q = readln.chomp.to!int; for (int i = 0; i < q; i++) { auto p = readln.chomp.split.map!(to!double).array; double[2] p1p = p[] - p1[]; double[2] p1p2 = p2[] - p1[]; double[2] ph = p1p2[] * dotProduct(p1p, p1p2) / dotProduct(p1p2, p1p2) + p1[]; writefln("%.10f %.10f", ph[0], ph[1]); } }
を求めるには，各点同士の座標を引き算するだけ．D言語には配列のスライスを使ったベクトル演算が可能なため，
p[] - p1[]のようなベクトルの定義に沿った書き方が出来る（p[] += 3などのようなベクトルに対するスカラー演算も可能です）．dotProductはstd.numericに定義されている．D言語は神．
参考
AtCoder Typical Contest 001 をD言語で解いた（A, B問題）
競プロ界隈重要アルゴリズムが大会形式でchokudaiさんのスライドを見ながら提出できるという神コンテストが開催されたので，勉強不足な僕も参加してみました．RubyでDFSを書き始めたらデバッグが全く進まなくて無事死亡したので後日D言語で改めて解いたものをブログに残しておきます．
A問題
迷路をスタートからゴールまで行く．深さ優先探索という問題なので一応それで．迷路と言われたら普通最短解で幅優先な気がするけどTwitter見てたらUnion Findでも解けるみたいな意見を見て「？？？？？？」ってなってた．やり方が全く思いつかない．
import std.stdio; import std.range; import std.string; void main() { int H, W; readf("%d %d\n", &H, &W); string[] c; int[] s = new int[2]; foreach (int i, string line; stdin.lines) { c ~= line.chomp; foreach (int j, ch; line) { if (ch == 's') s = [ i, j ]; } } /** * ある地点に訪問済みかどうかを記録しておく配列 * 記録しておかないと同じ地点を永遠にさまよい続ける */ bool[][] visit = new bool[][](H, W); if (dfs(H, W, s[0], s[1], c, visit)) writeln("Yes"); else writeln("No"); } /** * 深さ優先探索で迷路を探索する * H: 高さ, W: 幅, h: 今いる場所の縦位置, w: 今いる場所の横位置 * c: 迷路 v: 記録シート */ bool dfs(int H, int W, int h, int w, string[] c, bool[][] v) { // 迷路からはみ出たらやめる // これを一番最初に弾いとかないと Range violation で実行時に落ちる if (h < 0 || H <= h || w < 0 || W <= w) return false; // 訪問済みだったらやめる if (v[h][w]) return false; // 壁だったらやめる if (c[h][w] == '#') return false; // ゴールに辿り着いたら成功 if (c[h][w] == 'g') return true; // 今たどり着いたマスをチェックしておく v[h][w] = true; // 上下左右のうちどれかがゴール = trueだったらいいので論理和を返す return dfs(H, W, h - 1, w, c, v) || dfs(H, W, h + 1, w, c, v) || dfs(H, W, h, w - 1, c, v) || dfs(H, W, h, w + 1, c, v); }
readf で改行を読み込み忘れたり，配列のサイズをコンパイル時に確保しといたのに実行時に ~= で追加して前の方に空白の要素が出来ちゃったりいろいろな凡ミスをしてしまった．いい加減流れを覚えたい．あと最初はスタックを使って書いてみたけど配列を適当に弄ったのでたぶんスタック配列からの取り出しとか追加に時間がかかってTLEで落ちた．関数の再帰呼出しに書き直したら普通に通った．でもスタックオーバーフローで落ちるのこわい．
B問題
N個ある要素をつなげたり，与えられた2つの要素が繋がっているかどうかの判定をしたりしたい．Union Findって今まで名前は知ってたけどどういうものか分からなかったので，今回のお陰で理論と実装が分かってよかった．応用の仕方は全く分からないので良い問題を教えてほしい．
import std.stdio; import std.range; void main() { int N, Q; readf("%d %d\n", &N, &Q); int[] uf = new int[](N); // 最初は各要素が自分を見るようにする // ref を付けないとコピーしたのを見てしまうので意味が無い foreach (int i, ref e; uf) { e = i; } foreach (q; iota(0, Q, 1)) { int p, a, b; readf("%d %d %d\n", &p, &a, &b); if (p == 0) { unite(a, b, uf); } else { if (find(a, b, uf)) writeln("Yes"); else writeln("No"); } } } bool find(int a, int b, int[] uf) { return (root(a, uf) == root(b, uf)); } // 引数で受け取ったUF木を直接いじりたいのでrefを付ける void unite(int a, int b, ref int[] uf) { int x = root(a, uf); int y = root(b, uf); // もし根が違ったら根どうしを繋げる if (x != y) uf[x] = y; } int root(int x, int[] uf) { // 自分自身を参照しているところが根 if (uf[x] == x) return x; else // 代入しながら再帰することで，途中経過で参照したノードを全て // 根に繋げることができる // 例：uf[2] = uf[5] = uf[3] = uf[4] = 4 // で，2と5と3がこれ以降直接4を見てくれるようになる return uf[x] = root(uf[x], uf); }
C問題は脳が途中で理解しようとする努力をやめてしまいました．南無三．
D言語でdubを叩いてMySQLに接続する
D言語でもMySQLしたい！
Rubyで書いたプログラムが結構非現実的な時間を返してきたのでD言語にポートしてみました（結果だけ言うとDのほうが遅くて悲しい気持ちになりました（コードの書き方が悪かったのかもしれないけど））．
当然MySQLライブラリを使う必要がありますが，D言語にはDUBというRubyで言うbundlerのような便利ツールがあるのでそれを使ってみました．DUBのHPはここ
Find, Use and Share DUB Packages - DUB - The D package registry
Macの場合はHomebrewにdubが入っているので brew install dub で入ります．そうでなくてもOSごとにprecompiled binaryが用意されています．優しい世界．入れたら，リポジトリディレクトリを作りたいディレクトリに移動して dub init [リポジトリ名] します．
$ dub init hoge Successfully created an empty project in '/home/nagoyan/Documents/hoge'. $ cd hoge $ ls -a . .. .gitignore dub.json source
.gitignore には既に .dub や *.o，*.obj などバージョン管理から除外すべきファイルが入力されています．dub.json にリポジトリの情報や依存パッケージをJSONで入力します．今回はdubのサイトでmysqlでヒットした3件のうち一番単純に使えそうな Package mysql-d version 0.3.1 - DUB - The D package registry を使うことにするので，dub.json に
{
...
"dependencies": {
"mysql-d": "~>0.3.1"
}
}
と入力します．サイトに載っている例では特定のバージョンを持ってくるようにしていますが，常に最新のものが欲しければ，バージョンに当たる部分に ~master と書けば最新のコードが降ってきます．
source/app.d に，エントリポイントである main 関数を書きます．これはinitした時に既に以下の様な内容で作成されています：
import std.stdio; void main() { writeln("Edit source/app.d to start your project."); }
dub build で，リポジトリ内のソースコードをビルドしてくれます．依存パッケージはこの時ダウンロードします．が，この時なぜかdubがldconfigのキャッシュを無視して /usr/lib64/mysql を見てくれなかったので，dub.json のトップレベルに "lflags": ["L/usr/lib64/mysql"] を追加します（実はこの作業はもともとCentOS上でやっていました）．
$ dub build Target mysql-d 0.3.1 is up to date. Use --force to rebuild. Building hoge ~master configuration "application", build type debug. Compiling using dmd... Linking... $ dub > $ dub Target mysql-d 0.3.1 is up to date. Use --force to rebuild. Target hoge ~master is up to date. Use --force to rebuild. Running ./hoge Edit source/app.d to start your project.
最後のメッセージは app.d の中の writeln に書かれているやつです．あとは app.d をゴニョゴニョするだけ．mysql-dのページのREADMEに使用例が書かれているのでそれを真似するだけ．インスタンスを1個作って，query 関数の引数にSQLを書く．可変長引数でSQLの ? を使ったバインディング機構にも対応しています．SELECT などの結果が返ってくるタイプのクエリではMysqlResultというクラスのインスタンスが返ってきます（そうでないCRUD操作でも返ってくると思いますが）．このクラスはforeach range要件を満たしているので，foreachに渡すことでMysqlRowというクラスのインスタンスを1個ずつ渡してくれます．MysqlRowは文字列として出力してやるとただの文字列配列のように見えますが，内部でカラム名と値の位置をマッピングしているため，数値の添字だけでなくカラム名でも要素にアクセスできます．
MySQLサーバとの接続を終了する時に .close とかしなくていいの？ と思って調べてみたのですが， https://github.com/Paxa/mysql.d/blob/master/source/mysql/mysql.d#L122-L124 を見るとデストラクタの中でやってくれているようなので書かなくても大丈夫そうです（安易にこういうこと書くと刺されそうですが）．
参考
Problem linking mysqlclient when compiling mysql-d - RejectedSoftware Forums
備考：LDFLAGSを追加しないと……
以下のような結果が返ってきます．これを解決するのに一番時間がかかった．
$ dub build Target mysql-d 0.3.1 is up to date. Use --force to rebuild. Building hoge ~master configuration "application", build type debug. Compiling using dmd... Linking... /usr/bin/ld: cannot find -lmysqlclient collect2: ld はステータス 1 で終了しました --- errorlevel 1 FAIL .dub/build/application-debug-linux.posix-x86_64-dmd_2067-D139BA4168D82F8FB70F3EB71271D775/ hoge executable Error executing command build: dmd failed with exit code 1.
PRML 演習2.6 モードの導出
ベータ分布は の時凸関数っぽいから微分して0になる時でだいじょぶっしょウェイみたいな感じで．
ということで，最後のなんちゃら = 0 のところを何とかして μ = なんちゃらにしたい．
何とかなりました．
