問題
空の状態から始まる集合に対して 挿入 と 最小値取り出し を処理する「簡略版ソフトヒープ」を実装する。構造は二項ヒープ（binomial heap）と同じ「同階数の木を1本にまとめる繰り上がり処理」で構成されるが、階数閾値 $R$ が与えられ、次のルールで代表キー（ckey）を管理する。
- 階数 $r$ の木2本（ckey は $c_1,c_2$）を併合し階数 $r+1$ の木を作るとき
- $r+1 \le R$ なら「正確」：新ckey $=\min(c_1,c_2)$
- $r+1 > R$ なら「破損」：新ckey $=\max(c_1,c_2)$
最小値取り出しでは、フォレスト中でckeyが最小の木を1つ取り出しそのckeyを出力する。取り出した木の子は個別の木として繰り上がり処理でフォレストへ戻す。取り出した木の items のうち真のキーが報告ckeyより小さいものの個数を「破損個数」とし、$Q$ 回の取り出しにわたる合計を求める。
入力形式
N R Q
x_1 x_2 ... x_N制約
$1 \le Q \le N \le 16$
$0 \le R \le 4$
$x_i$ は相異なる整数（$1\le x_i\le1000$）
挿入は $x_1,\dots,x_N$ の順
入出力例
入力例1
4 1 2
3 1 4 2出力例1
2
1
11〜2行目が2回の最小値取り出しのckey、3行目が破損個数の合計。$N=4,R=1$ で理論目安 $N/2^{R+1}=1$ と実測が一致する。
概念図：階数閾値Rを超えると ckey が min→max に切り替わる
ヒント（段階的開示）
ヒント1（方向性）
通常の二項ヒープに「ある階数を超えたら代表値をminではなくmaxにする」というルールを1つ足すだけで、ソフトヒープの本質（正確さを犠牲にして操作を高速化する）を体験できる。
ヒント2（アプローチ）
併合を「木Aに木Bを子として追加し階数+1」と実装すれば木構造は保たれる。ckeyの更新だけを閾値$R$で`min`/`max`切り替えればよい。挿入も最小値取り出し後の子の再挿入も同じ「同階数があれば併合して繰り上げる」carry処理に帰着できる。
ヒント3（誘導）
def merge(a, b, R):
new_rank = a['rank'] + 1
if new_rank <= R:
new_ckey = min(a['ckey'], b['ckey'])
else:
new_ckey = max(a['ckey'], b['ckey'])
a['children'].append(b)
a['rank'] = new_rank
a['ckey'] = new_ckey
a['items'] = a['items'] + b['items']
return a
def insert_tree(forest, node, R):
r = node['rank']
while r in forest:
other = forest.pop(r)
node = merge(node, other, R)
r = node['rank']
forest[r] = node模範解答 (Python)
import sys
def merge(a, b, R):
new_rank = a['rank'] + 1
if new_rank <= R:
new_ckey = min(a['ckey'], b['ckey'])
else:
new_ckey = max(a['ckey'], b['ckey'])
a['children'].append(b)
a['rank'] = new_rank
a['ckey'] = new_ckey
a['items'] = a['items'] + b['items']
return a
def insert_tree(forest, node, R):
r = node['rank']
while r in forest:
other = forest.pop(r)
node = merge(node, other, R)
r = node['rank']
forest[r] = node
def insert(forest, key, R):
leaf = {'rank': 0, 'ckey': key, 'items': [key], 'children': []}
insert_tree(forest, leaf, R)
def extract_min(forest, R):
min_rank = min(forest, key=lambda r: forest[r]['ckey'])
node = forest.pop(min_rank)
reported = node['ckey']
corrupted = sum(1 for x in node['items'] if x < reported)
for child in node['children']:
insert_tree(forest, child, R)
return reported, corrupted
def main():
data = sys.stdin.buffer.read().split()
idx = 0
N = int(data[idx]); idx += 1
R = int(data[idx]); idx += 1
Q = int(data[idx]); idx += 1
keys = [int(data[idx + i]) for i in range(N)]
idx += N
forest = {}
for k in keys:
insert(forest, k, R)
total_corrupted = 0
out = []
for _ in range(Q):
reported, c = extract_min(forest, R)
out.append(str(reported))
total_corrupted += c
out.append(str(total_corrupted))
print('\n'.join(out))
main()Step-by-Step 解説
1二項ヒープの繰り上がり構造
$N$個の挿入で階数集合は$N$の二進表現に対応する。ソフトヒープはこの上にckey計算ルールを1つ足しただけ。
$N$個の挿入で階数集合は$N$の二進表現に対応する。ソフトヒープはこの上にckey計算ルールを1つ足しただけ。
2破損の発生箇所
破損は「新階数がRを超える併合」でのみ発生。Rが大きいほど破損開始階数が高くなり、破損割合が下がる代わりに正確さを保つコストが増える。
破損は「新階数がRを超える併合」でのみ発生。Rが大きいほど破損開始階数が高くなり、破損割合が下がる代わりに正確さを保つコストが増える。
3破損個数の理論上限
階数$r$の木は$2^r$要素。閾値$R$を超えて誕生する木(階数$R+1$)は正確な2本をmaxでまとめるため一部が隠れる。目安は$N/2^{R+1}$。入力例1では$4/2^2=1$で実測と一致。
階数$r$の木は$2^r$要素。閾値$R$を超えて誕生する木(階数$R+1$)は正確な2本をmaxでまとめるため一部が隠れる。目安は$N/2^{R+1}$。入力例1では$4/2^2=1$で実測と一致。
4最小値取り出し後の再構成
取り出した木の子(互いに異なる階数の独立した木の集合)を挿入と同じ`insert_tree`で繰り上げてフォレストへ戻す。
取り出した木の子(互いに異なる階数の独立した木の集合)を挿入と同じ`insert_tree`で繰り上げてフォレストへ戻す。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 破損閾値判定を併合前の階数で行う | `a['rank']<=R`のように判定 | 併合後の新階数`new_rank=a['rank']+1`で判定する |
| 破損個数を木の全要素数にしてしまう | 真に小さい要素だけが「隠された」ことを見落とす | `items`のうち`x<reported`のものだけを数える |
| 取り出した木の子を丸ごと1本として戻す | 子は互いに異なる階数の独立した複数の木であることを忘れる | `children`の各要素を個別に`insert_tree`へ渡す |
| `min(forest)`で最小ckeyを探そうとする | それだと階数最小になりckey最小にならない | `min(forest, key=lambda r: forest[r]['ckey'])`を使う |
| 併合で両者の children を両方引き継ごうとする | 二項木の併合は一方を根、他方を子として追加するだけでよい | `a['children'].append(b)`のみでよい |
次のステップ
- 発展: $R$を$0$から$4$まで変化させ破損個数の推移をグラフ化し$N/2^{R+1}$との誤差を実測せよ。
- 次回予告: ビームサーチ（Beam Search・ビーム幅Kによる近似探索）