D: 壊れかけのヒープ 問題案: 稲葉
問題 与えられた配列を接尾辞として持つような、 最小ヒープ木（子より親が小さい値を持つ木）を表現した配列の最短の長さを求めよ Input (length ≦ 100) Which is a Heap 4 2 3 1 4 Output 1 4 2 3 2 3
想定解法 ・・・ 入力を接尾辞に持つ形を短い順に全部試す 4 2 3 4 2 3 4 2 4 3 2 3 4 2 3 これはヒープに なるかな？ これはヒープに なるかな？ これはヒープに なるかな？ これは・・・？
想定解法： 注意点が２つ ・・・ 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 これはヒープに なるかな？ これはヒープに なるかな？ これはヒープに なるかな？ これは・・・？
Q1: どのくらいのサイズまで試す？ A: このくらい。
Q1: どのくらいのサイズまで試す？ の方が より 短い より の方が 短い など A: 入力長の倍以上に木の底辺が長い解があるなら もっと短い解が存在したはずなのでそれ以上考えなくて良い の方が 短い より a a min b,c b c より の方が 短い など
“入力が葉に全部並ぶまで” や “2Nまで” は不十分 入力の長さ：７ 答え：16 6 1 7 8 2 3 9 10 15 11 4 12 13 5 14
Q2: これはヒープになるかな？の判定 A: 下から順に、使える最大値を貪欲に埋める これはヒープに なるかな？ 9 2 3 6
1 9 2 3 6 Q2: これはヒープになるかな？の判定 A: 下から順に、使える最大値を貪欲に埋める 3, 6 より小さい、 まだ使ってない 最大値 1 9 2 3 6
1 9 2 3 6 Q2: これはヒープになるかな？の判定 A: 下から順に、使える最大値を貪欲に埋める 2, 9 より小さい、 まだ使ってない 最大値 1 9 2 3 6
Q2: これはヒープになるかな？の判定 A: 下から順に、使える最大値を貪欲に埋める 無理 もう無理 1 9 2 3 6
Q2: これはヒープになるかな？の判定 A: 下から順に、使える最大値を貪欲に埋める これはヒープに なるかな？ 9 2 3 6
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 できた！
貪欲でよいことの証明 [1/2] M 例：最大値 M は別の場所に使って 末尾では M-a を使うヒープの作り方が あったとする。 M-1
貪欲でよいことの証明 [2/2] M 例：その別解で [M-a, ..., M] があった箇所を [M, M-a, ...] に置き換えてもヒープなのでOK M-2 M-1 M
結果 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 %