AHC028解説

AtCoder Heuristic Contest 028（ https://atcoder.jp/contests/ahc028 ）の解説放送で使用した解説スライドです。

Transcript

1. © ALGO ARTIS Co.,Ltd. ")$
   ղ๏εϥΠυ  גࣜձࣾ"-(0
   "35*4
2. © ALGO ARTIS Co.,Ltd. ໰୊จ;Γ͔͑Γ
3. © ALGO ARTIS Co.,Ltd. ղ๏ྫͷղઆ
4. © ALGO ARTIS Co.,Ltd. ղ๏πϦʔ ᩦཉ ᩦཉ ॏͳΓߟྀ %1 ᩦཉ ϏʔϜαʔν ୯ޠͷϚʔδ ۙ๣ͷ௥Ճ ୯ޠͷϚʔδ ۙ๣ͷߜΓࠐΈ %1 ධՁؔ਺มߋ ম͖ͳ·͠
5. © ALGO ARTIS Co.,Ltd. ᩦཉ ᩦཉ ᩦཉ ॏͳΓߟྀ %1 ᩦཉ ϏʔϜαʔν ୯ޠͷϚʔδ ۙ๣ͷ௥Ճ ୯ޠͷϚʔδ ۙ๣ͷߜΓࠐΈ %1 ධՁؔ਺มߋ ম͖ͳ·͠
6. © ALGO ARTIS Co.,Ltd. ᩦཉ ·ͣ͸ᩦཉΛͯ͠ΈΔɻ • ͱΓ͋͑ͣԑىͷྑ͍୯ޠΛ൪໨͔Βॱ൪ʹूΊͯΈΔɻ • "#$%&
   '()*+
   ,-./0 ͷͭͷ୯ޠΛूΊ͍ͨͳΒɺ ͱΓ͋͑ͣ "#$%&'()*+,-./0
   ͱ͍͏ॱ൪Ͱ๚ΕͯΈΔɻ • ϚεΛશ୳ࡧͯ͠ɺҰ൪ίετͷখ͍͞ϚεʹҠಈ͢Δᩦཉ Λ܁Γฦ͢ɻ D A C B D C B A D D A C B D C B A D D A C B D C B A D   ఺ Ґ૬౰
7. © ALGO ARTIS Co.,Ltd. ᩦཉ ॏͳΓߟྀ લޙͷ୯ޠͷؒͰڞ௨͢Δ෦෼͸·ͱΊͯ͠·͏ɻ • "#$%&
   &'()*
   )*+,- ͷͭͷ୯ޠΛूΊ͍ͨͱ͖ɺ ୯७ʹ୯ޠΛܨ͛Δ͚ͩͩͱ "#$%&&'()*)*+,-
   ͱͳΓ ແବʹͳͬͯ͠·͏ɻ • લޙͷ୯ޠͰॏͶΒΕΔ෦෼Λݕग़ͯ͠ɺ ॏͳΔՕॴ͸εΩοϓ͠ͳ͕ΒᩦཉΛߦ͏ɻ " # $ % & & ' ( ) * ) * + , - " # $ % & ' ( ) * + , -   ఺ Ґ૬౰
