何らかの目的があって複数のシェルスクリプトを書き殴る必要があるとき、Makefileにシェルスクリプトをガシガシ埋め込んでいくことが多いです。偽のターゲット(Phony Target)でmakeをラウンチャのように使えますし、ファイルの依存関係も見てくれます。並列…
昨日、簡単なシェルスクリプトを書いていたとき、「grepはマッチする行が1行でもあれば真を返すのであった。はて、grep -vの戻り値はどういう条件で真になるんだろう? また、grep -v -e a -e bなどといったように、条件が複数指定されているときはどうなるの…
文字列\(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の記事に記載されているように、…
SRM 535 Div II 初参加したSRMにて惨敗した問題に挑戦。今でも自分には中々難しく、35分ほど時間を要した FromAndGCDLCM 未知の数AとBの最大公約数と最小公倍数、GとLが与えられる。ここからAとBを推測し、その最小の和(A + B)を返す問題 最大公約数Gと最小…
SRM 653 Div I http://community.topcoder.com/stat?c=round_overview&er=5&rd=16317SRM 653 Div Iに参加。制限時間一杯Easyを考えるが、全く手が出ず。SRM後に幾つかの実装を読み、全く考えもしていなかった問題に還元できることを学んだ。グラフの問題であ…
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を敬遠していました。しかし時勢には敵わず、使用頻度が増えてきました。どうせやるのであれば手が増えたほうがよいので、スニペットを多数作成し検証しています。気付いたことをブログに少しずつまとめようかと思…
