Rustで始める競技プログラミング

Rustで始める競技プログラミング

Transcript

1. 3VTU
   Ͱ࢝ΊΔ
   ڝٕϓϩάϥϛϯά NJOBNJOBP SPQQPOHJST
   
2. Ԭೆ
   ௚࠸
   NJOBNJOBP
   !WJOBNJ ࣗݾ঺հ ஜ೾େֶ
   ৘ใֶ܈
   ৘ใՊֶྨ
   ೥
   d
   -BZFS9
   3%
   νʔϜ
3. 
   ڝϓϩͱ͸
   
   ಘΒΕΔ΋ͷ
   
   ఺໰୊
   ໨࣍ 
   ఺໰୊
   
   ఺໰୊
   
   ·ͱΊ
   
4. ڝٕϓϩάϥϛϯάͱ͸
   
   ໰୊͕༩͑ΒΕΔ
   
   ɾ࣮ߦ࣌ؒͱϝϞϦ࢖༻ྔͷ্ݶ෇͖
   
   
   ͦΕΛղ͘ϓϩάϥϜΛ࣮૷ˍఏग़
   
   
   αʔόʔ͕ਖ਼ղ͔൑ఆ ղ͚ͨ໰୊਺͕ଟ͍ํ͕উͪ
5. ڝϓϩͰಘΒΕΔ΋ͷ
   ɾϓϩάϥϛϯάݴޠͷ஌ࣝͱ࣮૷ྗ
   
   ɾ໰୊ղܾྗɺ࿦ཧతࢥߟྗɺ਺ֶྗ
   
   ɾߴ଎ͳϓϩάϥϜͷ࣮૷ํ๏
   
   ΞϧΰϦζϜͱσʔλߏ଄
6. ΞϧΰϦζϜͱσʔλߏ଄ ૊߹ͤ਺ֶɺแআݪཧɺ෼ׂ਺ɺηάϝϯτπϦʔɺฏํ෼ׂɺώʔϓɺ#JOBSZ
   *OEFYFE
   5SFFɺฏߧೋ෼୳ࡧ໦ɺ࠲ඪѹॖɺLE໦ɺ6OJPO'JOEɺಈత࠷దԽɺήʔ Ϝཧ࿦ɺ࠷௕૿Ճ෦෼ྻɺ८ճηʔϧεϚϯ໰୊ɺ࠷খแؚٿɺزԿɺ࠷খॏΈࡾ֯ ܗ෼ׂɺάϥϑཧ࿦ɺ࠷୹ܦ࿏໰୊ɺ໦ɺ-PXFTU
   $PNNPO
   "ODFTUPSɺϚονϯάɺ ด࿏ݕग़ɺ࠼৭਺ɺ-PXMJOLɺ࠷খશҬ໦ɺτϙϩδΧϧιʔτɺڧ࿈݁੒෼෼ղɺ ᩦཉ๏ɺઢܗ୅਺ɺΨ΢εͷফڈ๏ɺ਺࿦ɺೋ߲܎਺ɺ($%-$.ɺૉҼ਺෼ղɺ ਺஋ղੳɺೋ෼๏ɺϥάϥϯδϡิؒɺιʔτɺస౗਺ɺ.BOBDIFSɺ.PSSJTr1SBUUɺ ϩʔϦϯάϋογϡɺ4V⒏Y
   "SSBZɺ;
   "MHPSJUINɺ͠Ό͘ͱΓ๏ɺ౳ ͜ΕΒ Ұྫ Λཧղˍ࢖͑ΔΑ͏ʹͳΔ
7. ૣ଎΍ͬͯΈΔ
   3VTUͰʂ
8. "#$
   "
   
   1SPEVDU
   IUUQTBUDPEFSKQDPOUFTUTBCDUBTLTBCD@B
   
9. "#$
   "
   
   1SPEVDU
   ఺ wਖ਼੔਺B C͕ඪ४ೖྗ͔Β༩͑ΒΕΔ
   wۭന۠੾Γ
   wB C͕ۮ਺ͳΒ&WFOΛح਺ͳΒ0EEΛग़ྗ
   wB
   C
   
   
   ໰୊֓ཁ
10. wඪ४ೖྗΛ࢖͏
    
    VTF
    TUEJP
    wۮ਺͔Ͳ͏͔
    JG
    B
    
    C
    
    
    
    
    ϙΠϯτ "#$
    "
    
    1SPEVDU
    ఺
    w IUUQTBUDPEFSKQDPOUFTUTBCDTVCNJTTJPOT
    ղ౴ྫ
