Algorithm

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

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未…

Precalculating a Combination

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

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の素因数…

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問とまだ少ないですが、一つ一つの問題を解くごとに発見…

Parse Tree Dynamic Visualization

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

Oriented Bounding Box using Covariance Matrix

まとまった時間があったので、共分散行列(Covariance Matrix)を用いた主成分分析(Principal Component Analysis)にて生成した有向バウンディングボックスのデモをGoogle Gadgetsを用いて書いてみました(有向バウンディングボックスについては、過去のエント…

How Breadth First Search uses Queue

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

Visualizing Dijkstra's, and A* Search Algorithm

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

Finding Shortest Path using Breadth First Search Algorithm

面白い問題があったので解いてみました。問題の詳細は、出題者さんのエントリでご確認ください。 さて試験問題です。内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。 人生を書…

Consistent Binary Tree Layout(3)

算術式を記述するにはいくつかの方法があります。算数、数学に使われる中値記法はその一つです。中値記法は、英語ではInfix Notationと表記されます。計算機で使用される言語では、数学のように大括弧(bracket)、中括弧(brace)、括弧(parenthesis)を使い分け…

Consistent Binary Tree Layout(2)

先日のエントリにて、一貫した二分検索木の可視を行うアルゴリズムについて記載しました。また、木構造、特に二分木や二分検索木と親和性が高い、通りがけ順について説明しました。以下は、通りがけ順にてkd木を走査する様子を可視したものです。さて、木の…

Consistent Binary Tree Layout(1)

名著アルゴリズム Cの特筆すべき点の一つとして、可視の美しさが挙げられます。特に二分木の可視は美しく、計算されつくされた様にいつも唸らされます。以下は、アルゴリズム C 第2巻の14章、初等的な検索法の章に掲載されている二分木の可視です。この木は9…

Axis Aligned Rectangle Intersection and Projection Technique(3)

さて、先日までのエントリにて矩形と射影について各々解説しました。今回のエントリでは、射影を応用した矩形の交差判定について記載したいと思います。早速、以下のようなAとBの二つの矩形の交差判定について考えてみましょう。先日のエントリにて解説した…

Axis Aligned Rectangle Intersection and Projection Technique(2)

先日のエントリでは、矩形の交差判定を行う際の用語の紹介を行いました。今回のエントリでは、射影(Projection)という技法を紹介します。一見、射影は単純なことを難しく表現しているだけに感じられるかもしれません。しかし、計算幾何や領域検索を考えるに…

Axis Aligned Rectangle Intersection and Projection Technique(1)

先日のエントリではマンハッタン幾何を紹介し、総当たりによる実装を行いました。その際、水平と垂直の線分を縮退した矩形とみなし、交差判定を行いました。今回のエントリでは、矩形の交差判定アルゴリズムを考えるための用語の解説を行います。また、次回…

Solving Manhattan Geometry(1)

先日kd-treeについてのエントリを記載したことは、自分にとって計算幾何の面白さを再認識する良い機会となりました。計算幾何で用いられる幾何学的アルゴリズムは比較的若く、今でも進化の過程にあります。また、人間には単純に見える問題も計算機にとっては…

Selecting median using Quick Select Algorithm(2)

先日のエントリに引き続き、Quick Selectアルゴリズムについて考えてみたいと思います。Quick Selectアルゴリズムを考えるに至った動機は、メディアンを選択することでした。今回は以下の9個の要素を持つ配列を使って考えてみましょう。ここでは、配列のイン…