8. © ALGO ARTIS Co.,Ltd. ॏͳΓͷൃੜ͢Δ֬཰ʹ͍ͭͯ Ͳͷ͘Β͍ॏͳΓ͕ൃੜ͢Δ͔Λݟੵ΋Γɺํ਑ΛཱͯΔͨΊͷࢀߟͱ͢Δɻ • ͋Δ୯ޠ 𝑡! ͷ຤ඌ 𝑚 จࣈͱɺ͋Δ୯ޠ 𝑡!! ͷઌ಄ 𝑚 จࣈ͕ॏͳΒͳ͍֬཰ 𝑝 ͸ɺ 𝑝 = 1 − " #$ % • ͋Δ୯ޠ 𝑡! ʹ͍ͭͯɺ 𝑚 จࣈҎ্ॏͳΔ୯ޠ͕ͭҎ্ଘࡏ͢Δ֬཰ 𝑞 ͸ɺ 𝑞 = 1 − 𝑝&'" = 1 − 1 − " #$ % &'" • ࣮ࡍʹܭࢉͯ͠ΈΔͱɺ จࣈॏͳΓ·Ͱ͸݁ߏൃੜͦ͠͏ ͱ͍͏͜ͱ͕෼͔Δɻ 𝒎 𝒒 𝟐𝟎𝟎𝒒            
9. © ALGO ARTIS Co.,Ltd. %1 ࠷ऴతͳจࣈྻ 𝑆 ͕ܾ·Ε͹ɺ࠷దͳܦ࿏͸%1ͰٻΊΒΕΔɻ • 𝑑𝑝 𝑙 𝑖 𝑗 ≔ จࣈྻ 𝑆 ͷ 𝑙 จࣈ໨·Ͱ֬ఆ͓ͯ͠Γɺ Ϛε 𝑖, 𝑗 ʹࢦ͕͋Δͱ͖ͷ࠷খίετ ͱఆٛ͢Δɻ • ࣮૷্͸ 𝑆( = 𝐴),+ ͱͳΔϚε͚ͩߟ͑ͯ%1͢Ε͹Α͍ɻ C C A B D C A B C C C A B D C A B C C C A B D C A B C C C A B D C A B C 3 3 5 5 7 8 8 7 0   ఺ Ґ૬౰
10. © ALGO ARTIS Co.,Ltd. %1 ᩦཉ ͜ͷ%1Λ࢖ͬͯɺ୯ޠΛܨ͛Δॱ൪Λ࠷దԽ͍ͯ͘͠ɻ • 𝑆 ͷ຤ඌʹ௥Ճ͢Δ୯ޠ 𝑡! Λશ୳ࡧ͠ɺ ίετ͕࠷খͱͳΔ୯ޠΛબͿᩦཉΛߦ͏ɻ "#$%&'() *+,-. ()*+, )*+,- 7 8 9 21 17 17 19 18 16    ఺ Ґ૬౰
11. © ALGO ARTIS Co.,Ltd. ධՁؔ਺ͷมߋ ੜͷίετΑΓྑ͍ධՁؔ਺͕ͳ͍͔ߟ͑ͯΈΔɻ • ੜͷίετΛͦͷ··ධՁؔ਺ʹ͢Δͱɺ ʮۙ͘ʹ͋Δ୯ޠʯΑΓʮ΋ͱ΋ͱ୹͍୯ޠʯΛ ༏ઌͯ͠͠·͏ͷͰྑ͘ͳͦ͞͏ɻ A B C C B F E F D E A F B C E F C D E B "#$ ίετ %&' ίετ
12. © ALGO ARTIS Co.,Ltd. ධՁؔ਺ͷมߋ • ʮͦͷ୯ޠͷΈΛߟ͑ͯ%1ͨ͠ͱ͖ͷ࠷খίετʯΛ ϕʔείετͱݺͿ͜ͱʹ͢Δɻ • ʮ ίετ
    — ϕʔείετ ʯΛධՁ஋ͱ͢Δ͜ͱͰɺ ͲΕ͚ͩ༨ܭʹҠಈ͔ͨ͠ΛධՁͰ͖ɺੑೳ͕޲্͢Δɻ A B C C B F E F D E A F B C E F C D E B "#$ ίετ ϕʔείετ ධՁ஋ %&' ίετ ϕʔείετ ධՁ஋    ఺ Ґ૬౰
