概要

この問題は、与えられた \(N\) 個の商品の価格からいくつかを選び、その合計金額をちょうど \(S\) 円にする方法が何通りあるかを求める問題です。

価格の合計がちょうど \(S\) 円になる選び方の総数 \(C\) に応じて、 \(C = 0\) なら NO、 \(C = 1\) なら ALMOST、 \(C \geq 2\) なら YES を出力します。

これは「部分和問題」の数え上げであり、制約の \(N \le 40\)、 \(S \le 10^{18}\) に対応するために、半分全列挙（Meet-in-the-middle）という手法を用いて効率的に解くことができます。

---

考察

素朴なアプローチとその限界

各商品について「選ぶ」か「選ばない」かの 2 通りの選択肢があるため、すべての選び方を愚直に探索すると \(2^N\) 通りの組み合わせが存在します。 今回の制約は \(N \le 40\) です。 \(2^{40} \approx 1.1 \times 10^{12}\)（約1兆）通りとなり、制限時間（通常2〜3秒）以内にすべての組み合わせを調べることは不可能です。

また、動的計画法（DP）を用いて「 \(i\) 番目の商品まで見て合計金額を \(j\) 円にする方法の数」を管理する方法も考えられますが、目標金額 \(S \le 10^{18}\) と非常に大きいため、配列のサイズや計算量の観点から不可能です。

解決策：半分全列挙

\(N\) 個の商品を、半分（ \(N_1 = \lfloor N/2 \rfloor\) 個と \(N_2 = N - N_1\) 個）の 2 つのグループに分割します。 \(N \le 40\) のとき、半分に分けるとそれぞれのグループの要素数は高々 \(20\) 個になります。

\(2^{20} \approx 1.0 \times 10^6\)（約100万）通りであれば、コンピュータで十分に高速に全列挙できます。

1. グループ1 から選ぶ商品の合計金額としてあり得る値をすべて列挙したリスト \(A\) を作成する。
2. グループ2 から選ぶ商品の合計金額としてあり得る値をすべて列挙したリスト \(B\) を作成する。
3. \(A\) の要素 \(a\) と \(B\) の要素 \(b\) のペアのうち、 \(a + b = S\) となる組み合わせの数を効率よく数え上げる。

さらなる最適化（枝刈り）

本問題では、組み合わせの正確な総数 \(C\) を最後まで求める必要はありません。 \(C \ge 2\) であることが判明した瞬間に、探索を打ち切って YES を出力して終了（早期終了）できます。これにより大幅な高速化が期待できます。

また、以下の明らかなケースは探索を行う前に即座に判定できます。 - \(S\) より大きい価格の商品は絶対に選ばれないため、最初から除外する。 - すべての商品の合計金額が \(S\) 未満であれば、答えは 0 通り（NO）。 - すべての商品の合計金額がちょうど \(S\) であれば、すべての商品を選ぶ 1 通りのみ（ALMOST）。

---

アルゴリズム

1. 前処理:

   • 商品の価格配列 \(P\) を降順にソートします。
   • \(P_i > S\) となる要素を配列から除外します。
   • 残った要素の総和が \(S\) 未満なら NO、ちょうど \(S\) なら ALMOST を出力して終了します。

2. 半分に分割:

   • 残った商品を前半グループ \(P_1\)（要素数 \(N_1\)）と後半グループ \(P_2\)（要素数 \(N_2\)）に分割します。

3. 部分和の全列挙:

   • それぞれのグループについて、作ることができる部分和をすべて列挙し、リスト sums1 と sums2 を作成します。
   • このとき、部分和が \(S\) を超えるものはあらかじめ追加しないようにして、無駄なメモリと計算量を削減します。

4. ソートと尺取り法（Two Pointers）による探索:

   • sums1 と sums2 を昇順にソートします。
   • sums1 の先頭（最小値）を指すポインタ left と、sums2 の末尾（最大値）を指すポインタ right を用意します。
   • sums1[left] + sums2[right] の値を評価します：
     • \(S\) より小さければ、合計を大きくするために left を右に動かします。
     • \(S\) より大きければ、合計を小さくするために right を左に動かします。
     • ちょうど \(S\) であれば、同じ値が連続する個数を考慮して組み合わせ数を加算します。
   • 組み合わせ数が \(2\) 以上になった時点で、直ちに YES を出力してプログラムを終了します。
   • 探索が終了しても \(2\) 以上にならなかった場合、最終的なカウントに応じて NO または ALMOST を出力します。

---

計算量

• 時間計算量: \(O(2^{N/2} \log(2^{N/2}))\)

  • 半分全列挙により、生成される部分和の数は最大で \(2^{20} \approx 10^6\) 個です。
  • これらをソートするのに \(O(M \log M)\) （ただし \(M = 2^{N/2}\)）かかります。\(10^6 \log_2(10^6) \approx 2 \times 10^7\) 回の演算となり、実行時間制限（通常2秒）に余裕で間に合います。
  • 尺取り法による探索は \(O(2^{N/2})\) で行えます。

• 空間計算量: \(O(2^{N/2})\)

  • 部分和を格納するリスト sums1, sums2 のサイズは最大で \(2^{20}\)（約 100 万要素）です。これは数メガバイト程度のメモリしか消費しないため、空間計算量も非常に安全です。

---

実装のポイント

• 効率的な部分和の生成:

  def get_sums(arr):
    sums = [0]
    for p in arr:
        sums.extend([x + p for x in sums if x + p <= S])
    return sums
  

  このように、新しい商品 p を加える際に、すでに \(S\) を超えてしまう組み合わせをリストに加えない（if x + p <= S）ようにすることで、探索空間を劇的に削減しています。

• 重複要素の正しい数え上げ: 尺取り法において、sums1 や sums2 に同じ値が複数存在する場合、単にポインタを動かすだけでは組み合わせ数を正しく数えられません。同じ値が連続する個数 c1 と c2 をカウントし、その積 c1 * c2 を加算することで、重複を正しく処理しています。

  ソースコード

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    S = int(data[1])
    P = [int(x) for x in data[2:]]

    P.sort(reverse=True)
    P = [p for p in P if p <= S]
    N = len(P)

    if N == 0:
        print("NO")
        return

    total_sum = sum(P)
    if total_sum < S:
        print("NO")
        return
    if total_sum == S:
        print("ALMOST")
        return

    N1 = N // 2
    P1 = P[:N1]
    P2 = P[N1:]

    def get_sums(arr):
        sums = [0]
        for p in arr:
            sums.extend([x + p for x in sums if x + p <= S])
        return sums

    sums1 = get_sums(P1)
    sums2 = get_sums(P2)

    sums1.sort()
    sums2.sort()

    ans = 0
    left = 0
    right = len(sums2) - 1
    len1 = len(sums1)

    while left < len1 and right >= 0:
        val = sums1[left] + sums2[right]
        if val < S:
            left += 1
        elif val > S:
            right -= 1
        else:
            c1 = 1
            while left + 1 < len1 and sums1[left] == sums1[left + 1]:
                c1 += 1
                left += 1
            c2 = 1
            while right - 1 >= 0 and sums2[right] == sums2[right - 1]:
                c2 += 1
                right -= 1
            ans += c1 * c2
            if ans >= 2:
                print("YES")
                return
            left += 1
            right -= 1

    if ans == 0:
        print("NO")
    elif ans == 1:
        print("ALMOST")
    else:
        print("YES")


if __name__ == "__main__":
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。