11. "#$
    "
    
    1SPEVDU
    
    ղ౴ྫ
12. "#$
    "
    
    1SPEVDU
    
    ղ౴ྫ ೖྗΛָʹ͍ͨ͠ʂ
13. ۭനɾվߦ͝ͱʹೖྗΛಘΔؔ਺
14. ۭനɾվߦ͝ͱʹೖྗΛಘΔؔ਺ w 3VTUͰڝٕϓϩάϥϛϯάͷೖྗΛεοΩϦهड़͢ΔϚΫϩ
    
    2JJUB
    CZ
    ͨͳ͜;͞Μ
    w IUUQTRJJUBDPNUBOBLIJUFNTCBDDBDEEBD ߋʹߴػೳͳೖྗิॿ Θ͔Γ΍͍͢
15. "#$
    "
    
    1BSLJOH
    IUUQTBUDPEFSKQDPOUFTUTBCDUBTLTBCD@B
    
16. "#$
    "
    
    1SPEVDU
    ఺ wறं৔ͷྉۚϓϥϯ͕छྨ
    wϓϥϯ
    5࣌ؒͰ" 5ԁ
    wϓϥϯ
    #ԁݻఆ
    wਖ਼੔਺/ " #͕༩͑ΒΕΔ
    w/࣌ؒறं͢Δͱ͖ͷ࠷҆ͷ஋ஈ͸ʁ ໰୊֓ཁ
17. wNJOؔ਺
    
    VTF
    TUEDNQNJO
    wNJO B C
    ϙΠϯτ "#$
    "
    
    1SPEVDU
    ఺
18. ୅දతίϯςεταΠτ AtCoder Codeforces Google Code Jam ։࠵ස౓ 1,2ճ/ि 6ճ͘Β͍/݄ 1ճ/೥ ࢀՃਓ਺/ճ ໿5000ਓ ໿10000ਓ ໿35000ਓ ։࠵ࠃ ೔ຊ ϩγΞ - ໰୊จ ೔ຊޠ / ӳޠ ӳޠ ӳޠ Rust version 1.15.1 1.35.0 ະରԠ
19. ఺਺ ఺਺ Ϩϕϧ 100 ࢛ଇԋࢉ, จࣈྻૢ࡞ 200 ৚݅෼ذ, ϧʔϓ 300 ιʔτͳͲͷΞϧΰϦζϜͷ஌͕ࣝඞཁʹ 400 ~ ܭࢉྔͷݟੵ΋Γ͕ඞཁʹ 2000఺Ҏ্ͷ໰୊΋
20. "#$
    #
    
    
    
    IUUQTBUDPEFSKQDPOUFTUTBCDUBTLTBCD@C
    
21. "#$
    #
    
    
    
    ఺ wਖ਼੔਺B C͕ඪ४ೖྗ͔Β༩͑ΒΕΔ
    wۭന۠੾Γ
    wBͱCΛจࣈྻͱͯ͠ܨ͛ͨͱ͖ฏํ਺͔ʁ
    wྫ
    l
    z
    ͸
    
    
    ?
    wฏํ਺ͳΒ:FTɺͦ͏Ͱͳ͍ͳΒ/PΛग़ྗ
    wB
    C
    
    
    ໰୊֓ཁ