13. © ALGO ARTIS Co.,Ltd. ϏʔϜαʔν ᩦཉ ᩦཉ ॏͳΓߟྀ %1 ᩦཉ ϏʔϜαʔν ୯ޠͷϚʔδ ۙ๣ͷ௥Ճ ୯ޠͷϚʔδ ۙ๣ͷߜΓࠐΈ %1 ධՁؔ਺มߋ ম͖ͳ·͠
14. © ALGO ARTIS Co.,Ltd. ϏʔϜαʔν ᩦཉΛϏʔϜαʔνʹॻ͖׵͑ͯΈΔɻ • ֤ঢ়ଶͷධՁؔ਺͸৭ʑߟ͑ΒΕΔ͕ɺࠓճ͸ %1ςʔϒϧͷ࠷খ஋
    — ࢖ͬͨ୯ޠͷϕʔείετͷ࿨ ͱͨ͠ɻ ίετ ࢒Γͷ୯ޠͷਪఆίετͷ૯࿨ ͱ΋ݴ͍׵͑ΒΕΔɻ • ֤୯ޠʹ͍ͭͯɺελʔτ஍఺ผͷ%1ςʔϒϧΛલܭࢉ͢Δͱ ਺ഒఔ౓ͷߴ଎ԽʹͳΔɻ • ࢼͨ͠ͱ͜ΖɺϏʔϜ෯͸ఔ౓ʹͳͬͨɻ    ఺ Ґ૬౰
15. © ALGO ARTIS Co.,Ltd. ϏʔϜαʔν ୯ޠͷϚʔδ ϏʔϜαʔνΛޮ཰Խ͢Δํ๏ʹ͍ͭͯߟ͑Δɻ • ϏʔϜαʔνͷܭࢉίετ͸֓Ͷ 𝑀# ʹൺྫ͢Δɻ • ໌Β͔ʹ࿈ଓͤͨ͞ํ͕ྑ͍୯ޠ 𝑡! ͱ 𝑡!! ʹ͍ͭͯɺ ࣄલʹ୯ޠΛϚʔδͯ͠͠·͏ͱ 𝑀 Λখ͘͞Ͱ͖Δɻ • ͨͩ͠ɺॏͶΕ͹ྑ͍ͱ͍͏΋ͷͰ΋ͳ͍ɻ ԿจࣈॏͳΔ͔͚ͩͰ൑அ͢Δͱٯʹίετ͕૿Ճ͢Δ͜ͱ΋ɻ A C B D E H G F D E A C B D E H G F D E A C B D E H G F D E → + "#$%& %&'() "#$%&'()
16. © ALGO ARTIS Co.,Ltd. ϏʔϜαʔν ୯ޠͷϚʔδ • ͜͜Ͱ΋ઌ΄Ͳͷϕʔείετͷߟ͑ํ͕࢖͑Δɻ • จࣈྻ 𝑠 ͷϕʔείετΛ 𝑏𝑎𝑠𝑒 𝑠 ͱͯ͠ɺ 𝑏𝑎𝑠𝑒 𝑡! + 𝑏𝑎𝑠𝑒 𝑡!! ≥ 𝑏𝑎𝑠𝑒 𝑡! 𝑡!! + 𝑋Ͱ͋Ε͹Ϛʔδͯ͠ΈΔɻ • ͜͜Ͱɺ 𝑋 ͸࣮ݧతʹܾΊΔద౰ͳύϥϝʔλɻ ςετϓϨʔͰ͸ 𝑋 = 0 ͘Β͍͕ྑͦ͞͏Ͱ͋ͬͨɻ A F B C E F C D E B A F B C E F C D E B A F B C E F C D E B 𝑏𝑎𝑠𝑒 ABCDEF = 19 𝑏𝑎𝑠𝑒 ABCD = 15 𝑏𝑎𝑠𝑒 CDEF = 8 ≥ + + 𝑋
17. © ALGO ARTIS Co.,Ltd. ϏʔϜαʔν ୯ޠͷϚʔδ • ͜ΕʹΑΓ୯ޠ਺Λ͔Βʙ͘Β͍·ͰݮΒͤͨɻ • ϏʔϜ෯͸έʔεόΠέʔε͕ͩɺఔ౓·Ͱ৳͹ͤͨɻ • ͦͷଞɺʮޙ൒΄ͲϏʔϜ෯Λ޿͘͢Δʯ ʮखઌಡΈͨ͠ධՁؔ਺Λ༻͍ΔʯͳͲͷ޻෉ΛೖΕͨɻ    ఺ Ґ૬౰
18. © ALGO ARTIS Co.,Ltd. ম͖ͳ·͠ ᩦཉ ᩦཉ ॏͳΓߟྀ %1 ᩦཉ ϏʔϜαʔν ୯ޠͷϚʔδ ۙ๣ͷ௥Ճ ୯ޠͷϚʔδ ۙ๣ͷߜΓࠐΈ %1 ධՁؔ਺มߋ ম͖ͳ·͠
19. © ALGO ARTIS Co.,Ltd. ম͖ͳ·͠ ࢖͏୯ޠͷॱ൪͕෼͔Ε͹%1Ͱ࠷దղ͕ٻΊΒΕΔͷͰɺ ॱ൪Λম͖ͳ·͠Ͱ࠷దԽ͢Δɻ • ۙ๣
    ͭͷ୯ޠΛ࡟আ͠ɺϥϯμϜͳ৔ॴʹૠೖ͢Δɻ • είΞܭࢉ͸ී௨ʹ%1ɻؤுΔͱສճ͘Β͍ճΔɻ • ͋·Γڧ͘ͳ͘ɺݡ͍ᩦཉʹෛ͚Δɻ 𝑡" 𝑡# 𝑡, 𝑡- 𝑡. 𝑡$ 𝑡/ 𝑡" 𝑡. 𝑡# 𝑡, 𝑡- 𝑡$ 𝑡/ 𝑆: 𝑆′:    ఺ Ґ૬౰
