TopCoderのマラソンマッチは大きく以下の二つの形式に分類することができます。 最適化 機会学習 何れの形式のマッチもそれぞれの魅力的がありますが、今回は特に最適化に主眼を置いたマッチを題材にお話しをします。最適化を主眼においたマッチがどのような…

異なるn個のものから異なるk個のものを選ぶ組み合わせは以下のように計算することができます。階乗を使うとより簡潔に書くことができます。とてもシンプルに見えますよね。しかし、計算機で組み合わせの計算を行うのは意外と厄介なのです。階乗はとても大き…

Past, Present and Future コンテスト中に自分のブログから該当するエントリを探す作業をよくしていることに気付いたので、インデックスを作成しておくことにした。 Google Code Jam 2012 Round 1A Kingdom Rush std::sort()のコンパレータオブジェクトにつ…

定理を素早く思い出したりするために自分にとっての「定型」の問題を用意しておくことがままあります。例えばベイズの定理の場合。「囚人問題」や「モンティホール問題」が特に有名なので、それを「定型」としている方もいらっしゃるのではないでしょうか。 …

SRM 611 Div II http://community.topcoder.com/stat?c=round_overview&er=5&rd=15844SRM 611 Div Iに参加。戦績は惨憺たるものだった。SRM終了後に@nico_shindanninさんのTopCoderでプログラムしてみた 第2060回(SRM611 直後放送)を視聴。そこで解説されて…

Rを使うようになってきた最大の動機はR自身で柔軟にデータを作成できることにあります。例えば、パッケージユーザーのための機械学習(1)：決定木 - 銀座で働くデータサイエンティストのブログでは以下のようなXORパターンのデータを用いて決定木の解説を行っ…

構文的な一貫性をなかなか感じられないのでRを敬遠していました。しかし時勢には敵わず、使用頻度が増えてきました。どうせやるのであれば手が増えたほうがよいので、スニペットを多数作成し検証しています。気付いたことをブログに少しずつまとめようかと思…

回文に関連する実装が苦手です。回文について考えなければならないときはいつも気が重かったのですが、与えられた文字列から回文となる部分文字列を列挙する方法を@nico_shindanninさんがニコニコ生放送で解説していらっしゃいました。とても分かりやすい解…

STLやPythonで範囲指定の多くは左閉半開区間を基調にしています。しかし、std::string::substrでの範囲指定は大きく異なり、戸惑います。気が付くと実装時に繰り返し同じことを考え、無駄を感じていたのでまとめてみました。 以下はstring::substr - C++ Ref…

エラトステネスの櫛はN以下の素数を列挙するアルゴリズムとして知られています。まずは素数を列挙するナイーブな実装を行い、計算量を落としていきながらエラトステネスの櫛を考えてみることにします。次の実装の計算量はO(N2)です。 #include <iostream> #include <vector> #d</vector></iostream>…

素数を扱う簡単なアルゴリズムはO(√n)で行えます。以下の何れのアルゴリズムもO(√n)で行うことができます。 素数判定 約数の列挙 素因数分解 プログラミングコンテストチャレンジブックでは二つの式を使って簡潔に説明をしています(p. 111)。例えばnの素因数…

Codeforces # 223 Div. 2 http://codeforces.com/contest/381Codeforces # 223 Div. 2に参加。ABCが通り、2,492点。94位。部屋(Room 74)でも初めて1位となり、嬉しい回であった。レートは1,621から1,720へ。紫コーダーになった。今回のエントリではstd::lowe…