!

Idiom: Partial Sorting

書庫から久しぶりに取り出したEffective STLをパラパラめくっていて、std::partial_sortのうまい用法を学びました(第31項「ソートの選択肢を知っておこう」)。昇順に整列して初めから20番目の要素までの合計を取りたいときにはstd::sortを使うより、std::par…

Multi-start Breadth First Search

先日参加したコンテストで以下のような問題が出題されました1。 シンプルなグラフがある。それぞれの頂点は最大で100個ほどのグループに分けられている。各頂点から各グループの頂点までの最短距離を求めよ。ただし、頂点の最大数は\(10^{5}\)である。 この…

Idiom: Enumerate ranges that decrease(but not strictly)

コンテストに参加していると、数列の部分的に降順になっている区間を列挙することを求められることがままあるのですが、苦手意識がありました。図でいえば、[4, 9]、[18, 21]、[23, 24]を列挙することです。 この小問題、自分にはなかなか難しいものでした。…

Finding Distance Between Two Nodes of a Binary Tree

yambe2002さんの記事に面白い問題が掲載されていたことをふと思い出して、考えてみました。 バイナリツリーの2ノード間の距離を求めるメソッドを作成せよ こちらは所謂「ホワイトボードコーディング」で出題された問題だそうです。つまり、面接の問題です。 …

Idiom: Cumulative Summation Summary

累積和を実装するとき、いつもインデックスの扱いに悩んでしまいます。これが結構時間を喰うので 、しっかりイディオムとしてまとめようと思いました。 例えば0-indexの配列、\(a_i\)があるとします。 $$ \begin{array}{c|ccccc} i & 0 & 1 & 2 & 3 & 4 & 5\…

Idiom: Check if given string starts with some string

std::stringとして与えられた文字列がある特定の文字列から始まるかどうかを記述するのは簡単なことのように思えます。これが自分にとっては意外に難しく、いつも時間を割いてしまうのです。先日、コードリーディングをしていた際にうまい方法を見つけたため…

Redirecting Contents of File to Standard Input

1行シェルスクリプトとEmacsで極力物事を済ます方針になって久しいのですが、コンテスト中は時間がないので多少のスクリプトを用意しています。先日コンテスト中にこんなスクリプトがあったらいいなあ、と考えついたので早速作成しました。 Emacsでテキスト…

Idiom: Calculating Power of 10 using pow Function in Integer Arithmetic

今日参加したコンテストで有効な電話番号の組み合わせ数を求める問題が出題されました。実装ではlong longの大きな値、例えば\(10^{17}\)から小さな値、例えば10や1を引く演算を行う必要がありました。 powを使って10の冪乗を計算する解法も少なくなかったの…

Series of Xor Arithmetics

先日参加したコンテストにこんな問題が出題されました。排他的論理和を使う問題です。 nとxが与えられる。n個の異なる整数のビットごとに排他的論理和を取ってxとなるようにしたい。n個の非負整数を出力せよ ただし、1 ≦ n ≦ 105、0 ≦ x ≦ 105とし、出力する…

Idiom: Getting the largest number that is less than x

Idiom: Getting the largest number that is less than x プログラムを書いているとき、思ったことが思った計算量でできることは分かっているのに細かい処理がパッと書けないことってありますよね。今日はこの問題を解いているときに、「std::mapのキーがx未…

To a better understanding of the Otsu’s method

大津の方法の最も有名な応用例として画像の2値化が挙げられます。この応用での圧倒的ともいえる知名度とその貢献度からか他の問題(例えば機械学習)への応用に関して明示的に言及されることが少ないですが、英語版のWikipediaの記事に記載されているように、…

Precalculating a Combination

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

Recalling Bayes' Theorem

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

How to Find Palindromic Substrings?

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

Understanding How std::string::substr works

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

Implementing Sieve of Eratosthenes

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

Telling If a Number is Prime

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

Markov's inequality and 0-1 random variables

