!
文字列\(s\)から反転した文字列\(t\)を作成するとき、これまではコピーして反転という処理をしていました。 std::string s("string"); : std::string t(s); std::reverse(ALL(t)); // tの内容は"gnirts"となる 今日なんとなくこの実装を見て目から鱗が落ちま…
std::multisetをstd::priority_queueの代わりに使う実装例を目にしました。std::priority_queueは重いと言われているし、std::multisetのほうが性能がよいのであれば使う価値があるな...と考えて計測してみたところstd::priority_queueよりも3倍重く少しがっ…
縮約を伴ったUnion-Find木は高速に動作することで知られています。以下は蟻本からの抜粋です。 // 木の根を求める int find(int x) { if (par[x] == x) { return x; } else { return par[x] = find(par[x]); } } // xとyの属する集合を併合 void unite(int x…
書庫から久しぶりに取り出したEffective STLをパラパラめくっていて、std::partial_sortのうまい用法を学びました(第31項「ソートの選択肢を知っておこう」)。昇順に整列して初めから20番目の要素までの合計を取りたいときにはstd::sortを使うより、std::par…
先日参加したコンテストで以下のような問題が出題されました1。 シンプルなグラフがある。それぞれの頂点は最大で100個ほどのグループに分けられている。各頂点から各グループの頂点までの最短距離を求めよ。ただし、頂点の最大数は\(10^{5}\)である。 この…
コンテストに参加していると、数列の部分的に降順になっている区間を列挙することを求められることがままあるのですが、苦手意識がありました。図でいえば、[4, 9]、[18, 21]、[23, 24]を列挙することです。 この小問題、自分にはなかなか難しいものでした。…
yambe2002さんの記事に面白い問題が掲載されていたことをふと思い出して、考えてみました。 バイナリツリーの2ノード間の距離を求めるメソッドを作成せよ こちらは所謂「ホワイトボードコーディング」で出題された問題だそうです。つまり、面接の問題です。 …
累積和を実装するとき、いつもインデックスの扱いに悩んでしまいます。これが結構時間を喰うので 、しっかりイディオムとしてまとめようと思いました。 例えば0-indexの配列、\(a_i\)があるとします。 $$ \begin{array}{c|ccccc} i & 0 & 1 & 2 & 3 & 4 & 5\…
std::stringとして与えられた文字列がある特定の文字列から始まるかどうかを記述するのは簡単なことのように思えます。これが自分にとっては意外に難しく、いつも時間を割いてしまうのです。先日、コードリーディングをしていた際にうまい方法を見つけたため…
1行シェルスクリプトとEmacsで極力物事を済ます方針になって久しいのですが、コンテスト中は時間がないので多少のスクリプトを用意しています。先日コンテスト中にこんなスクリプトがあったらいいなあ、と考えついたので早速作成しました。 Emacsでテキスト…
今日参加したコンテストで有効な電話番号の組み合わせ数を求める問題が出題されました。実装ではlong longの大きな値、例えば\(10^{17}\)から小さな値、例えば10や1を引く演算を行う必要がありました。 powを使って10の冪乗を計算する解法も少なくなかったの…
先日参加したコンテストにこんな問題が出題されました。排他的論理和を使う問題です。 nとxが与えられる。n個の異なる整数のビットごとに排他的論理和を取ってxとなるようにしたい。n個の非負整数を出力せよ ただし、1 ≦ n ≦ 105、0 ≦ x ≦ 105とし、出力する…
Idiom: Getting the largest number that is less than x プログラムを書いているとき、思ったことが思った計算量でできることは分かっているのに細かい処理がパッと書けないことってありますよね。今日はこの問題を解いているときに、「std::mapのキーがx未…
大津の方法の最も有名な応用例として画像の2値化が挙げられます。この応用での圧倒的ともいえる知名度とその貢献度からか他の問題(例えば機械学習)への応用に関して明示的に言及されることが少ないですが、英語版のWikipediaの記事に記載されているように、…
異なるn個のものから異なるk個のものを選ぶ組み合わせは以下のように計算することができます。階乗を使うとより簡潔に書くことができます。とてもシンプルに見えますよね。しかし、計算機で組み合わせの計算を行うのは意外と厄介なのです。階乗はとても大き…
定理を素早く思い出したりするために自分にとっての「定型」の問題を用意しておくことがままあります。例えばベイズの定理の場合。「囚人問題」や「モンティホール問題」が特に有名なので、それを「定型」としている方もいらっしゃるのではないでしょうか。 …
回文に関連する実装が苦手です。回文について考えなければならないときはいつも気が重かったのですが、与えられた文字列から回文となる部分文字列を列挙する方法を@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の素因数…
Xを非負の確率変数としたとき、任意のa > 0に対してが成り立ちます。この不等式はマルコフの不等式として知られており、確率変数の値がある正の定数以上になる確率の上限を与えます。Markov's inequalityではこの不等式の興味深い応用例を紹介しています。 A…
期待値の線形性は期待値の重要な性質の一つです。任意の確率変数の和の期待値は個々の確率変数の期待値の和と等しい、というものです。この性質を用いると期待値の計算を極めて簡単化することができます。例えば確率変数XとYの和の期待値E[X + Y]はそれぞれ…
計算機を使って確率を考えるのは楽しいことです。特に、実装が考察した通りの結果であったときは嬉しいものです。しかし、確率を計算するのに予期しない工夫を求められることもあります。例えば二項分布の計算はそれほど簡単ではないことが知られています。…
数学を考えるとき、公式を自分で導くことができると有利であることが多いように感じます。そのため、自分の感覚と合う計算方法と出会えたときは嬉しいものです。例えば確率pで成功する実験をn回独立に行うことを考えてみましょう。成功する回数を確率変数Xで…
id:practicalschemeさんの珠玉のエントリ、なんでも継続は以下のような一説から始まります。 プログラミングの世界の概念には、禅の公案のようなものがある。 それを説明する文章はほんの一文なのに、最初に目にする時、 その文は全く意味をなさない、暗号の…
テキストデータを加工するとき、sedは欠くことの出来ないツールです。しかし、sedが改行を読み込まないことはあまり知られていません。例えば、入力に含まれる改行を全て削除するために以下のようなスクリプトを記述したとしましょう。 $ sed -n -e 's/\n//g…
数値計算のプログラムを行うとき、端数処理に関して繰り返し調べていることに気が付きました。負の数の扱いや絶対値を伴った計算は意外に複雑で、気が付くとWikipediaのRoundingやFloor and ceiling functionsを何度も訪れていたり...そこで備忘録として、切…
前回のエントリでは、3003 -- Spiderman’s workoutの解法としてメモ化再帰を解説しました。今回のエントリではこれを元に、動的計画法を解説します。 まず、前回のエントリにて実装したsearch関数を見てみましょう。 #define INT_INF 999999 int memo[40+1][…
昨年のSIGGRAPH参加後、9月ほどからでしょうか。アルゴリズムに関する知識と実装する力を基礎から鍛え直す衝動にかられ、北京大学のJudge Online(以下POJ)に参加するようになりました。現在のAC数は123問とまだ少ないですが、一つ一つの問題を解くごとに発見…
PostScriptにはSymbolというフォントが用意されています。ギリシャ文字を用いるにはこのフォントを使用します。例えば、πを出力するには以下のようにします。 /Symbol findfont 10 scalefont setfont 0 0 moveto (p) show文字は8進数数値としても与えられる…
