class Array def bsearch(v) l = -1 r = size while r - l > 1 m = (l + r) / 2 self[m] >= v ? r = m : l = m end self[r] == v ? self[r] : nil end def bsearch_index(v) l = -1 r = size while r - l > 1 m = (l + r) / 2 self[m] < v ? l = m : r = m e…

1 2 3 4 5ここにある数字を好きに組み合わせて足していき、目標となる値を作れるか？ そんな問題を「部分和問題」という。9を目標の数とする場合 1, 3, 5 2, 3, 4 4, 5 目標の数となる組み合わせはいくつかあり、その中でも4, 5が手っ取り早い。 このような …

yukari yukkuriある二つの文字列がある。 この二つを全く同じ文字列にするのに、一文字ずつの挿入・削除・置換を行う。 それらの操作は最小で何回だろうか？ このような「最小操作回数」のことを「編集距離」*1と呼ぶ。バージョン管理や分析、つまりは差分や…

10になるカードの組み合わせはある？数字の書かれたカードが並んでいる。 この中から好きなカードを選び、書かれた数字の合計が10になる組み合わせは存在するか？ このような「部分和問題」を「動的計画法」を使って効率よく解く方法を考える。 部分和問題を…

どれを持ち帰る？冒険者が旅の途中、たくさんの宝物を見つけました。 しかし、持ち帰れるのは8kgまでです。 持ち帰る宝物の価値が最も高くなるには、どれを持ち帰ればいいのか。 それを知るべく我々はアマゾンの奥地「動的計画法」の奥地へ向かった・・・。 …

全探索では解けないような難しい問題を解くのに欠かせない「動的計画法」について考える。 動的計画法とは 「フィボナッチ数列」の計算 愚直な計算 動的計画法を使う計算 実装 Non-DP DP(メモ化再帰) DP(ループ) →②「ナップサック問題」 動的計画法とは そも…

前置き Win32APIの概要 Rubyの「Win32API」クラス Win32APIで出来ること 実装 解説 Win32APIクラスの初期化 関数の呼び出し キーの押下判定 まとめ おまけ(役立ちそうなリンク) 前置き RGSS3みたいな「ゲーム系のアプリケーションでキー入力を取得したい」 …

何かと便利だけど何かと忘れがちな「正規表現 / Regexp」のお話。 書き方も色々あるが、自分が使う書き方だけ書いてく。 基本の使い方 任意文字にマッチ キャプチャ 文字列の置き換え 普通に表示できない文字を分ける 擬似的に半角文字、全角文字を分ける パ…

※古いRuby(1.9)のお話、新しいバージョンではマイナス乗とか気にしなくていい！目次 前置き 改善 結論 余談 前置き n = 10 2 ** n 2のn乗。オーソドックスな書き方だ。 しかしRubyにおいて2のn乗を普通に書くのは 速度的にはあんましえらくない。とされてい…

三番煎じぐらい（コッチヲ見ロォ～！） 参考にパクらせて頂きました、ありがとうございます（爆）mametter.hatenablog.comobelisk.hatenablog.com目次 前置き RGSS3の仕様 pngの構造 チャンクの構造 IHDR データ IDAT データ IEND データ 仮実装(テストコー…

目次 前置き 二分ヒープを使ってみよう 二分ヒープの速度 実装 変数の解説 @node @count メソッドの解説 push(v) shift swap(i, j) min 検証 機能追加 まとめ 前置き 配列内のもっとも小さい要素を求めるコード。 array = [0, 1, 2, 3, 4] array.min .minメ…

Rubyのプログラムを書くときに 心に留めておくだけで速いコードが書けるかもしれない（？）三つのポイント注意点 Ruby1.9での検証。新しいバージョンでは要らなくなってるかも 筆者は競プロ勢でもなんでもないただの一般ﾋﾟｰﾎﾟｰ もっといい書き方があるかも …