トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

数え上げ問題

[アルゴリズム]

競技プログラミングも頑張ってやっていく。若いものには負けないぞ!

  • アルゴリズムなどで調べたものはここに書いていく

問題 - 1 から n までの数の中から、重複無しで3つの数を選びそれらの合計が x となる組み合わせの数

  解法1 - Finding all possible combinations of numbers to reach a given sum

愚直な手順(ナイーブな解法とか煽られるやつ)

アルゴリズム

 This problem can be solved with a recursive combinations of all possible sums filtering out those that reach the target. Here is the algorithm in Python:

この問題は全ての和の組み合わせを再帰的に解き、目標の数に一致したもの以外をフィルタリングすることで解くことができます。

処理フロー
引数に対象の数列N、目標X、部分配列Pをとる関数subset_sumを作成する
  1. subset_sumに初期値N、X、空の部分配列を入れて開始
  2. この時点での合計値 S = 配列Xの合計値 で計算する
  3. S=Xかどうか検査
    1. S==X であれば、その部分配列Pを記録して4へ進む
    2. S>=X ならば、プログラム終了
    3. S<Xであれば4へ進む
  4. 数列Nの長さiを取得してループを開始、i = 0 〜 iまで以下を繰り返す
    1. n = 数列Nのi番目の要素とおく
    2. 配列R = Nのi+1番目以降の全ての要素とおく
    3. 配列TR = 配列P の末尾に n を連結したものとおく
    4. 関数subset_sumに引数としてR, X, TR を渡して実行
メモリ制限に引っかかる
これではダメです…でも一応nCrの組み合わせの出し方は書いておく → Javaで簡単な組み合わせの総数 nCr を求めてみる

  解法2 - Given an array A[] and a number x, check for pair in A[] with sum as x

アルゴリズムA

 Time Complexity: Depends on what sorting algorithm we use. If we use Merge Sort or Heap Sort then (-)(nlogn) in worst case. If we use Quick Sort then O(n^2) in worst case.

時間計算量:これは我々がどのようなソートアルゴリズムを使っているかによる。マージソートやヒープソートをつかっている場合最悪でも (-)(nlogn) となる。クイックソートをつかっている場合は、最悪でも O(n^2) になる。

 Auxiliary Space : Again, depends on sorting algorithm. For example auxiliary space is O(n) for merge sort and O(1) for Heap Sort.

空間計算量:これも、我々がどのようなソートアルゴリズムを使っているかによる。例えば空間計算量はマージソートならばO(n)、ヒープソートならばO(1)になる。

処理フロー
引数に対象の数列A、配列サイズar_size、その和sumをとる関数hasArrayTwoCandidatesを作成する
  1. 配列Aを昇順でソートする
  2. ソートされた配列の中の要素から候補を見つけるために、2つのインデックス用の変数を初期化する
    1. 1つ目の変数を、最左端の値で初期化する: L = 0
    2. 2つ目の変数を、最右端の値で初期化する: R = ar_size - 1
  3. l < r の間これを繰り返す ( while L < R )
    1. もし A[L] + A[R] == sum ならば、1を返す
    2. もし A[L] + A[R] < sum ならば、Lをインクリメント、L++
    3. それ以外は Rをデクリメント、R--
  4. 配列全てから候補が見つからなければ、0を返す

アルゴリズムB

 This method works in O(n) time if range of numbers is known.

この手法は数値の範囲が既知のものであればO(n)で動作する

処理フロー
和は与えられた和で、配列Aは我々が見つけたいペアとなる(?)
  1. 2分木の連想配列を初期化する M[] = {0, 0, 0...}
  2. 配列A[]の中にある、各々のA[i]に対して以下を実行
    1. もし M[x - A[i]] がセットされていれば A[i], x - A[i] を出力
    2. M[A[i]] をセットする

アルゴリズムC

Cを走らせて、先ほどのアルゴリズムAかBを内部で使用する。

 We have discussed a O(n^3) algorithm in the previous post on this topic. The problem can be solved in O(n^2Logn) time with the help of auxiliary space.

先に我々は、AとBのアルゴリズムでこれがO(n^3)で動作することを議論した。この問題は空間計算量の助けによりO(n^2 log n)で解ける

処理フロー
対象の数列をAとする
  1. 補助用の配列aux[]を作成する、そして全ての求めるべき和の可能性のあるペアをそこに格納する。aux[]のサイズは n が 配列Aのサイズとすると、 n*(n-1)/2 になる
  2. 補助用の配列aux[]をソートする
  • 今やXに等しいなんらかの数値の組み合わせの和を配列auxから見つける問題は簡単化された。その2つの要素を能率的に見つけるにはアルゴリズムAが使えるだろう。
  • ここには以下のような特筆すべきポイントがある
    • 配列aux は 配列Aから抽出したペアを表している。配列auxから2つの要素を選ぶ一方で、その2つの要素が一般に配列Aの中にあるかどうかをチェックする必要がある
    • 例えば、A[1]とA[2]の和が最初の要素だとして、A[2]とA[4]の和が次の要素だとすると、これは配列Aの中から抽出した4要素を持った配列ということにはならない
お名前: コメント: