高速解と愚直解をぶつける

もっともらしい証明だけで実装ミスは消えません。小さな入力で確実に正しい愚直解と比較し、最小の反例を探します。

言語：Python / 計算量：テスト回数 × 愚直解コスト

前提：set と辞書で「見たこと」を記録

考え方

1. 小さい制約の愚直解を独立に書きます。
2. 乱数の種を固定し、再現可能にします。
3. 不一致の入力を保存し、要素を削って原因を絞ります。

具体例

ペアの和を数える高速解では「自分自身を数える」「2倍数える」が典型のバグ。愚直な i<j と比較します。

実装

import random
from collections import Counter
rng=random.Random(0)
def fast(a,k):
    c=Counter();ans=0
    for x in a:
        ans+=c[k-x];c[x]+=1
    return ans
for _ in range(100):
    a=[rng.randrange(5) for _ in range(8)];k=rng.randrange(9)
    slow=sum(a[i]+a[j]==k for i in range(len(a)) for j in range(i+1,len(a)))
    assert fast(a,k)==slow,(a,k)
print("OK")

注意する条件

ランダムテストが通っても正しさの証明にはなりません。最大値・0・同値・境界の手動テストも必要です。

確認問題

[2,2,2] で和4となる i<j の組数は？

実装課題

講義の fast で c[x]+=1 を ans+=c[k-x] より前へ移したバグ版を作り、a=[2], k=4 で結果を出す。なぜ誤るか説明。

出力:
1

from collections import Counter
a=[2];k=4;c=Counter();ans=0
for x in a:
    c[x]+=1
    ans+=c[k-x]
print(ans)
# 自分自身を数えてしまう。正解は0。

読了の記録・下書き・メモへ