Xを非負の確率変数としたとき、任意のa > 0に対してが成り立ちます。この不等式はマルコフの不等式として知られており、確率変数の値がある正の定数以上になる確率の上限を与えます。Markov's inequalityではこの不等式の興味深い応用例を紹介しています。 A…

Proving linearity of expectations

期待値の線形性は期待値の重要な性質の一つです。任意の確率変数の和の期待値は個々の確率変数の期待値の和と等しい、というものです。この性質を用いると期待値の計算を極めて簡単化することができます。例えば確率変数XとYの和の期待値E[X + Y]はそれぞれ…

Calculating binomial distribution

計算機を使って確率を考えるのは楽しいことです。特に、実装が考察した通りの結果であったときは嬉しいものです。しかし、確率を計算するのに予期しない工夫を求められることもあります。例えば二項分布の計算はそれほど簡単ではないことが知られています。…

Expectation of a binomial random variable X

数学を考えるとき、公式を自分で導くことができると有利であることが多いように感じます。そのため、自分の感覚と合う計算方法と出会えたときは嬉しいものです。例えば確率pで成功する実験をn回独立に行うことを考えてみましょう。成功する回数を確率変数Xで…

How does the product of uniform variates distribute?

id:practicalschemeさんの珠玉のエントリ、なんでも継続は以下のような一説から始まります。 プログラミングの世界の概念には、禅の公案のようなものがある。 それを説明する文章はほんの一文なのに、最初に目にする時、 その文は全く意味をなさない、暗号の…

Understanding how sed works(1)

テキストデータを加工するとき、sedは欠くことの出来ないツールです。しかし、sedが改行を読み込まないことはあまり知られていません。例えば、入力に含まれる改行を全て削除するために以下のようなスクリプトを記述したとしましょう。 $ sed -n -e 's/\n//g…

Visualizing Roundings

数値計算のプログラムを行うとき、端数処理に関して繰り返し調べていることに気が付きました。負の数の扱いや絶対値を伴った計算は意外に複雑で、気が付くとWikipediaのRoundingやFloor and ceiling functionsを何度も訪れていたり...そこで備忘録として、切…

Visualizing Memoization and Dynamic Programming(2)

前回のエントリでは、3003 -- Spiderman’s workoutの解法としてメモ化再帰を解説しました。今回のエントリではこれを元に、動的計画法を解説します。 まず、前回のエントリにて実装したsearch関数を見てみましょう。 #define INT_INF 999999 int memo[40+1][…

Visualizing Memoization and Dynamic Programming(1)

昨年のSIGGRAPH参加後、9月ほどからでしょうか。アルゴリズムに関する知識と実装する力を基礎から鍛え直す衝動にかられ、北京大学のJudge Online(以下POJ)に参加するようになりました。現在のAC数は123問とまだ少ないですが、一つ一つの問題を解くごとに発見…

Symbol Font on PostScript

PostScriptにはSymbolというフォントが用意されています。ギリシャ文字を用いるにはこのフォントを使用します。例えば、πを出力するには以下のようにします。 /Symbol findfont 10 scalefont setfont 0 0 moveto (p) show文字は8進数数値としても与えられる…

Parse Tree Dynamic Visualization

多忙だったこともあり、久しぶりのエントリとなってしまいました。さて、Gmailのメッセージ検索にはダッシュ(-)、OR演算子および括弧が用意されています。これらの演算子は大変便利で、強い依存性があるように思います。それぞれの演算子の用法は大変簡潔で…

How Breadth First Search uses Queue

先日のエントリにて、幅優先探索を用いたダイクストラのアルゴリズムを考察しました。今回は、幅優先探索が如何にキューを用いるかをまとめてみました。名著アルゴリズムCでは、幅優先探索はレベル順(level-order)の走査として、第1巻第4章、木の章にてごく…

Visualizing Dijkstra's, and A* Search Algorithm

先日話題になっていた最短経路探索問題を考察するにあたり、探索回数を如何に減らすかを主眼において考えてみました。それに伴い、いくつかの可視を行いました。 ダイクストラのアルゴリズムを伴った幅優先探索において、すでに訪れた節点を再度訪れる場合と…