22. wจࣈྻ݁߹
    
    GPSNBU l\^\^z B C
    w4USJOH
    UP
    JTJ[F
    TQBSTFJTJ[F VOXSBQ
    ϙΠϯτ "#$
    #
    
    
    
    ఺
    w Y
    
    BͱCΛ݁߹ͨ͠਺஋
    w JdY
    ·Ͱ
    J J
    
    Y
    Λຬͨ͢΋ͷ͕ଘࡏ͢Δ͔ௐ΂Δ
    w ଘࡏ͢ΔͳΒY͸ฏํ਺
    ղ౴ྫ
23. "#$
    #
    
    
    
    
    ղ౴ྫ ͜ͷղ๏ͷܭࢉྔ͸0 Y
    ߋʹྑ͍ղ๏
    ɾJd㲋YͰ୳ࡧ
    0 㲋Y
    ɾJʹ͍ͭͯೋ෼୳ࡧ
    0 MPH
    Y
    
24. ܭࢉྔ ྫ 1ඵҎ಺Ͱ O(1) ࢛ଇԋࢉͳͲ - O(n) n=໿10^8·Ͱ O(n^2) n=໿10^4·Ͱ O(log n) ೋ෼୳ࡧͳͲ ͨ͘͞Μ O(n log n) ιʔτͳͲ n=໿10^5·Ͱ ܭࢉྔ w0 O
    
    Oճܭࢉ͢ΔͳΒ0 O
    wఆ਺ഒ͸ແࢹ
    Oճܭࢉ͢Δͱͯ͠΋0 O #JH
    0
    ه๏
25. "#$
    #
    
    7BSJFE
    IUUQTBUDPEFSKQDPOUFTUTBCDUBTLTBCD@C
    
26. "#$
    #
    
    7BSJFE
    ఺ wӳখจࣈ͔ΒͳΔจࣈྻ4͕༩͑ΒΕΔ
    w4ʹؚ·ΕΔจࣈ͕શͯҟͳΔ͔Ͳ͏͔
    wҟͳΔͳΒZFTɺͦ͏Ͱͳ͍ͳΒOPΛग़ྗ
    w4ͷ௕͞
    
     ໰୊֓ཁ
27. "#$
    #
    
    7BSJFE
    
    ղ౴ྫ w4USJOH
    ͸
    T<J>
    ͷΑ͏ʹจࣈͷऔಘ͕Ͱ͖ͳ͍
    w4USJOH
    ͔Β
    7FDDIBS
    ʹม׵͢Δ
    ϙΠϯτ
28. "#$
    $
    
    1SJTPO
    IUUQTBUDPEFSKQDPOUFTUTBCDUBTLTBCD@D
    
29. "#$
    $
    
    1SJTPO
    ఺ w/ຕͷ*%Χʔυ
    .ຕͷήʔτ
    wήʔτ͸*%ΧʔυͰ௨ΕΔ
    wJ൪໨ͷήʔτ͸
    -@J
    d
    3@J
    ൪໨ͷ*%ΧʔυͰ௨ΕΔ
    wͲΕ͔͍ͭ࣋ͬͯΕ͹͍͍
    wຕ͚ͩͰશήʔτΛ௨աͰ͖Δ*%Χʔυ͸Կຕ͔
    w/
    
    ?
    .
    
    ?
    w
    
    -@J
    
    3@J
    
    / ໰୊֓ཁ
30. 4BNQMF
     ID1 ID2 ID3 ID4 G1 G2 /
    .
    -@
    3@
    
    
    
    -@
    3@
    
    
     ൪໨ͱ൪໨ͷ*%Χʔυ͕શήʔτΛ௨ΕΔ
31. 4BNQMF
     ID1 2 3 4 5 6 7 8 9 10 G1 G2 G3 ൪໨ͷ*%ΧʔυͷΈશήʔτΛ௨ΕΔ
32. "#$
    $
    
    1SJTPO
    
    ղ౴ྫ
33. "#$
    $
    
    0UPTIJEBNB
    IUUQTBUDPEFSKQDPOUFTUTBCDUBTLTBCD@D
    
34. "#$
    $
    
    0UPTIJEBNB
    ఺ wԁࡳɺԁࡳɺԁࡳ͕ແݶʹ͋Δ
    w͓ࡳ͕/ຕɺ߹ܭ:ԁ
    wԁࡳYຕɺԁࡳZຕɺԁࡳ[ຕͱ͢Δ
    w༗ΓಘΔຕ਺ͷ૊߹ͤͭΛग़ྗ
    w:ԁͳΒɺ Y Z [
    
      
    ͳͲ ໰୊֓ཁ
35. 5-&ղ౴
36. 5-&ղ౴
    0 O? O? ?
    ؒʹ߹Θͳ͍
37. "$ղ౴
    0 O?
38. ·ͱΊ
39. ·ͱΊ wѹ౗తΞ΢τϓοτ͕Ͱ͖Δ
    wܭࢉྔ͕ݟੵ΋ΕΔΑ͏ʹͳΔ
    wΞϧΰϦζϜͱσʔλߏ଄ʹৄ͘͠ͳΕΔ
    w࣮ྗ͕ఆྔԽ͞ΕΔ
    wԿΑΓָ͍͠
    w࣮ߦʹ೥͔͔Δॲཧ͕ඵͰͰ͖ͨΓ
    w೔ʹ೔ʹίʔσΟϯάεϐʔυ͕଎͘ͳͬͨΓ
40. ͓·͚ʢPKʹΑΔࣗಈఏग़ʣ IUUQTHJUIVCDPNNJOBNJOBPBUDPEFSSVTUCMPCNBTUFSWTDPEFUBTLTKTPO IUUQTHJUIVCDPNLNZLPOMJOFKVEHFUPPMT