なんとな～くしあわせ？の日記

「そしてそれゆえ、知識そのものが力である」 (Nam et ipsa scientia potestas est.) 〜 フランシス・ベーコン

AOJ - ITP1_7_B (組み合わせ) を解いてみた

プログラミング AOJ 競技プログラミング

偉そうに書いてるが、これは序の口の問題である。。。

AOJ - ITP1_7_B

How many ways? | Aizu Online Judge
自分の回答


解法１ algorithm - Finding all possible combinations of numbers to reach a given sum - Stack Overflow

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

アルゴリズム

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 を求めてみる - なんとな～くしあわせ？の日記

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

２つのアルゴリズムを使う

アルゴリズム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. ソートされた配列の中の要素から候補を見つけるために、２つのインデックス用の変数を初期化する
    1. １つ目の変数を、最左端の値で初期化する： L = 0
    2. ２つ目の変数を、最右端の値で初期化する： R = ar_size - 1
  3. L < R の間これを繰り返す ( while L < R )
    1. もし A[L] + A[R] == sum ならば、１を返す
    2. もし A[L] + A[R] < sum ならば、Lをインクリメント、L++
    3. それ以外は Rをデクリメント、R--
  4. 配列全てから候補が見つからなければ、０を返す
アルゴリズムB

This method works in O(n) time if range of numbers is known.
この手法は数値の範囲が既知のものであればO(n)で動作する

処理フロー

和は与えられた和で、配列Aは我々が見つけたいペアとなる（？）

  1. ２分木の連想配列を初期化する 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から見つける問題は簡単化された。その２つの要素を能率的に見つけるにはアルゴリズムAが使えるだろう。

ここには以下のような特筆すべきポイントがある

  • 配列aux は 配列Aから抽出したペアを表している。配列auxから２つの要素を選ぶ一方で、その２つの要素が一般に配列Aの中にあるかどうかをチェックする必要がある
  • 例えば、A[1]とA[2]の和が最初の要素だとして、A[2]とA[4]の和が次の要素だとすると、これは配列Aの中から抽出した４要素を持った配列ということにはならない
結果

アルゴリズムAとCを使用してやることで普通に解けた。

  • 解法１
    • ターゲットの配列が1〜100まであったとき、そこから全ての組み合わせを求めると161700になってしまう、そこから更に計算して合計値が100になるのを探すのは効率が悪すぎる
  • 解法２
    • 求めるべき要素３つのうち１つを決め撃ちして、残り二つを配列から挟み撃ちの形で求めているので早い