アルゴリズム関連

アルゴリズムを設計するために役立つ考え方を設計技法

「後先のことを考えず、その場その場での選択を繰り返していく」 このような考え方を貪欲法と呼ぶ。

リサイズと初期化は別の処理

メモ化とは
メモ化は、一度計算した再帰関数の結果を配列などに保存しておき、再度同じ関数の計算が必要になった際はそこから参照するテクニック。 これによって、同じ関数の計算結果を何度も再帰呼び出しを用いて計算してしまうことを避けることができる。

貪欲法とは、 「後先のことを考えずにその場での最善の選択をしていく」 という方法論

見方を変えれば、貪欲法が通用するようになる。

貪欲方で、最善策を先頭から順に考えてできない場合は末尾から考えてみる

巡回セールスマン問題の最適解
参考：NP hardness (wikipedia)

貪欲法は常に最適解が得られるとは限らない

ビットセットを使うことのメリット

• コンピュータが高速に計算できる
• 複数の状態を 1 つの変数で一斉に管理できる

一般に、整数 N に右ビットシフトを行うと「 N/2 の小数点以下を切り捨てた値 」となる

一般に、最上位のビットが 1 でない(オーバーフローを考慮しない)整数 N に左ビットシフトを行うと「 N×2 」となる

A と 2 のi乗の排他的論理和 (XOR) を求めることによって、 A を二進数で表したときの i 桁目を反転させることができます。 具体的には、 二進数表記の i 桁目が 0 なら 1 に、1 なら 0 に変更することができます。i 桁目とは左から0桁目でカウントしたもの

AxorX=C という数式は、次のことを意味します。

二進法で表した整数値 A に対して、
二進法で表した整数値 X の 1 である桁について、0 と 1 を入れ替えると C になる

AxorX=C ⇔X=AxorC

DRY原則：同じものを繰り返さない
Don't Repeat Yourself

プログラムを書く際には「シンプルなもののほうがよい」という原則を KISS 原則
KISS とは Keep It Simple Stupid の略で、「シンプルで愚鈍にする」などと訳される。

可変長配列は末尾に値を追加することが得意だ(早い)が先頭に値を追加することは苦手(遅い)

先頭要素の挿入/削除、末尾要素の挿入/削除を得意とするデータ構造にはデックまたは両端キューが挙げられる。

うさぎでもわかる配列と連結リスト

周囲 4 マスを全探索する方法については、

dx = {1, 0, -1, 0} や dy = {0, 1, 0, -1}

と元のマスからの差分を表す適当な配列を作り、d=0,1,2,3 についてマス (x+dx[d],y+dy[d]) をチェックする方法などが考えられる。

比較対象の変数を左辺にして x > 0 と書くほうが、わかりやすいとされることが多い

一般に、条件式は肯定文で書くほうが、意図がわかりやすいプログラムになる場合が多い

与えられた配列以外の記憶領域が不要 (in-place であるという)

バブルソート

• 最悪時の計算量は O(N^2)
• 平均時の計算量は O(N^2)
• 最良時の計算量は O(N)

関数は早めに抜けれるのであれば抜けるようにする

ソートされた配列に対して二分探索することで、計算量を減らすことができる。
全探索：O(N)
二分探索：O(logN)

二分探索の考え方

正規表現とは、特定の文字列パターンを「メタ文字」と呼ばれる特殊な文字と「リテラル」と呼ばれるそれ以外の普通の文字を用いて表現する方法

正規表現を用いると文字列から特定の文字列パターンを検出できるが、検出する文字列パターンは、考えられる候補のうち先頭の文字が最もはやく出てくる最も長い文字列

c++で正規表現を扱う

lower_bound (C++)

取りうる値を添え字に持つ配列を バケット (bucket) と呼ぶ

正規表現の先読み後読み、アンカー

競プロで出がちなREの原因をまとめる