「ネタ」の記事一覧（4 / 12ページ目）

ひとりで勝手にはじめた蟻本読書会 フェニック木 BIT（Binary Indexed Tree） 蟻本読書会 の続きです。 巡回セールスマン問題は、複数の決められた地点を巡回して元の位置に戻る際、どう回れば最も移動距離が・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 セグメント木 遅延評価セグメント木で区間の総和・最大値（最小値）を素早く計算する の続きです。 フェニック木とセグメント木の違い Binary Indexed Tree（BIT 別名 フ・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 座標圧縮 領域の個数 蟻本読書会 の続きです。 セグメント木とは？ セグメント木は、固定長配列にいくつかの操作を加えたデータ構造です。セグメント木は、基本的には以下の操作を時間計算量 O・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 半分全列挙 全探索を高速化するテクニック 蟻本読書会 の続きです。 座標圧縮とは数列 A[0], A[0], …, A[N-1] が与えられたときに、それぞれの要素が全体の中で何番目に小・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 反転 (ライツアウト) 蟻本読書会 の続きです。 全探索では全通り直接的に探索を行うので、対象の数が増えると計算量は指数関数的に増えてしまいます。半分全列挙とは、半分ずつのグループに分け・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 しゃくとり法 最大区間・最小区間 数え上げ 蟻本読書会 の続きです。 ライツアウトは、5×5の形に並んだライトをある法則にしたがってすべて消灯 (lights out) させることを目的・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 二分探索法 平均の最大値を求める 蟻本読書会 の続きです。 しゃくとり法は区間の左端と右端を尺取り虫のように動かすことで、条件を満たす区間を高速に見つけるアルゴリズムです。条件を満たす連・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 二分探索法 可能となるような最大値・最小値を求める 蟻本読書会 の続きです。 基本問題 二分探索法は平均最大化する問題を解くときにも使えます。 効率よく盗もう (paizaランク A 相・・・

続きを読む

ひとりで勝手にはじめた蟻本読書会 二分探索法 lower_bound と upper_bound 蟻本読書会 の続きです。 ～を満たす最大値（または最小値） 二分探索法でパイプを切る問題を解くにもあるように、「～を満たす・・・

続きを読む

二分探索法とは？ ソート済み配列に対する探索アルゴリズムの一つです。中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して検索していきます。この方法は先頭から順番に比較・・・

続きを読む