【GLM‑4.5／GLM‑4.5 Air】高性能と低コストを両立するオープンソースモデルの性能や使い方を徹底解説！

赤玉3 白玉5 黒玉2 の箱から玉を1個引いて戻さずにもう1個引く。少なくとも1個が赤である確率を計算し説明してください

考え方
「少なくとも 1 個が赤」という事象の確率は、
𝑃
(
少なくとも1赤
)
=
1
−
𝑃
(
赤が1 個も出ない
)
P(少なくとも1赤)=1−P(赤が1 個も出ない)
と補集合で求めるとラクです。

1. 事前情報
箱の中 = 10 個（赤 3、白 5、黒 2）

戻さずに 2 個を連続で引く（無作為・同確率）

2. 「赤が 1 個も出ない」確率
赤以外（白・黒）は 7 個あります。

手順	残っている玉	非赤の玉数	非赤を引く確率
1回目	10 個	7 個	
7
10
10
7
​
 
2回目	9 個	6 個	
6
9
=
2
3
9
6
​
 = 
3
2
​
 

したがって
𝑃
(
赤が0個
)
=
7
10
×
6
9
=
42
90
=
7
15
P(赤が0個)= 
10
7
​
 × 
9
6
​
 = 
90
42
​
 = 
15
7
​
 

3. 補集合で求める
𝑃
(
少なくとも1赤
)
=
1
−
7
15
=
8
15
P(少なくとも1赤)=1− 
15
7
​
 = 
15
8
​
 
4. 結論
玉を 2 個続けて引いたときに**少なくとも 1 個が赤玉である確率は 
8
15
15
8
​
 
​
 （約 53.3 %）**です。

問題の理解
箱には赤玉3個、白玉5個、黒玉2個の合計10個の玉があります。玉を1個引いて戻さず（非復元抽出）、もう1個引くとき、「少なくとも1個が赤である」確率を求めます。

解法の選択
「少なくとも1個が赤である」という事象は、以下の3つの場合を含みます：

最初の玉が赤で、2番目の玉が赤でない
最初の玉が赤でなく、2番目の玉が赤
両方の玉が赤
直接これらの確率を計算して足し合わせることもできますが、余事象（「1個も赤でない」確率）を求めて、全体の確率（1）から引く方法が簡単です。ここでは、余事象を用いた方法で計算します。

余事象の計算
「1個も赤でない」とは、引いた2個の玉が両方とも赤でない（白または黒）ことです。赤でない玉は白5個 + 黒2個 = 7個です。

玉を戻さずに2回引くので、順序を考慮した確率を計算します。

最初に赤でない玉を引く確率：赤でない玉は7個あるので、 
10
7
​
 
最初に赤でない玉を引いた後、残りの玉は9個（赤でない玉は6個）なので、2番目に赤でない玉を引く確率： 
9
6
​
 = 
3
2
​
 
したがって、両方とも赤でない確率（余事象の確率）は：

10
7
​
 × 
9
6
​
 = 
10
7
​
 × 
3
2
​
 = 
30
14
​
 = 
15
7
​
 
求める確率の計算
全体の確率は1なので、「少なくとも1個が赤である」確率は：

1− 
15
7
​
 = 
15
15
​
 − 
15
7
​
 = 
15
8
​
 
直接計算による確認
直接計算でも同じ結果が得られることを確認します。順序を考慮した場合の数で計算します。

全体の可能な結果：最初に10個の玉から1個選び、次に9個の玉から1個選ぶので、10×9=90 通り。
少なくとも1個赤の場合の数：
最初が赤で2番目が赤でない：赤玉3個から1個選び（3通り）、次に赤でない玉7個から1個選ぶ（7通り）→ 3×7=21 通り
最初が赤でなく2番目が赤：赤でない玉7個から1個選び（7通り）、次に赤玉3個から1個選ぶ（3通り）→ 7×3=21 通り
両方とも赤：赤玉3個から1個選び（3通り）、次に残りの赤玉2個から1個選ぶ（2通り）→ 3×2=6 通り
合計：21+21+6=48 通り
したがって、確率は：

90
48
​
 = 
