本日 12/08 は Recruit Programming Contest というものに参加してきました。登録した時は他にネタを考えようと思っていた (研究で使っているコードの一部を解説するとか) のですが、これに参加することを決めたので他に準備できませんでした。
プログラミングコンテストというのは制限時間内に仕様に沿うプログラムを書くゲームです。AtCoder をはじめ、色々なプログラミングコンテストでD言語を使っている人が増えています。
A: 部分和
問題
非負整数のリストが与えられる。最上位の桁が同じ数字である数のみを足すことによって得られる和のうち最大のものを求めよ。
解答
最上位の桁は高々10個なので、和を全て求めて最大値をとればよい。first_digit なる関数を再帰で定義してループ1回で10個の和を求める。最大は reduce!max ですね。
B: ゴーストライティング
問題
テキストがいくつか与えられる。最初のものと平均単語長が最も近いものを求めよ。
解答
平均単語長は line.split().map!(a => a.length) してから reduce!((a, b) => a + b) / length すれば OK 。
どう書こう?
いくつかの候補 x[i] から、ある関数 f による評価 f(x[i]) が最小 (最大) になるものについて、g(x[i]) を求めるという問題は多い。状態変数を持ってループで回しているが、もっといい書き方はないだろうか?
C: DivMultSub
問題
カードを順に引いていくゲームがある。勝者のスコアを求めよ。
解答
素直にシミュレーションすればよい。label つきループの break label; や std.bigint : BigInt, そして foreach より細かく制御できる empty-front-popFront トロイカを使った。
D: 重なり合った矩形
幾何あんまり得意じゃない。スキップ。
E: 期待リスク
問題
戦闘ゲームがある。終了時に残る自分の兵士の期待値を求めよ。
解答
(自分の残り兵士の数, 相手の残り兵士の数) を引数にした関数の std.functional : memoize で OK!
しかし…
しかし関数内の関数を memoize しても、親の呼び出しを通じて共通の memo が使われてしまうという仕様のため、std.functional : memoize をそのまま使うことはできない。と思って自分で memo を書いた。が、実はこの問題では単に memoize でよかった。
memoize と関数内関数との相性を良くする方法は k3_kaimu 氏によるシンプルな実装 がある。
F: ホットキーとコールドコール
問題
いくつかの単語が与えられる。すべての単語が同じ行の文字で構成されるようなキー配列が存在すれば求めよ。
解答
同じ単語に含まれる文字は同じ行にならなければならない。これは Union Find を使う。のが普通だが、そうではない実装で char[] を sort して uniq しようとしていたらコンパイルエラーに。Union Find で回避できたが、どの文字集合をどの列に割り当てるかを探索する方法が思い浮かばなかったので正解できず。
char[] は sort できない
mono_shoo さんが教えてくれたところ によると、char[] は1要素が1文字に対応しているとは限らないため無造作には sort できないことになっているとのこと。to!dchar[] または cast(ubyte[]) を経由すれば sort できる。
G: ACME Puzzle Box
問題
完成したパズルを接着して保管したい。接着コストは接着部分によって異なる。必要最小限の接着コストを求めよ。
解答
最小全域木だ! ということはわかったが実装が間に合わず終了。
H: 冷たいマシン
手も足も出ず。
結果
4問正解で144人中65位。
結論
より「D言語らしい」コードを目指すために、D言語erの方々はぜひ競技プログラミングで活躍して手本を見せてください!