分割統治法 - 問題を小さく分けてまとめよう

スライド内のリンクを見たい方はこちら：https://hcpc-hokudai.github.io/archive/algorithm_divide_and_conquer_001.pdf

Transcript

1. ෼ׂ౷࣏๏ ໰୊Λখ͘͞෼͚ͯ·ͱΊΑ͏ tsutaj (@tsutaj) Hokkaido University M1 February 7, 2019 tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 1 / 30
2. 1 ೖ໳ฤ 2 ෼ׂ౷࣏๏ͱ͸ʁ స౗਺ (όϒϧιʔτͷަ׵ճ਺) ;ͨͭͷ࿨ 3 ໦ʹର͢Δ෼ׂ౷࣏ ໦ʹର͢Δ෼ׂ౷࣏ ໦ͷॏ৺ͱ͸ ໦ͷॏ৺ͷٻΊํ ࿅श໰୊ (Tree) 4 ฏ໘ʹର͢Δ෼ׂ౷࣏ ࠷ۙ఺ର໰୊ tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 2 / 30
3. ෼ׂ౷࣏๏ͱ͸ʁ ▶ ͦͷ··Ͱ͸ܭࢉʹ࣌ؒΛཁ͢Δ໰୊Λద੾ʹ෼ׂ͠ɺখ͍͞໰୊ʹ ͯ͠ղ͍ͨޙʹͦΕΒΛ·ͱΊΔ͜ͱͰɺޮ཰Α͘ܭࢉ͢Δํ๏ͷ ͜ͱ ▶ ༷ʑͳόϦΤʔγϣϯ ▶ ਺ྻʹର͢Δ෼ׂ౷࣏ ▶ ໦ʹର͢Δ෼ׂ౷࣏ ▶ ฏ໘ʹର͢Δ෼ׂ౷࣏ ▶ ࠓճ͸ͦΕͧΕʹ͍ͭͯ؆୯ʹઆ໌ ▶ ٜຊͷ಺༰ͱ΄΅ಉ͡ͳͷͰɺ͢ͰʹಡΜͰΔํ͸͢Έ·ͤΜ tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 3 / 30
4. స౗਺ όϒϧιʔτͷަ׵ճ਺ స౗਺ όϒϧιʔτͷަ׵ճ਺ ௕͞ N ͷ਺ྻ A ͕༩͑ΒΕΔɻA ͷ i ൪໨ͷཁૉΛ Ai ͱදه͢ΔɻҎ Լͷ৚݅Λຬͨ͢૊ (i, j) ͷݸ਺ΛٻΊΑɻ ▶ 1 ≤ i < j ≤ N ▶ Ai > Aj ೖྗ੍໿ ▶ 1 ≤ N ≤ 105 ▶ 1 ≤ Ai ≤ 109 3 1 4 1 5 9 2 6 転倒数: i < j で、i 番目の数よりも j 番目の数が小さいような (i, j) の個数 この例では (1, 2), (1, 4), (1, 7), (3, 4), (3, 7), (5, 7), (6, 7), (6, 8) の 8 個 tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 4 / 30
5. స౗਺ όϒϧιʔτͷަ׵ճ਺ ▶ Binary Indexed Tree, Segment Tree ͳͲͷʮ۠ؒ࿨ʯΛߴ଎ʹٻΊΒ ΕΔσʔλߏ଄Λ༻͍Δͱ O(N log N) ▶ Binary Indexed Tree Λ࢖ͬͨղ๏͸ผεϥΠυΛࢀর Link ▶ ࣮͸͜ΕΒͷσʔλߏ଄Λ࢖Θͳͯ͘΋ղ͚Δʂʂ Figure: (ࢀߟ) Binary Indexed Tree ͷ֎؍ ▶ ෼ׂ౷࣏๏Ͱղ͘͜ͱΛߟ͑Δ ▶ ͲͷΑ͏ʹ໰୊Λ෼͚ͯɺ·ͱΊΕ͹Α͍ɾɾɾʁ ▶ ਺ྻΛద੾ʹ෼ׂͯ͠໰୊Λখ͘͞͠ɺͦΕΒΛ·ͱΊΑ͏ tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 5 / 30
6. స౗਺ όϒϧιʔτͷަ׵ճ਺ ▶ ݩͷ਺ྻΛɺαΠζ͕Ͱ͖Δ͚ͩ౳͘͠ͳΔΑ͏ 2 ͭʹ෼ׂʂʂ ▶ ෼ׂޙͷ਺ྻΛͦΕͧΕ X, Y ͱ͓͘ͱɺస౗͕ൃੜ͢Δύλʔϯ͸ Ͳ͏ॻ͚Δ͔ʁ 3 1 4 1 5 9 2 6 3 1 4 1 5 9 2 6 分割 数列 X 数列 Y tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 6 / 30
7. స౗਺ όϒϧιʔτͷަ׵ճ਺ స౗ʹ͸ɺ࣍ͷ 3 ύλʔϯ͕͋Δ 1. X ಺Ͱస౗͕ى͜Δ ▶ ͜Ε͸ X Λ΋͏Ұ౓෼ׂ͠ɺ࠶ؼతʹॲཧ͢ΔͱٻΊΒΕΔ 2. Y ಺Ͱస౗͕ى͜Δ ▶ ্ͱಉ༷ʹ࠶ؼతʹٻΊΒΕΔ 3. X ͱ Y ͷؒͰస౗͕ى͜Δ ▶ ͜Ε͸ਅ໘໨ʹٻΊΔ ▶ X ͷ֤ཁૉ e ʹରͯ͠ɺ ʮY ಺ʹ͋Δɺ e ΑΓখ͍͞ཁૉ͸͍ͭ͋͘Δ ͔ʯΛٻΊΔ 3 1 4 1 5 9 2 6 数列 X 数列 Y 3 1 4 1 5 9 2 6 3 1 4 1 5 9 2 6 1: 2: 3: tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 7 / 30
8. స౗਺ όϒϧιʔτͷަ׵ճ਺ X ͱ Y ͷؒͷస౗ΛٻΊΔํ๏ ▶ ࠶ؼతʹॲཧ͢Δࡍʹɺಉ࣌ʹ਺ྻΛιʔτ͢ΔΑ͏ʹ͢Δ ▶ Ϛʔδιʔτ Link ͱಉ͜͡ͱΛ͍ͯ͠Δ ▶ ιʔτࡁΈͰ͋Ε͹ɺస౗͍ͯ͠Δ΋ͷͷݸ਺͸ईऔΓ๏ͷΑ͏ʹٻ ΊΒΕΔ 3 1 4 1 5 9 2 6 ソート 数列 X 数列 Y 1 1 3 4 2 5 6 9 ※再帰的に処理すると、このようなソート済みの列が作れる cf. マージソート tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 8 / 30
9. స౗਺ όϒϧιʔτͷަ׵ճ਺ X ͱ Y ͷؒͷస౗ΛٻΊΔํ๏ ▶ ࠶ؼతʹॲཧ͢Δࡍʹɺಉ࣌ʹ਺ྻΛιʔτ͢ΔΑ͏ʹ͢Δ ▶ Ϛʔδιʔτ Link ͱಉ͜͡ͱΛ͍ͯ͠Δ ▶ ιʔτࡁΈͰ͋Ε͹ɺస౗͍ͯ͠Δ΋ͷͷݸ਺͸ईऔΓ๏ͷΑ͏ʹٻ ΊΒΕΔ 3 1 4 1 5 9 2 6 ソート 数列 X 数列 Y 1 1 3 4 2 5 6 9 転倒: 0 個 tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 8 / 30
10. స౗਺ όϒϧιʔτͷަ׵ճ਺ X ͱ Y ͷؒͷస౗ΛٻΊΔํ๏ ▶ ࠶ؼతʹॲཧ͢Δࡍʹɺಉ࣌ʹ਺ྻΛιʔτ͢ΔΑ͏ʹ͢Δ ▶ Ϛʔδιʔτ Link ͱಉ͜͡ͱΛ͍ͯ͠Δ ▶ ιʔτࡁΈͰ͋Ε͹ɺస౗͍ͯ͠Δ΋ͷͷݸ਺͸ईऔΓ๏ͷΑ͏ʹٻ ΊΒΕΔ 3 1 4 1 5 9 2 6 ソート 数列 X 数列 Y 1 1 3 4 2 5 6 9 転倒: 0 個 tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 8 / 30
11. స౗਺ όϒϧιʔτͷަ׵ճ਺ X ͱ Y ͷؒͷస౗ΛٻΊΔํ๏ ▶ ࠶ؼతʹॲཧ͢Δࡍʹɺಉ࣌ʹ਺ྻΛιʔτ͢ΔΑ͏ʹ͢Δ ▶ Ϛʔδιʔτ Link ͱಉ͜͡ͱΛ͍ͯ͠Δ ▶ ιʔτࡁΈͰ͋Ε͹ɺస౗͍ͯ͠Δ΋ͷͷݸ਺͸ईऔΓ๏ͷΑ͏ʹٻ ΊΒΕΔ 3 1 4 1 5 9 2 6 ソート 数列 X 数列 Y 1 1 3 4 2 5 6 9 転倒: 1 個 tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 8 / 30
12. స౗਺ όϒϧιʔτͷަ׵ճ਺ X ͱ Y ͷؒͷస౗ΛٻΊΔํ๏ ▶ ࠶ؼతʹॲཧ͢Δࡍʹɺಉ࣌ʹ਺ྻΛιʔτ͢ΔΑ͏ʹ͢Δ ▶ Ϛʔδιʔτ Link ͱಉ͜͡ͱΛ͍ͯ͠Δ ▶ ιʔτࡁΈͰ͋Ε͹ɺస౗͍ͯ͠Δ΋ͷͷݸ਺͸ईऔΓ๏ͷΑ͏ʹٻ ΊΒΕΔ 3 1 4 1 5 9 2 6 ソート 数列 X 数列 Y 1 1 3 4 2 5 6 9 転倒: 1 個 tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 8 / 30
13. స౗਺ όϒϧιʔτͷަ׵ճ਺ ΍͍ͬͯΔ͜ͱશମΛݟΔͱɺϚʔδιʔτΛ͠ͳ͕Βస౗਺Λ਺͍͑ͯ Δ͜ͱʹଞͳΒͳ͍ 1 1 2 3 4 5 6 9 1 1 3 4 2 5 6 9 1 3 1 4 5 9 2 6 3 1 4 1 5 9 2 6 +1 +1 +1 +3 +2 tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 9 / 30
14. స౗਺ όϒϧιʔτͷަ׵ճ਺ ࣮૷ྫ tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 10 / 30
15. ;ͨͭͷ࿨ ;ͨͭͷ࿨ ௕͞ N ͷ਺ྻ A ͕͋ΔɻҎԼͷ৚݅Λຬͨ͢૊ i, j (i < j) ΛͦΕͧΕ਺ ͑Αɻ 1. Ai + Aj ≤ K Λຬͨ͢΋ͷ 2. Ai + Aj = K Λຬͨ͢΋ͷ ೖྗ੍໿ ▶ 1 ≤ N ≤ 105 ▶ 1 ≤ Ai ≤ 109 1 ͭΊͷ΄͏͕೉ͦ͠͏ʹݟ͑·͕͢ɺ࣮͸ 1 ͭΊͷղ๏Λ׆͔ͯ͠ 2 ͭ ΊΛղ͘ɺͱ͍͏ྲྀΕʹͳΓ·͢ tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 11 / 30
16. ;ͨͭͷ࿨ ▶ Ai + Aj ≤ K ͱͳΔ (i, j) Λ਺͑Δ͜ͱΛߟ͑Α͏ ▶ ઌఔͷʮస౗਺ʯͰ΍͍ͬͯͨईऔΓύʔτΛɺ ʮେখൺֱʯ͔Βʮ࿨ ͷൺֱʯʹม͑Δ͚ͩʂ ▶ ιʔτࡁΈ਺ྻ X, Y ʹରͯ͠ईऔΓΛ͢ΔͳΒ͹ɺX Λ߱ॱʹݟͯɺ Y ʹର͢ΔΧʔιϧΛঢॱʹಈ͔ͤ͹ɺ࿨͕ K ҎԼʹͳΔݸ਺Λईऔ ΓͰٻΊΒΕΔ ▶ Αͬͯɺઌ΄Ͳͱಉ͡ํ਑Ͱղ͚Δ tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 12 / 30
17. ;ͨͭͷ࿨ ▶ Ai + Aj = K ͱͳΔ (i, j) Λ਺͑Δ͜ͱΛߟ͑Α͏ ▶ ॏཁͳݴ͍׵͑: (࿨͕ͪΐ͏Ͳ K ͷݸ਺) ⇐⇒ (࿨͕ K ҎԼͷݸ ਺) − (࿨͕ K − 1 ҎԼͷݸ਺) ▶ ઌఔͷ໰୊Λ K ͷ৔߹ͱ K − 1 ͷ৔߹ʹ͍ͭͯղ͖ɺҾ͘͜ͱͰٻ ΊΒΕΔʂ ▶ ࣍ͷϖʔδͰ࣮૷Λࣔ͠·͢ tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 13 / 30
18. ;ͨͭͷ࿨ ͪΐ͏Ͳ K Ͱ͋Δ΋ͷΛٻΊΔ࣮૷ྫ tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 14 / 30
19. ໦ʹର͢Δ෼ׂ౷࣏ ▶ ઌ΄Ͳ·Ͱʮྻʹର͢Δ෼ׂ౷࣏ʯΛߟ͍͑ͯͨ ▶ ࣮͸ɺ໦ʹରͯ͠΋ಉ͡Α͏ͳ͜ͱ͕Ͱ͖Δʂ tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 15 / 30
20. ໦ͷॏ৺ ໦ͷॏ৺ ▶ N ௖఺ͷ໦ T ʹ͍ͭͯߟ͑Δ ▶ T ಺ͷ͋Δ௖఺ v ʹ͍ͭͯɺv ΛऔΓআ͘͜ͱͰͰ͖Δ෦෼໦ͷαΠ ζ͕શͯ N 2 ҎԼʹͳΔͱ͖ɺv Λʮ໦ͷॏ৺ʯͱݺͿ ໦ͷॏ৺ʹؔ͢Δॏཁͳࣄ࣮ ▶ ೚ҙͷ໦ʹରͯ͠ɺॏ৺ͱͳΔ௖఺͕ඞͣଘࡏ ▶ ೚ҙͷ໦ʹରͯ͠ɺॏ৺ͱͳΔ௖఺͸ߴʑ 2 ݸ ࢀߟʹͳΔϖʔδ ▶ πϦʔͷॏ৺෼ղͷਤղ (drken ͞Μ) Link ▶ ໦ͷॏ৺ྻڍΞϧΰϦζϜ (͜͏͖ ͞Μ) Link tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 16 / 30
21. ໦ͷॏ৺ ໦ͷॏ৺ ▶ N ௖఺ͷ໦ T ʹ͍ͭͯߟ͑Δ ▶ T ಺ͷ͋Δ௖఺ v ʹ͍ͭͯɺv ΛऔΓআ͘͜ͱͰͰ͖Δ෦෼໦ͷαΠ ζ͕શͯ N 2 ҎԼʹͳΔͱ͖ɺv Λʮ໦ͷॏ৺ʯͱݺͿ Figure: ໦ͷॏ৺Ͱͳ͍ྫ tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 17 / 30
22. ໦ͷॏ৺ ໦ͷॏ৺ ▶ N ௖఺ͷ໦ T ʹ͍ͭͯߟ͑Δ ▶ T ಺ͷ͋Δ௖఺ v ʹ͍ͭͯɺv ΛऔΓআ͘͜ͱͰͰ͖Δ෦෼໦ͷαΠ ζ͕શͯ N 2 ҎԼʹͳΔͱ͖ɺv Λʮ໦ͷॏ৺ʯͱݺͿ Figure: ໦ͷॏ৺Ͱ͋Δྫ tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 17 / 30
23. ໦ͷॏ৺ ▶ ໦Λॏ৺Ͱ෼ׂ͠ɺͦΕʹΑͬͯͰ͖ͨ෦෼໦Λͦͷॏ৺Ͱ෼ׂ ͠ɾɾɾͱ͍͏࠶ؼతͳॲཧΛߟ͑Δ ▶ ॏ৺Ͱ෼ׂͯ͠Ͱ͖Δ෦෼໦͸ɺݩͷ໦ͷαΠζͷ൒෼ҎԼʂ ▶ SegmentTree ͱಉ͡Α͏ʹߟ͑ΔͱɺO(log N) ͷਂ͞·Ͱ෼ׂ͢Ε͹ શͯόϥόϥʹ ▶ ઌఔͷʮྻʹର͢Δ෼ׂ౷࣏ʯͱಉ༷ʹ෼ׂ౷࣏Λߟ͑Δ͜ͱ͕Ͱ ͖Δʂ tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 18 / 30
24. ॏ৺ͷٻΊํ ▶ ॏ৺Λ࢖ͬͯ໦Λ෼ղ͢Ε͹෼ׂ౷࣏͕Ͱ͖ͦ͏Ͱ͋Δ͜ͱ͸Θ ͔ͬͨ ▶ Ͱ͸ɺॏ৺͸ͲͷΑ͏ʹٻΊΕ͹Α͍͔ʁ ॏ৺ΛٻΊΔΞϧΰϦζϜ  1. ໦ͷ௖఺ r Λద౰ʹબͼɺr Λࠜͱ͖ͨࠜͭ͠໦ʹ͢Δ 2. ֤௖఺ v ʹରͯ͠ɺv Λࠜͱ͢Δ෦෼໦ͷαΠζ subv ΛٻΊΔ 3. ֤௖఺ v ʹରͯ͠ɺv ͷ͢΂ͯͷࢠ c ʹ͍ͭͯ subc ≤ N 2 Ͱ͋Γɺ͔ ͭ N − subv ≤ N 2 Ͱ͋Δ৔߹ɺv ͸໦ͷॏ৺Ͱ͋Δ ▶ N − subv ͱ͸ɺv ͷ਌ํ޲ʹ͋Δ෦෼໦Λࢦ͍ͯ͠Δ tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 19 / 30
25. ॏ৺ͷٻΊํ ࣮૷ྫ tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 20 / 30
26. ॏ৺ͷٻΊํ ▶ ॏ৺ΛٻΊΔΞϧΰϦζϜ͸΋͏ͻͱͭ͋Δʂ ▶ ॏ৺෼ղ͢Δࡍ͸ɺॏ৺͸ 1 ͭٻ·Ε͹े෼ͳͷͰͪ͜ΒͷΞϧΰϦ ζϜΛ࢖͏͜ͱ͕ଟͦ͏ ॏ৺ΛٻΊΔΞϧΰϦζϜ   ▶ ໦ͷ௖఺ r Λద౰ʹબͼɺr Λࠜͱͨࠜ͠෇͖໦ʹ͢Δ ▶ ֤௖఺ v ʹରͯ͠ɺv Λࠜͱ͢Δ෦෼໦ͷαΠζ subv ΛٻΊΔ ▶ ॏ৺෼ղ͢Δࡍ͸ɺ͢Ͱʹ੾ͬͨ௖఺͸ߟྀ͠ͳ͍͜ͱʹ஫ҙʂ ▶ v ← r ͱ͢Δ ▶ while true: ▶ v ͷ͢΂ͯͷࢠ c ʹରͯͦ͠ͷ෦෼໦ͷαΠζ subc Λݟͯɺ࠷΋αΠ ζ͕େ͖͍௖఺ cmax ʹ͍ͭͯ subcmax > N 2 ͳΒ͹ɺv ← cmax ͱ͢Δ ▶ ͦ͏Ͱͳ͚Ε͹ɺv ͕໦ͷॏ৺Ͱ͋ΔͷͰ v Λฦ͢ tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 21 / 30
27. ॏ৺ͷٻΊํ ࣮૷ྫ tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 22 / 30
28. 6HAA ॏ৺෼ղͷ࿅श໰୊Λߟ͑ͯΈΑ͏ʂ 6HAA N ௖఺͔ΒͳΔ໦͕༩͑ΒΕɺ֤ลʹ͸ॏΈ li ͕͍͍ͭͯΔɻ͜ͷ໦ʹؚ ·ΕΔ௕͞ K ҎԼͷύεΛ਺্͑͛Αɻ ▶ 1 ≤ N ≤ 10, 000 ▶ 1 ≤ li ≤ 1, 000 ग़య: POJ 1741 Link ▶ ίʔυྔ͕ଟ͗ͯ͢εϥΠυʹషΕͳ͍ͷͰɺ࣮૷ྫ͸ল͖·͢ ▶ ͜Εͱ΍Δ͜ͱ͕΄΅ಉ͡໰୊ (ΈΜͳͷϓϩίϯ 2018 ܾউ C) ͷιʔείʔυͷϦ ϯΫΛ୅ΘΓʹషΔͷͰɺͦͪΒ΋ࢀߟʹ͍ͯͩ͘͠͞ ▶ ໰୊ Link ▶ ιʔείʔυ Link tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 23 / 30
29. 6HAA ▶ ໦Λॏ৺ g Ͱ෼ׂ͠ɺ͍͔ͭ͘ͷ෦෼໦ʹ෼͚Δ͜ͱΛߟ͑Δ ▶ ύε (u, v) ʹ͍ͭͯɺߟྀ͢΂͖৔߹͸ҎԼͷ 3 ௨Γ 1. u ΋ v ΋ಉ͡෦෼໦ʹଐ͢Δ 2. u ͱ v ͕ҟͳΔ෦෼໦ʹଐ͢Δ 3. u, v ͷ͍ͣΕ͔͕ g ͱҰக͢Δ ▶ ʮྻʹର͢Δ෼ׂ౷࣏ʯͰ΍ͬͨ͜ͱΛࢥ͍ग़͢ͱɾɾɾʁ u u v v v g g u tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 24 / 30
30. 6HAA ▶ ໦Λॏ৺ g Ͱ෼ׂ͠ɺ͍͔ͭ͘ͷ෦෼໦ʹ෼͚Δ͜ͱΛߟ͑Δ ▶ ύε (u, v) ʹ͍ͭͯɺߟྀ͢΂͖৔߹͸ҎԼͷ 3 ௨Γ 1. u ΋ v ΋ಉ͡෦෼໦ʹଐ͢Δ 2. u ͱ v ͕ҟͳΔ෦෼໦ʹଐ͢Δ 3. u, v ͷ͍ͣΕ͔͕ g ͱҰக͢Δ ▶ ʮྻʹର͢Δ෼ׂ౷࣏ʯͰ΍ͬͨ͜ͱΛࢥ͍ग़͢ͱɾɾɾʁ ▶ ύλʔϯ 1 ͸࠶ؼతʹॲཧՄೳ ▶ ύλʔϯ 2 ͸ɺg ͔Β֤௖఺·Ͱύεͷ௕͞Λશͯه࿥ͨ͠഑ྻΛιʔ τ͠ɺईऔΓ͢Δ͜ͱͰՄೳ ▶ ύλʔϯ 3 ͸ɺύλʔϯ 2 ʹର͢ΔॲཧͰ g Λʮڑ཭ 0 ͷ௖఺ʯͱΈ ͳͤ͹Մೳ u u v v v g g u tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 24 / 30
31. 6HAA ▶ ໦Λॏ৺ g Ͱ෼ׂ͠ɺ͍͔ͭ͘ͷ෦෼໦ʹ෼͚Δ͜ͱΛߟ͑Δ ▶ ύε (u, v) ʹ͍ͭͯɺߟྀ͢΂͖৔߹͸ҎԼͷ 3 ௨Γ 1. u ΋ v ΋ಉ͡෦෼໦ʹଐ͢Δ 2. u ͱ v ͕ҟͳΔ෦෼໦ʹଐ͢Δ 3. u, v ͷ͍ͣΕ͔͕ g ͱҰக͢Δ ▶ ʮྻʹର͢Δ෼ׂ౷࣏ʯͰ΍ͬͨ͜ͱΛࢥ͍ग़͢ͱɾɾɾʁ ▶ ύλʔϯ 1 ͸࠶ؼతʹॲཧՄೳ ▶ ύλʔϯ 2 ͸ɺg ͔Β֤௖఺·Ͱύεͷ௕͞Λશͯه࿥ͨ͠഑ྻΛιʔ τ͠ɺईऔΓ͢Δ͜ͱͰՄೳ ▶ ύλʔϯ 3 ͸ɺύλʔϯ 2 ʹର͢ΔॲཧͰ g Λʮڑ཭ 0 ͷ௖఺ʯͱΈ ͳͤ͹Մೳ ▶ ύλʔϯ 1 Λॏෳͯ͠਺͑ͳ͍Α͏ʹ஫ҙʂʂ u u v v v g g u tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 24 / 30
32. 6HAA ▶ ໦Λॏ৺ g Ͱ෼ׂ͠ɺ͍͔ͭ͘ͷ෦෼໦ʹ෼͚Δ͜ͱΛߟ͑Δ ▶ ύε (u, v) ʹ͍ͭͯɺߟྀ͢΂͖৔߹͸ҎԼͷ 3 ௨Γ 1. u ΋ v ΋ಉ͡෦෼໦ʹଐ͢Δ 2. u ͱ v ͕ҟͳΔ෦෼໦ʹଐ͢Δ 3. u, v ͷ͍ͣΕ͔͕ g ͱҰக͢Δ ▶ ʮྻʹର͢Δ෼ׂ౷࣏ʯͰ΍ͬͨ͜ͱΛࢥ͍ग़͢ͱɾɾɾʁ ▶ ύλʔϯ 1 ͸࠶ؼతʹॲཧՄೳ ▶ ύλʔϯ 2 ͸ɺg ͔Β֤௖఺·Ͱύεͷ௕͞Λશͯه࿥ͨ͠഑ྻΛιʔ τ͠ɺईऔΓ͢Δ͜ͱͰՄೳ ▶ ύλʔϯ 3 ͸ɺύλʔϯ 2 ʹର͢ΔॲཧͰ g Λʮڑ཭ 0 ͷ௖఺ʯͱΈ ͳͤ͹Մೳ ▶ ಉ༷ͷํ਑Ͱʮ௕͕ͪ͞ΐ͏Ͳ Kʯͷύε΋਺͑ΒΕ·͢ u u v v v g g u tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 24 / 30
33. ࠷ۙ఺ର ࠷ۙ఺ର ฏ໘্ʹ N ݸͷ఺ (xi, yi) ͕͋Δɻ࠷΋͍ۙ 2 ఺ͷڑ཭ΛٻΊΑɻ ▶ 2 ≤ N ≤ 105 ▶ −100 ≤ xi, yi ≤ 100 ͲͷΑ͏ͳ෼ׂΛߟ͑ͯɺ·ͱΊΕ͹Α͍͔ɾɾɾʁ tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 25 / 30
34. ࠷ۙ఺ର ▶ ఺ͷू߹Λɺx ࠲ඪΛج४ʹ൒෼ʹ෼͚ͯΈΑ͏ ▶ ఺ର (a, b) ʹ͍ͭͯɺߟྀ͢΂͖৔߹͸ҎԼͷ 2 ௨Γ 1. a, b ͕ಉ͡ྖҬ಺ʹଐ͢Δ 2. a, b ͕ҟͳΔྖҬ಺ʹଐ͢Δ (1) (2) tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 26 / 30
35. ࠷ۙ఺ର ▶ ఺ͷू߹Λɺx ࠲ඪΛج४ʹ൒෼ʹ෼͚ͯΈΑ͏ ▶ ఺ର (a, b) ʹ͍ͭͯɺߟྀ͢΂͖৔߹͸ҎԼͷ 2 ௨Γ 1. a, b ͕ಉ͡ྖҬ಺ʹଐ͢Δ 2. a, b ͕ҟͳΔྖҬ಺ʹଐ͢Δ ▶ ύλʔϯ 1 ͸࠶ؼతʹॲཧ͢Ε͹࣮ݱͰ͖ͦ͏ ▶ ύλʔϯ 2 ͸Ͳ͏͢Δʁ (1) (2) tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 26 / 30
36. ࠷ۙ఺ର ▶ ΄͍͠৘ใ͸ʮ࠷΋͍ۙ 2 ఺ͷڑ཭ʯͳͷͰɺͦΕʹͳΓ͑ͳ͍΋ͷ ͷ৘ใ͸͍Βͳ͍ ▶ ύλʔϯ 1 Λܭࢉͯ͠ɺ࠷ۙ఺ରͷڑ཭͕গͳ͘ͱ΋ d ҎԼͰ͋Δ͜ ͱ͕൑໌ͨ͠ͱ͢Δ d1 d2 d = min(d1, d2 ) tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 27 / 30
37. ࠷ۙ఺ର ▶ ύλʔϯ 2 ͷܭࢉ࣌ʹ͸ɺҎԼͷΑ͏ʹ෯ d ͷεϦοτ಺ʹ͋Δ఺ͩ ͚Λߟ͑ͯܭࢉ͢Ε͹ྑ͍ʂ ▶ ͜ͷεϦοτ಺ʹແ͍఺͸ɺͦ΋ͦ΋ڑ཭͕ d ΑΓେ͖͍ͨΊߟྀ͢Δ ඞཁ͕ͳ͍ ▶ εϦοτ಺ʹ͋Δ఺ͷ਺͸ඇৗʹগͳ͍͜ͱ͕ূ໌Մೳ (ৄ͘͠͸ٜຊ P.325 Λࢀর) d1 d2 d = min(d1, d2 ) d d tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 28 / 30
38. ࣮૷ྫ ෼ׂ͸ x ࠲ඪʹ͍ͭͯߦ͍ɺͦͷޙ y ࠲ඪͰιʔτ͠௚࣮ͯ͠૷͍ͯ͠ ·͢ tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 29 / 30
39. ࿅श໰୊ ෼ׂ౷࣏ʹؔ͢Δ࿅श໰୊ ▶ POJ 1854: Evil Straw Warts Live Link ▶ GCJ 2009 World Finals B: Min Perimeter Link ▶ Yandex. Algorithm 2011 Finals B: Superset Link ▶ POJ 2114: Boatherds Link ▶ UVa 12161: Ironman Race in Treeland Link ▶ SPOJ QTREE5: Query on a tree V Link ▶ hamayan ͞Μͷϒϩάʹ΋ؔ࿈໰୊͕๛෋ʹࡌ͍ͬͯ·͢ʂ Link tsutaj (Hokkaido Univ.) ෼ׂ౷࣏๏ February 7, 2019 30 / 30