20. © ALGO ARTIS Co.,Ltd. ম͖ͳ·͠ ۙ๣ͷ௥Ճ ۙ๣Λ௥Ճͯ͠վળΛࢼΈΔɻ • 541ͷΑ͏ʹɺ͍͔ͭ͘·ͱΊͯҠಈͤͯ͞ΈΔ͜ͱʹ͢Δɻ • ۙ๣
    ϥϯμϜͳՕॴͰ੾ͬͯɺྻΛೖΕସ͑Δɻ • ۙ๣ ϥϯμϜͳՕॴͰ੾ͬͯɺྻΛೖΕସ͑Δɻ 𝑡! 𝑡" 𝑡# 𝑡$ 𝑡% 𝑡& 𝑡' 𝑡! 𝑡" 𝑡% 𝑡& 𝑡' 𝑡# 𝑡$ 𝑡! 𝑡" 𝑡# 𝑡$ 𝑡% 𝑡& 𝑡' 𝑡! 𝑡$ 𝑡% 𝑡& 𝑡" 𝑡# 𝑡'    ఺ Ґ૬౰
21. © ALGO ARTIS Co.,Ltd. ম͖ͳ·͠ ୯ޠͷϚʔδ ϏʔϜαʔνͱಉ༷ʹ୯ޠͷϚʔδΛࢼΈΔɻ • ୯ޠ਺͕ݮΔͱʮείΞܭࢉ͕ߴ଎Խ͞ΕΔʯ ʮۙ๣ͷީิ਺͕ݮΔʯͱ͍͏ೋॏͷϝϦοτΛड͚ΒΕΔɻ • େ͖͘վળ͠ɺϏʔϜαʔνͱ֓Ͷಉఔ౓ͷείΞʹͳΔɻ    ఺ Ґ૬౰
22. © ALGO ARTIS Co.,Ltd. ম͖ͳ·͠ ۙ๣ͷߜΓࠐΈ ۙ๣
    ͷडཧ཰͕ҎԼͱ͔ͳΓ௿͍ͨΊɺվળΛࢼΈΔɻ • ྑͦ͞͏ͳۙ๣ΛࣄલʹߜΓࠐΊΕ͹ޮ཰্͕͕Δ͸ͣɻ • ୯ޠͷ૊ 𝑡!, 𝑡!! ʹ͍ͭͯɺ૬ੑͷྑ͞ 𝑓 𝑡!, 𝑡!! Λ 𝑓 𝑡! , 𝑡!! = 𝑏𝑎𝑠𝑒 𝑡! + 𝑏𝑎𝑠𝑒 𝑡!! − 𝑏𝑎𝑠𝑒 𝑡! 𝑡!! ͱఆٛ͢Δɻ • ྑ͍ղͰ͸ྡΓ߹͏୯ޠͷ૊ 𝑡!, 𝑡!1" ͷ૬ੑͷྑ͕͞ ൺֱతେ͖͍஋ʹͳ͍ͬͯΔ͸ͣɻ A F B C E F C D E B A F B C E F C D E B A F B C E F C D E B 𝑏𝑎𝑠𝑒 ABCDEF = 19 𝑏𝑎𝑠𝑒 ABCD = 15 𝑏𝑎𝑠𝑒 CDEF = 8 − + = 4
