Upgrade to Pro — share decks privately, control downloads, hide ads and more …

正しく作るランダムケース

tsutaj
July 11, 2023

 正しく作るランダムケース

2023/07/11 UV Study:ビアバッシュ!競技プログラミングLT会
https://uniquevision.connpass.com/event/287075/

スライド内のリンク先を見たい方はこちら:https://compro.tsutaj.com/archive/230711_random_case.pdf

tsutaj

July 11, 2023
Tweet

More Decks by tsutaj

Other Decks in Programming

Transcript

  1. ਖ਼͘͠࡞ΔϥϯμϜέʔε
    UV Study: ϏΞόογϡʂ ڝٕϓϩάϥϛϯά LT ձ
    tsutaj
    July 11, 2023
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 1 / 24

    View Slide

  2. ࣗݾ঺հ
    ▶ Twitter: @tsutaj
    ▶ ࠷ۙ͸ AHC ʹग़ͨΓ ICPC OB/OG ձʹ͍·͢
    ▶ ֶੜͷͱ͖͸େֶ༗ࢤͰ࡞໰ΛΑ͘΍ͬͯ·ͨ͠
    ▶ ໋ཱ߹॓ɺձ௡߹॓ɺ๺େ߹॓ɺetc...
    ▶ ࠷ۙ PAST ্ڃʙΤΩεύʔτຊΛࣥච͠·ͨ͠
    ▶ ࠓճ͸ڝϓϩ࡞໰ʹ࢖͑ͦ͏ͳςΫΛ঺հ͠·͢
    ▶ աڈͷൃද (ࢀߟ): ڝϓϩ࡞໰Λࢧ͑Δٕज़ Link
    ▶ ͳ͚ͳ͠ͷ࡞໰ϊ΢ϋ΢Λগͣͭ͠์ྲྀ͍ͨ͠
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 2 / 24

    View Slide

  3. 1
    ͸͡Ίʹ
    ϥϯμϜέʔεΛ࢖͏৔໘
    ͜ͷൃදʹ͓͚Δ ʮਖ਼͍͠ʯ ϥϯμϜέʔεͱ͸
    2
    ϥϯμϜέʔεΛ࡞ͬͯΈΑ͏
    ॱྻΛϥϯμϜʹ࡞Δ
    N ݸͷத͔Β K ݸબͿ
    K = 2 ͩͬͨΒʁ
    ֬཰తख๏
    ܾఆతख๏
    άϥϑΛϥϯμϜʹ࡞Δ
    άϥϑΛ࡞Δ
    ໦Λ࡞Δ
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 3 / 24

    View Slide

  4. 1
    ͸͡Ίʹ
    ϥϯμϜέʔεΛ࢖͏৔໘
    ͜ͷൃදʹ͓͚Δ ʮਖ਼͍͠ʯ ϥϯμϜέʔεͱ͸
    2
    ϥϯμϜέʔεΛ࡞ͬͯΈΑ͏
    ॱྻΛϥϯμϜʹ࡞Δ
    N ݸͷத͔Β K ݸબͿ
    K = 2 ͩͬͨΒʁ
    ֬཰తख๏
    ܾఆతख๏
    άϥϑΛϥϯμϜʹ࡞Δ
    άϥϑΛ࡞Δ
    ໦Λ࡞Δ
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 4 / 24

    View Slide

  5. ϥϯμϜέʔεΛ࢖͏৔໘
    ϥϯμϜʹέʔεΛ࡞Γͨ͘ͳΔ৔໘͸͍͔ͭ͋͘Δ
    ▶ ڝϓϩͰ໰୊Λղ͍͍ͯͯɺόάΛಛఆ͍ͨ͠ͱ͖
    ▶ ڝϓϩͷςετέʔεΛ࡞Γ͍ͨͱ͖
    ▶ ࣮ߦ͢Δ͝ͱʹҟͳΔग़ྗ݁Ռʹ͍ͨ͠ͱ͖
    ▶ ਓһͷׂΓ౰ͯ
    ▶ நબ
    ͜ͷεϥΠυͰ ʮਖ਼͍͠ʯ ϥϯμϜέʔεΛ࡞ΕΔΑ͏ʹͳΓ·͠ΐ͏ʂ
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 5 / 24

    View Slide

  6. 1
    ͸͡Ίʹ
    ϥϯμϜέʔεΛ࢖͏৔໘
    ͜ͷൃදʹ͓͚Δ ʮਖ਼͍͠ʯ ϥϯμϜέʔεͱ͸
    2
    ϥϯμϜέʔεΛ࡞ͬͯΈΑ͏
    ॱྻΛϥϯμϜʹ࡞Δ
    N ݸͷத͔Β K ݸબͿ
    K = 2 ͩͬͨΒʁ
    ֬཰తख๏
    ܾఆతख๏
    άϥϑΛϥϯμϜʹ࡞Δ
    άϥϑΛ࡞Δ
    ໦Λ࡞Δ
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 6 / 24

    View Slide

  7. ͜ͷൃදʹ͓͚Δ ʮਖ਼͍͠ʯ ϥϯμϜέʔεͱ͸
    ▶ ͜ͷൃදʹ͓͍ͯɺ
    ʮਖ਼͍͠ϥϯμϜέʔεʯ = ภΓ͕ͳ͍
    ▶ ΞϧΰϦζϜΛؒҧ͑ΔͱɺҰ༷Ͱͳ͘ͳΔ͜ͱ΋ଟʑ͋Δ
    ▶ ςετέʔε͕ภΔͱɺಛఆͷཁૉ͕ͨ͘͞Μબ͹ΕͯࠔΔ͜ͱ΋
    ▶ ྫ: ͦͷγϟοϑϧɺຊ౰ʹγϟοϑϧͰ͔͢ʁ Կؾͳ͍མͱ݀͠ʹϋ
    Ϛͬͨ࿩ Link
    ▶ ಉ͡ϖΞ͕සൟʹબ͹Εͯ͠·͍ͬͯΔ
    ▶ ͜ͷൃදͰ͸ҎԼͷؔ਺ͷଘࡏΛೝΊɺසൟʹ࢖͍·͢
    ▶ rand(a, b) := a Ҏ্ b ະຬͷ੔਺ΛҰ༷ϥϯμϜʹฦ͢
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 7 / 24

    View Slide

  8. 1
    ͸͡Ίʹ
    ϥϯμϜέʔεΛ࢖͏৔໘
    ͜ͷൃදʹ͓͚Δ ʮਖ਼͍͠ʯ ϥϯμϜέʔεͱ͸
    2
    ϥϯμϜέʔεΛ࡞ͬͯΈΑ͏
    ॱྻΛϥϯμϜʹ࡞Δ
    N ݸͷத͔Β K ݸબͿ
    K = 2 ͩͬͨΒʁ
    ֬཰తख๏
    ܾఆతख๏
    άϥϑΛϥϯμϜʹ࡞Δ
    άϥϑΛ࡞Δ
    ໦Λ࡞Δ
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 8 / 24

    View Slide

  9. ॱྻΛϥϯμϜʹ࡞Δ
    ▶ ௕͞ N ͷॱྻ P ͸ N! ௨Γ͋Δ
    ▶ Ұ༷ϥϯμϜʹॱྻΛ࡞Δʹ͸ɺN! ௨Γͷॱྻ͢΂͕ͯಉ֬͡཰Ͱग़
    Ε͹Α͍
    ▶ ࣍ϖʔδͰϥϯμϜʹ࡞Δํ๏Λ঺հ
    Figure: Ҿ༻ݩ: GeeksforGeeks Link
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 9 / 24

    View Slide

  10. ॱྻΛϥϯμϜʹ࡞Δ
    ௕͞ N ͷॱྻ P Λ࡞Δʹ͸ɺྻ A = (1, . . . , N) Λγϟοϑϧ͢Ε͹Α͍
    ϑΟογϟʔɾΠΣʔπͷγϟοϑϧ Link
    1: P ← A
    2: for i = 0, . . . , N − 2 :
    3: j ← rand(i, N)
    4: Pi
    ͱ Pj
    Λަ׵͢Δ
    5: end for
    6: return P
    ▶ ಛ௃: ܭࢉྔ͕ O(N) Ͱɺ͔ͭภΓ͕ͳ͍ʂ
    ▶ A Ͱ i ൪໨ (0-indexed) ͩͬͨཁૉ͸ɺP Ͱ N − i ௨Γͷ৔ॴʹೖΓ
    ಘΔ
    ▶ ͦͷͨΊɺ͜ͷΞϧΰϦζϜͰಘΒΕΔग़ྗ͸ N! ௨Γ͋Δ
    ▶ ॱྻͷ૯਺ʹҰக
    ▶ ௕͞ N ͷ͢΂ͯͷॱྻ͕͜ͷํ๏Ͱੜ੒͞Ε͏Δ
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 10 / 24

    View Slide

  11. 1
    ͸͡Ίʹ
    ϥϯμϜέʔεΛ࢖͏৔໘
    ͜ͷൃදʹ͓͚Δ ʮਖ਼͍͠ʯ ϥϯμϜέʔεͱ͸
    2
    ϥϯμϜέʔεΛ࡞ͬͯΈΑ͏
    ॱྻΛϥϯμϜʹ࡞Δ
    N ݸͷத͔Β K ݸબͿ
    K = 2 ͩͬͨΒʁ
    ֬཰తख๏
    ܾఆతख๏
    άϥϑΛϥϯμϜʹ࡞Δ
    άϥϑΛ࡞Δ
    ໦Λ࡞Δ
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 11 / 24

    View Slide

  12. N ݸͷத͔Β 2 ݸબͿํ๏
    ▶ (0, 1, . . . , N − 1) ͷத͔Β 2 ݸબͿ͜ͱΛߟ͑Δ
    ▶ ͸͡ΊʹɺΑ͋͘Δؒҧ͍Λ঺հ
    ▶ ࢲ΋࣮ࡍʹ΍ͬͯ͠·ͬͨ͜ͱͷ͋Δख๏
    N ݸͷத͔Β 2 ݸબͿํ๏ʢؒҧ͍ʣ
    1: a ← rand(0, N − 1)
    2: b ← rand(a + 1, N)
    3: return (a, b)
    ▶ ͜Ε͸ಉ༷ʹ͔֬Β͘͠ͳΒͳ͍ͷͰ஫ҙʂ
    ▶ ۩ମྫΛग़ͯ͠ߟ͑ͯΈ·͠ΐ͏
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 12 / 24

    View Slide

  13. N ݸͷத͔Β 2 ݸબͿํ๏
    N ݸͷத͔Β 2 ݸબͿํ๏ʢؒҧ͍ʣ
    1: a ← rand(0, N − 1)
    2: b ← rand(a + 1, N)
    3: return (a, b)
    ▶ ภ͍ͬͯΔ͜ͱΛ͔֬ΊͯΈΑ͏
    ▶ a = 0, b = 1 ͱͳΔ֬཰: 1
    (N−1)2
    ▶ a ͕ 0 ʹͳΔ֬཰΋ɺb ͕ 1 ʹͳΔʢ৚݅෇͖ʣ֬཰΋ 1
    N−1
    ▶ a = N − 2, b = N − 1 ͱͳΔ֬཰: 1
    N−1
    ▶ a ͕ N − 2 ʹͳΔ֬཰͕ 1
    N−1
    Ͱɺͦͷͱ͖ b ͸ඞͣ N − 1 ʹͳΔ
    ▶ ྆ऀ͸ຊདྷಉ֬͡཰Ͱग़ͯ΄͍͕͠ɺޙऀͷ΄͏͕ N − 1 ഒग़΍͘͢ɺ
    ภ͍ͬͯΔ
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 13 / 24

    View Slide

  14. N ݸͷத͔Β 2 ݸબͿํ๏
    Ͱ͸ɺͲͷΑ͏ʹ͢Ε͹ภΓͳ͘औΕΔ͔ʁ
    N ݸͷத͔Β 2 ݸબͿํ๏
    1: repeat
    2: a ← rand(0, N)
    3: b ← rand(0, N)
    4: until a ̸= b
    ▶ a = b ͷέʔεΛഉআͭͭ͠ a, b ΛϥϯμϜʹܾΊΔͷΛ܁Γฦ͢͜
    ͱͰɺҰ༷ϥϯμϜʹϖΞΛܾΊΔ͜ͱ͕Ͱ͖Δ
    ▶ a < b ʹ͍ͨ͠৔߹͸ɺ্هͷํ๏Ͱ a, b ΛબΜͩޙʹඞཁʹԠͯ͡
    swap(a, b) ͢Ε͹Α͍
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 14 / 24

    View Slide

  15. N ݸͷத͔Β K ݸબͿํ๏: expected
    O(K)
    ▶ K ≤ N
    2
    ͷͱ͖ɺ࣍ͷํ๏Ͱ expected O(K) Λୡ੒Ͱ͖Δ
    ▶ K ≤ N
    2
    ΑΓɺཁૉΛ 1 ݸબͿͨΊʹඞཁͳࢼߦճ਺ͷظ଴஋͸ 2 ҎԼ
    ▶ S ͸ unordered_set ͳͲͰ͓࣋ͬͯ͘ͱΑ͍
    N ݸͷத͔Β K ݸબͿํ๏ (K ≤ N
    2
    ͷͱ͖)
    1: S = ()
    2: for i = 0, . . . , K − 1 :
    3: repeat
    4: v ← rand(0, N)
    5: until v not in S
    6: S ʹ v Λ௥Ճ͢Δ
    7: end for
    8: return S
    ▶ K ≥ N
    2
    ͷͱ͖͸ɺબ͹ͳ͍ཁૉΛ্هͷํ๏Ͱܾఆ͢Δ͜ͱͰ
    expected O(K) Λୡ੒Ͱ͖Δ
    ▶ ิू߹Λߟ͍͑ͯΔ
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 15 / 24

    View Slide

  16. N ݸͷத͔Β K ݸબͿํ๏: deterministic
    O(K log K)
    ▶ ࣍ͷํ๏Ͱ deterministic O(K log K) Λୡ੒Ͱ͖Δ
    N ݸͷத͔Β K ݸબͿํ๏
    1: S = ()
    2: for i = 0, . . . , K − 1 :
    3: v ← rand(0, N − K + 1)
    4: S ʹ v Λ௥Ճ͢Δ
    5: end for
    6: S Λঢॱιʔτ͢Δ
    7: for i = 0, . . . , K − 1 :
    8: Si
    ← Si + i
    9: end for
    10: return S
    ▶ ্هͷํ๏͸ N CK = N−K+1HK
    Ͱ͋Δ͜ͱΛར༻͍ͯ͠Δ
    ▶ ιʔτ͞Εͨ S ʹ͍ͭͯɺ
    ʮ·ͩऔ͍ͬͯͳ͍ཁૉͷ͏ͪ Si
    ൪໨ʹখ
    ͍͞΋ͷΛऔΔʯΛ i ͷঢॱʹ΍ͬͯΈΔͱΘ͔Γ΍͍͔͢΋
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 16 / 24

    View Slide

  17. 1
    ͸͡Ίʹ
    ϥϯμϜέʔεΛ࢖͏৔໘
    ͜ͷൃදʹ͓͚Δ ʮਖ਼͍͠ʯ ϥϯμϜέʔεͱ͸
    2
    ϥϯμϜέʔεΛ࡞ͬͯΈΑ͏
    ॱྻΛϥϯμϜʹ࡞Δ
    N ݸͷத͔Β K ݸબͿ
    K = 2 ͩͬͨΒʁ
    ֬཰తख๏
    ܾఆతख๏
    άϥϑΛϥϯμϜʹ࡞Δ
    άϥϑΛ࡞Δ
    ໦Λ࡞Δ
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 17 / 24

    View Slide

  18. άϥϑΛ࡞Δํ๏
    ௖఺Λ۠ผͨ͠ʢ௖఺ʹ൪߸͕͍ͭͨʣάϥϑΛ࡞Δ͜ͱΛߟ͑Δ
    ▶ ϥϯμϜάϥϑΛ࡞Δ
    ▶ ໦Λ࡞Δ
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 18 / 24

    View Slide

  19. ϥϯμϜάϥϑΛ࡞Δํ๏
    ▶ N ௖఺ M ลͷϥϯμϜάϥϑΛ࡞Δ͜ͱΛߟ͑Δ
    ▶ ͋Γ͑Δลͷ૯਺: E = N(N−1)
    2
    N ௖఺ M ลͷϥϯμϜάϥϑΛ࡞Δํ๏
    ઌ΄ͲͷʮN ݸͷத͔Β K ݸબͿํ๏ʯΛԠ༻
    ▶ M < E
    2
    ͷͱ͖
    ▶ ลΛϥϯμϜʹ M ݸબͼɺN ௖఺ M ล͔ΒͳΔάϥϑ G Λฦ͢
    ▶ M ≥ E
    2
    ͷͱ͖
    ▶ ลΛϥϯμϜʹ E − M ݸબͿ
    ▶ N ௖఺ E − M ล͔ΒͳΔάϥϑ G Λ࡞Δ
    ▶ G ͷิάϥϑ G Λฦ͢
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 19 / 24

    View Slide

  20. ϥϯμϜάϥϑΛ࡞Δํ๏ʢ͓·͚ʣ
    N ௖఺ M ลͷʮ࿈݁ͳʯϥϯμϜάϥϑΛ࡞Δ৔߹͸Ͳ͏͢Δ͔ʁ
    Α͘ݟΒΕΔɺ࿈݁ͳϥϯμϜάϥϑΛ࡞Δख๏
    ▶ N ௖఺͔ΒͳΔ໦Λ࡞Δ
    ▶ ໦ΛϥϯμϜʹ࡞Δํ๏͸ޙड़
    ▶ ࢒Γ M − N + 1 ลΛϥϯμϜʹ௥Ճ
    ͔͠͠ɺݫີʹ͸͜Ε͸Ұ༷ϥϯμϜͰͳ͍
    ▶ ݫີʹҰ༷ϥϯμϜɺ͔ͭߴ଎ʹ࡞Δํ๏͕͋Ε͹ڭ͍͑ͯͩ͘͞
    ▶ Codeforces Ͱͷٞ࿦ Link
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 20 / 24

    View Slide

  21. άϥϑΛ࡞Δํ๏
    ௖఺Λ۠ผͨ͠ʢ௖఺ʹ൪߸͕͍ͭͨʣάϥϑΛ࡞Δ͜ͱΛߟ͑Δ
    ▶ ϥϯμϜάϥϑΛ࡞Δ
    ▶ ໦Λ࡞Δ
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 21 / 24

    View Slide

  22. ໦Λ࡞Δํ๏
    ▶ N ௖఺ͷ໦͔Βɺ1 ͔Β N ͷ੔਺͔ΒͳΔ௕͞ N − 2 ͷ਺ྻ
    (Prüfer sequence) ͕Ұҙʹ࡞ΕΔ
    ▶ Prüfer sequence ͔Β໦Λ࡞Δ͜ͱ͕Ͱ͖Δ͠ɺͦͷٯ΋Ͱ͖Δ
    ▶ ໦ΛҰ༷ϥϯμϜʹ࡞Δʹ͸ɺ1 ͔Β N ͷ੔਺͔ΒͳΔ௕͞ N − 2 ͷ
    ਺ྻΛϥϯμϜʹ࡞Γɺ໦ʹม׵͢Ε͹Α͍
    ▶ ໦͔Β Prüfer sequence Λ࡞Δํ๏͸ Appendix ʹهࡌ
    ҎԼͷઆ໌͸ 1-indexed Ͱ͋Δ͜ͱʹ஫ҙ
    Prüfer sequence ͔Β໦Λ࡞Δ: O(N log N) Link
    1: function prufer_sequence_to_tree(A)
    2: (d1
    , d2
    , . . . , dN
    ) ← A Ͱͷ i ͷग़ݱճ਺ + 1 // ௖఺ͷ࣍਺ʹରԠ
    3: for i = 1, . . . , N − 2 :
    4: dv
    = 1 ͔ͭ௖఺൪߸͕࠷খͷ௖఺ v ΛٻΊΔ
    5: ௖఺ v ͱ Ai
    ͷؒʹลΛՃ͑Δ
    6: dv
    ͱ di
    ͷ஋Λ 1 ݮΒ͢
    7: end for
    8: du
    ̸= 0, dv
    ̸= 0 ͱͳΔ௖఺ u ͱ v ͷؒʹลΛՃ͑Δ
    9: end function
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 22 / 24

    View Slide

  23. ·ͱΊ
    ▶ ࠓճ͸ɺҎԼΛҰ༷ϥϯμϜʹ࡞Δํ๏Λ঺հͨ͠
    ▶ গ͠Ͱ΋όάΒͤΔͱҰ༷Ͱͳ͘ͳΔͷͰɺόάʹ஫ҙ
    ▶ ΑΓྑ͍ϥϯμϜέʔεΛ࡞ΕΔΑ͏ʹͳΓ·͠ΐ͏ʂ
    ର৅෺ ܭࢉྔ
    ॱྻ O(N)
    N ݸͷத͔Β૬ҟͳΔ K ݸΛબͿ expected O(K)
    deterministic O(K log K)
    ϥϯμϜάϥϑ expected O(M)
    ໦ O(N log N)
    (࿈݁ϥϯμϜάϥϑ) expected O(N log N + (M − N))
    ˞Ұ༷ϥϯμϜͰͳ͍
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 23 / 24

    View Slide

  24. Appendix:
    ໦͔Β Prüfer sequence
    Λ࡞Δ
    ໦͔Β Prüfer sequence Λ࡞Δ: O(N log N)
    ▶ 2 ͭͷ௖఺͕࢒Δ·ͰɺҎԼΛ܁Γฦ͢
    ▶ ͦͷ࣌఺Ͱͷ໦ͷ༿ͷ͏ͪɺ൪߸͕࠷΋খ͍͞΋ͷΛબͿ
    ▶ ྡ઀͢Δ௖఺Λ Prüfer sequence ʹ௥Ճ͠ɺબΜͩ༿Λ໦͔ΒऔΓআ͘
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 24 / 24

    View Slide

  25. Appendix:
    ໦͔Β Prüfer sequence
    Λ࡞Δ
    ໦͔Β Prüfer sequence Λ࡞Δ: O(N log N)
    ▶ 2 ͭͷ௖఺͕࢒Δ·ͰɺҎԼΛ܁Γฦ͢
    ▶ ͦͷ࣌఺Ͱͷ໦ͷ༿ͷ͏ͪɺ൪߸͕࠷΋খ͍͞΋ͷΛબͿ
    ▶ ྡ઀͢Δ௖఺Λ Prüfer sequence ʹ௥Ճ͠ɺબΜͩ༿Λ໦͔ΒऔΓআ͘
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 24 / 24

    View Slide

  26. Appendix:
    ໦͔Β Prüfer sequence
    Λ࡞Δ
    ໦͔Β Prüfer sequence Λ࡞Δ: O(N log N)
    ▶ 2 ͭͷ௖఺͕࢒Δ·ͰɺҎԼΛ܁Γฦ͢
    ▶ ͦͷ࣌఺Ͱͷ໦ͷ༿ͷ͏ͪɺ൪߸͕࠷΋খ͍͞΋ͷΛબͿ
    ▶ ྡ઀͢Δ௖఺Λ Prüfer sequence ʹ௥Ճ͠ɺબΜͩ༿Λ໦͔ΒऔΓআ͘
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 24 / 24

    View Slide

  27. Appendix:
    ໦͔Β Prüfer sequence
    Λ࡞Δ
    ໦͔Β Prüfer sequence Λ࡞Δ: O(N log N)
    ▶ 2 ͭͷ௖఺͕࢒Δ·ͰɺҎԼΛ܁Γฦ͢
    ▶ ͦͷ࣌఺Ͱͷ໦ͷ༿ͷ͏ͪɺ൪߸͕࠷΋খ͍͞΋ͷΛબͿ
    ▶ ྡ઀͢Δ௖఺Λ Prüfer sequence ʹ௥Ճ͠ɺબΜͩ༿Λ໦͔ΒऔΓআ͘
    tsutaj
    ਖ਼͘͠࡞ΔϥϯμϜέʔε July 11, 2023 24 / 24

    View Slide