D: 壊れかけのヒープ 問題案: 稲葉.

Presentation on theme: "D: 壊れかけのヒープ 問題案: 稲葉."— Presentation transcript:

1 D: 壊れかけのヒープ 問題案: 稲葉

2 問題 与えられた配列を接尾辞として持つような、 最小ヒープ木（子より親が小さい値を持つ木）を表現した配列の最短の長さを求めよ Input (length ≦ 100) Which is a Heap 4 2 3 1 4 Output 1 4 2 3 2 3

3 想定解法 ・・・ 入力を接尾辞に持つ形を短い順に全部試す 4 2 3 4 2 3 4 2 4 3 2 3 4 2 3 これはヒープに
なるかな？ これはヒープに なるかな？ これはヒープに なるかな？ これは・・・？

4 想定解法： 注意点が２つ ・・・ 4 2 3 4 2 4 3 2 3 4 2 3 どのくらいのサイズまで 試したら不可能 -1 と わかる？
ヒープになるかの判定： 空き要素　 をどう埋める？ 4 ・・・ 2 3 4 2 4 3 2 3 4 2 3 これはヒープに なるかな？ これはヒープに なるかな？ これはヒープに なるかな？ これは・・・？

5 Q1: どのくらいのサイズまで試す？ A: このくらい。

6 Q1: どのくらいのサイズまで試す？ の方が より 短い より の方が 短い など
A: 入力長の倍以上に木の底辺が長い解があるなら もっと短い解が存在したはずなのでそれ以上考えなくて良い の方が 短い より a a min b,c b c より の方が 短い など

7 “入力が葉に全部並ぶまで” や “2Nまで” は不十分
入力の長さ：７ 答え：16 6 1 7 8 2 3 9 10 15 11 4 12 13 5 14

8 Q2: これはヒープになるかな？の判定 A: 下から順に、使える最大値を貪欲に埋める これはヒープに なるかな？ 9 2 3 6

9 1 9 2 3 6 Q2: これはヒープになるかな？の判定 A: 下から順に、使える最大値を貪欲に埋める 3, 6 より小さい、
まだ使ってない 最大値 1 9 2 3 6

10 1 9 2 3 6 Q2: これはヒープになるかな？の判定 A: 下から順に、使える最大値を貪欲に埋める 2, 9 より小さい、
まだ使ってない 最大値 1 9 2 3 6

11 Q2: これはヒープになるかな？の判定 A: 下から順に、使える最大値を貪欲に埋める 無理 もう無理 1 9 2 3 6

12 Q2: これはヒープになるかな？の判定 A: 下から順に、使える最大値を貪欲に埋める これはヒープに なるかな？ 9 2 3 6

13 4 1 5 9 2 3 5 9 2 3 6 6 Q2: これはヒープになるかな？の判定 A: 下から順に、使える最大値を貪欲に埋める
4 1 …(中略)… 5 9 2 3 5 9 2 3 6より小さい 最大値… 6 6 できた！

14 貪欲でよいことの証明 [1/2] M 例：最大値 M は別の場所に使って 末尾では M-a を使うヒープの作り方が あったとする。 M-1

15 貪欲でよいことの証明 [2/2] M 例：その別解で [M-a, ..., M] があった箇所を
[M, M-a, ...] に置き換えてもヒープなのでOK M-2 M-1 M

16 結果 First Accepted (Onsite) First Accepted (Online)
semiexp (28:05) First Accepted (Online) Total Submission: 233 Accepted:72 Accepted / Total: 31 % Trying: 93 Trying / Total: 40 %