23. © ALGO ARTIS Co.,Ltd. ম͖ͳ·͠ ۙ๣ͷߜΓࠐΈ • 1 ͔Β 𝑀 ·Ͱͷॱྻ 𝑃 ʹ͍ͭͯɺྡΓ߹͏୯ޠಉ࢜ͷ૬ੑͷ૯࿨ 𝑔 𝑃 = ∑)2" &'" 𝑓 𝑡3" , 𝑡3"#$ Λߟ͑Δɻ • ֤छۙ๣Λద༻ͨ͠ͱ͖ͷ 𝑔 𝑃 ͷมԽྔ Δ𝑔 ͸ 𝑂 1 ͰܭࢉͰ͖Δɻ • Δ𝑔 ͕ద౰ͳᮢ஋ 𝑇 ະຬͷ৔߹͸ࢬמΓ͢Δ͜ͱʹ͢Δɻ ࠓճ͸ 𝑇 = −1 ͱͨ͠ɻ • ۙ๣
    ͷडཧ཰͸ʙఔ౓·Ͱվળɻ • ซͤͯɺϚʔδ൑அͷᮢ஋ 𝑋 ΋࠶ௐ੔͓ͯ͘͠ɻ ࠓճ͸ 𝑋 = −3 ͘Β͍ʢϚʔδগͳΊʣ͕ྑͦ͞͏ͩͬͨɻ • ࣌ؒͰ͜͜·Ͱߦ͚ͨΒੌ͗͢Ͱ͢ʜʜɻ    ఺ Ґ૬౰
24. © ALGO ARTIS Co.,Ltd. ࡞໰ཪ࿩
25. © ALGO ARTIS Co.,Ltd. ࡞໰ཪ࿩ ୊ࡐ • ݄։࠵ͳͷͰɺԿ͔ਖ਼݄ͬΆ͍΋ͷΛ୊ࡐʹ͠Α͏ͱߟ͍͑ͯͨΒࢥ͍෇͍ͨɻ • ୹ظίϯͱ͍͏͜ͱͰɺͰ͖Δ͚ͩγϯϓϧͳ໰୊ઃఆΛ໨ࢦͨͭ͠΋Γɻ • จࣈྻབྷΈͷ໰୊͸ٱ͠ৼΓͳ͸ͣʁ")$͸ώϯτʹͳ͔ͬͨ΋ɻ ௐ੔ • ϏʔϜαʔνɾম͖ͳ·͠ͷͲͪΒ΋ಉఔ౓ͷείΞΛग़ͤΔΑ͏ʹͨͭ͠΋Γɻ • ͳͷ͕ͩɺҰࡢ೔ΞΠσΞ͕͖߱ͬͯͯম͖ͳ·͠ͷํ͕ڧ͘ͳͬͯ͠·ͬͨʜʜɻ • ҰԠͲͪΒͰ΋୹ظϖʔδ໨͘Β͍·ͰͳΒૂ͑Δʁ • ͨͩম͚ͩ͘Ͱ͸্ʹߦ͚ͳ͍͘Β͍ͷ੍໿ʹͳͬͨ͸ͣʁ • ݪҊͱXSJUFSղΛXBUB͞Μʹ౉ͨ͠Βѹ౗తͳείΞࠩͰഊ๺ʜʜɻ • ΞυόΠεΛ௖͍͓͔ͨ͛Ͱ͍ͩͿ໰୊΋ϒϥογϡΞοϓ͞Εͨ͸ͣɻ
26. © ALGO ARTIS Co.,Ltd.