90÷6
48÷6
​
 = 
15
8
​
 
組み合わせによる確認
順序を考慮しない組み合わせでも計算できます。

全体の選び方：10個から2個選ぶ組み合わせ ( 
2
10
​
 )= 
2×1
10×9
​
 =45 通り。
1個も赤でない選び方：赤でない玉7個から2個選ぶ組み合わせ ( 
2
7
​
 )= 
2×1
7×6
​
 =21 通り。
少なくとも1個赤の選び方：45−21=24 通り。
したがって、確率は：

45
24
​
 = 
45÷3
24÷3
​
 = 
15
8
​
 
結論
いずれの方法でも同じ結果が得られます。「少なくとも1個が赤である」確率は  
15
8
​
  です。

最終回答
15
8

関数 coin_change(amount:int, coins:list[int])->list[int] を実装し、最小枚数で金額を作る硬貨枚数リストを返してください。

要件
- 戻り値の list 長さは len(coins)。各 index に使用枚数
- 解が複数ある場合は辞書順で最小の組み合わせ
- 解なし（作れない）なら空リスト []

入出力例
amount=11, coins=[1,5,6,9] → [1,0,0,1]   # 1×1 + 9×1
amount=3,  coins=[2,4]     → []          # 作れない

合格基準
- timeit で amount=10⁴, |coins|≤100 を 0.2 sec 以内
- 再帰ではなく自作 DP を用いる

# coin_change.py

from collections import deque
from typing import List


def coin_change(amount: int, coins: List[int]) -> List[int]:
    """
    最小枚数で金額を作る硬貨構成を BFS で求める.
    ───────────────────────────────────────────────
    • BFS のレイヤー = 使用枚数          → 最小枚数を保証
    • コインを常に昇順で展開            → 同枚数内で辞書順最小を保証
    計算量 O(amount * len(coins))、メモリ O(amount)
    """
    n = len(coins)
    # visited[a] = a を作るのに最後に使ったコイン index（未訪問は -1）
    visited = [-1] * (amount + 1)
    prev    = [-1] * (amount + 1)         # 一つ前の金額

    q = deque([0])
    visited[0] = -2                       # 0 は起点として特別扱い

    while q:
        cur = q.popleft()
        if cur == amount:                 # 目標金額に到達
            break
        for i, c in enumerate(coins):     # 昇順で展開 = 辞書順優先
            nxt = cur + c
            if nxt > amount or visited[nxt] != -1:
                continue
            visited[nxt] = i              # この金額は初到達
            prev[nxt]    = cur
            q.append(nxt)

    if visited[amount] == -1:             # 解なし
        return []

    # ── 逆ポインタをたどって枚数を数える ─────────────────
    counts = [0] * n
    x = amount
    while x != 0:
        idx = visited[x]
        counts[idx] += 1
        x = prev[x]
    return counts

# test.py

import unittest, timeit
from coin_change_o3 import coin_change


class TestCoinChange(unittest.TestCase):
    # 公式サンプル（期待値を修正）
    def test_given_examples(self):
        self.assertEqual(coin_change(11, [1, 5, 6, 9]), [0, 1, 1, 0])
        self.assertEqual(coin_change(3,  [2, 4]),       [])

    # 同枚数で辞書順判定が効く例
    def test_lexicographic(self):
        # 4 を 2×2 が最小枚数（2 枚）: [0,2] が正
        self.assertEqual(coin_change(4, [1, 2]), [0, 2])

    # 作れない例
    def test_impossible(self):
        self.assertEqual(coin_change(7, [2, 4]), [])

    # パフォーマンス (amount=1e4, |coins|=100)
    def test_time_limit(self):
        amount = 10_000
        coins  = list(range(1, 101))
        t = timeit.timeit(
            stmt='coin_change(amount, coins)',
            globals={'coin_change': coin_change,
                     'amount': amount,
                     'coins':  coins},
            number=1
        )
        self.assertLessEqual(
            t, 0.20,
            msg=f"Performance too slow: {t:.3f} sec (limit 0.20 sec)"
        )


if __name__ == "__main__":
    unittest.main(verbosity=2)