競プロのすすめ

社内勉強会で競技プログラミングを広めるために作成した資料を社外用に加工したもの

Transcript

1. ڝϓϩͷ͢͢Ί @_uya116
2. ಄ʹු͔ͿΠϝʔδɿυϥϚʹग़ͯ͘ΔϋοΧʔతͳ ͦ΋ͦ΋ڝϓϩͱ͸ʁ 2
3. ࣮ࡍɿͳͧͱ͖ʹ͍ۙ ͦ΋ͦ΋ڝϓϩͱ͸ʁ 3
4. ໰୊ͷδϟϯϧ͸༷ʑͰɺ਺ֶͷ஌͕ࣝ͋Δͱ༗རͳ໰୊΍ɺσʔλߏ଄Λ࢖͏໰୊΍ɺͻΒΊ͖ ྗ͕ࢼ͞ΕΔ໰୊ͳͲ͕͋Δɻ ͦ΋ͦ΋ڝϓϩͱ͸ʁ ᶃ໰୊͕༩͑ΒΕΔ ᶄߟ͑Δ ʢϝΠϯʣ ᶅίʔυʹ͢Δ ᶆࣗಈςετ 4
5. ࣮ࡍʹ΍ͬͯΈΑ͏ʢͦͷ̍ʣ Q1. ͋Δ੔਺ N ͕༩͑ΒΕΔͷͰ N ͷ໿਺Λ͢΂ͯग़ྗ͍ͯͩ͘͠͞ɻ 
 ɹɹͨͩ͠ N ͸ 1 Ҏ্ 10^12 ҎԼ ྫʣN = 100 ͷͱ͖ 
 1, 2, 4, 5, 10, 20, 25, 50, 100 5
6. ࣮ࡍʹ΍ͬͯΈΑ͏ʢͦͷ̍ʣ Q1. N ͷ໿਺Λ͢΂ͯग़ྗ͍ͯͩ͘͠͞ɻͨͩ͠ N ͸ 1 Ҏ্ 10^12 ҎԼ ◦ N ͕Ͳͷ਺ͰׂΔ͜ͱ͕Ͱ͖Δ͔ 1 ͔Β N ·Ͱͷ਺Ͱࢼ͢ 6 for i in 1ʙN if ( N % i == 0 ) print( i )ɹ← i ͰׂΓ੾ΕͨΒ i ͸ N ͷ໿਺
7. ࣮ࡍʹ΍ͬͯΈΑ͏ʢͦͷ̍ʣ Q1. N ͷ໿਺Λ͢΂ͯग़ྗ͍ͯͩ͘͠͞ɻͨͩ͠ N ͸ 1 Ҏ্ 10^12 ҎԼ ◦ N ͕Ͳͷ਺ͰׂΔ͜ͱ͕Ͱ͖Δ͔ 1 ͔Β N ·Ͱͷ਺Ͱࢼ͢ ਖ਼͍͠౴͑͸ग़ྗ͞ΕΔ͕ɺ 
 ڝϓϩͰ͸ϓϩάϥϜͷ࣮ߦ࣌ؒʹ੍ݶ͕͋Δʢ2ඵҎ಺ͳͲʣͨΊ͜ΕͰ͸NG • ίϯϐϡʔλ͸ 1 ඵʹ 10^8 ճܭࢉͰ͖Δ • ࠓճͷ໰୊Ͱ͸ N ͕࠷େ 10^12 ͷ৔߹ 10000ඵʢ3࣌ؒऑʣ͔͔ͬͯ͠·͏ • Ͱ͸Ͳ͏͢Δ͔ʁ΋ͬͱޮ཰ྑ͘ܭࢉͰ͖ͳ͍͔ߟ͑ͯΈΔ 7 for i in 1ʙN if ( N % i == 0 ) print( i )ɹ← i ͰׂΓ੾ΕͨΒ i ͸ N ͷ໿਺
8. ࣮ࡍʹ΍ͬͯΈΑ͏ʢͦͷ̍ʣ Q1. N ͷ໿਺Λ͢΂ͯग़ྗ͍ͯͩ͘͠͞ɻͨͩ͠ N ͸ 1 Ҏ্ 10^12 ҎԼ A. N ͕Ͳͷ਺ͰׂΔ͜ͱ͕Ͱ͖Δ͔ 1 ͔Β √N ·Ͱͷ਺Ͱࢼ͢ for i in 1ʙ√Nɹ← N / i ΋Ұॹʹग़ྗ͢Δ͜ͱͰ √N ·ͰͰ͢΂ͯͷ໿਺͕ἧ͏ if ( N % i == 0 ) print( i )ɹ← i ͰׂΓ੾ΕͨΒ i ͸ N ͷ໿਺ if ( N / i != i ) print( N / i )ɹ← i ͰׂΓ੾ΕͨΒ N / i ΋ N ͷ໿਺ • N ͕࠷େ 10^12 ͷ৔߹Ͱ΋ϧʔϓճ਺͸ 10^6 • ίϯϐϡʔλ͕ 1 ඵʹ 10^8 ճܭࢉ͢Δͱͯ͠ 1ඵҎ಺ʹܭࢉ͕ऴΘΔ ྫ͑͹ɺ100ͷ໿਺ΛٻΊΔͱ͖ 100͕5ͰׂΓ੾ΕΔͳΒ100͸20(=100/5)Ͱ΋ׂΓ੾ΕΔ 8
9. ࣮ࡍʹ΍ͬͯΈΑ͏ʢͦͷ̎ʣ Q2. ৽γεςϜʹ N ਓͷϢʔβΛొ࿥͠·͢ɻ 
 ɹɹʢೖྗ͸ N ݸͷ ID ͱر๬Ϣʔβ໊ͷ૊ʣ 
 ಉ͡Ϣʔβ໊͸ొ࿥Ͱ͖ͣ ID ͷখ͍͞Ϣʔβ͕༏ઌ͞Ε·͢ɻ 
 ɹɹر๬ͷϢʔβ໊Ͱొ࿥Ͱ͖ͳ͍Ϣʔβͷ ID Λग़ྗ͍ͯͩ͘͠͞ɻ 
 ɹɹͨͩ͠ N ͸ 1 Ҏ্ 10^6 ҎԼ ྫʣӈਤ ͷͱ͖ 
 ɹɹID ͕ 3, 4, 6 ͷϢʔβ͸ر๬ͷ ID ͕ొ࿥Ͱ͖ͳ͍ 9 ID ر๬Ϣʔβ໊ 1 aaa 2 bbb 3 aaa 4 aaa 5 ccc 6 ccc
10. ࣮ࡍʹ΍ͬͯΈΑ͏ʢͦͷ̎ʣ Q2. ر๬ͷϢʔβ໊Ͱొ࿥Ͱ͖ͳ͍Ϣʔβͷ ID Λग़ྗ͍ͯͩ͘͠͞ɻ 
 N ͸ 1 Ҏ্ 10^6 ҎԼ ◦ ֤Ϣʔβʹ͍ͭͯͦΕΑΓ ID ͕খ͍͞ϢʔβΛ͢΂ͯ֬ೝ for i in 1ʙNɹ← ࠓͷର৅Ϣʔβ for j in 1ʙ(i - 1)ɹ← ର৅ϢʔβΑΓID͕খ͍͞Ϣʔβ if ( username[ i ] == username[ j ] ) flag = 1ɹ← Ϣʔβ໊͕ඃ͍ͬͯͨΒνΣοΫ if (flag == 1) print( i ) 10 ID ر๬Ϣʔβ໊ 1 aaa 2 bbb 3 aaa 4 aaa 5 ccc 6 ccc
11. ࣮ࡍʹ΍ͬͯΈΑ͏ʢͦͷ̎ʣ Q2. ر๬ͷϢʔβ໊Ͱొ࿥Ͱ͖ͳ͍Ϣʔβͷ ID Λग़ྗ͍ͯͩ͘͠͞ɻ 
 N ͸ 1 Ҏ্ 10^6 ҎԼ ◦ ֤Ϣʔβʹ͍ͭͯͦΕΑΓ ID ͕খ͍͞ϢʔβΛ͢΂ͯ֬ೝ for i in 1ʙNɹ← ࠓͷର৅Ϣʔβ for j in 1ʙ(i - 1)ɹ← ର৅ϢʔβΑΓID͕খ͍͞Ϣʔβ if ( username[ i ] == username[ j ] ) flag = 1ɹ← Ϣʔβ໊͕ඃ͍ͬͯͨΒνΣοΫ if (flag == 1) print( i ) 11 ID ر๬Ϣʔβ໊ 1 aaa 2 bbb 3 aaa 4 aaa 5 ccc 6 ccc ͜Ε΋ਖ਼͍͠౴͑͸ग़ྗ͞ΕΔ͕ɾɾɾ • N ͷೋॏϧʔϓ͕͋ΔͨΊ N ͕࠷େ 10^6 ͷ৔߹ɺܭࢉྔ͸ 10^12 • 1 ඵʹ 10^8 ճܭࢉͰ͖Δͱͯ͠ 10000ඵʢ3࣌ؒऑʣ͔͔ͬͯ͠·͏ • ଞʹԿ͔ྑ͍ํ๏͸ͳ͍͔ߟ͑ͯΈΔ
12. ࣮ࡍʹ΍ͬͯΈΑ͏ʢͦͷ̎ʣ Q2. ر๬ͷϢʔβ໊Ͱొ࿥Ͱ͖ͳ͍Ϣʔβͷ ID Λग़ྗ͍ͯͩ͘͠͞ɻ 
 N ͸ 1 Ҏ্ 10^6 ҎԼͷ੔਺ A. ࿈૝഑ྻʢC++ͳΒmap, PythonͳΒdictʣΛ࢖͏ for i in 1ʙNɹ← ࠓͷର৅Ϣʔβ if (used[ username[ i ] ]) print( i )ɹ← ࿈૝഑ྻͷ஋͕ true ͳΒ͢Ͱʹ࢖ΘΕ͍ͯΔϢʔβ໊ used[ username[ i ] ] == trueɹ← ͢Ͱʹ࢖ͬͨϢʔβ໊Λ࿈૝഑ྻʹϢʔβ໊ΛΩʔͱͯ͠ه࿥ 12 ID ر๬Ϣʔβ໊ 1 aaa 2 bbb 3 aaa 4 aaa 5 ccc 6 ccc • ࿈૝഑ྻͷ֤஋ʹΞΫηε͢Δࡍͷܭࢉྔ͸ logN • τʔλϧͷܭࢉྔ͸ NlogNʹͳΓɺ࠷େ 10^6 ͷ৔߹ɺܭࢉྔ͸໿ 10^7 • ίϯϐϡʔλ͕ 1 ඵʹ 10^8 ճܭࢉ͢Δͱͯ͠ 1ඵҎ಺ʹܭࢉ͕ऴΘΔ
13. Q3. ௕͞ L cmͷ๮ͷ্Λ N ඖͷΞϦ͕ 1cm/ඵͰา͍͍ͯΔɻ 
 ΞϦ͸ޓ͍ʹͿ͔ͭΔͱ޲͖Λม͑ͯ൓ରํ޲ʹา͖ͩ͠ɺ 
 ๮ͷ୺ʹ౸ୡ͢Δͱ๮͔ΒམͪΔ 
 ࠷ޙͷΞϦ͕๮͔ΒམͪΔ·Ͱʹ͔͔Δ࣌ؒ͸Կඵ͔ʁ 13 p1 p2 p3 p4 0 L ࣮ࡍʹ΍ͬͯΈΑ͏ʢͦͷ̏ʣ
14. ࣮ࡍʹ΍ͬͯΈΑ͏ʢͦͷ̏ʣ Q3. ࠷ޙͷΞϦ͕๮͔ΒམͪΔ·Ͱʹ͔͔Δ࣌ؒ͸Կඵ͔ʁ ◦ ੺͸੨ͱҐஔ X1 ͰͿ͔ͭͬͯ୺·ͰߦͬͯམͪΔ 
 ੨͸ԫͱҐஔ X2 ͰͿ͔ͭͬͯ੺ͱҐஔ X1 ͰͿ͔ͭͬͯɾɾ 
 ྘ʹҐஔ X3 ͰͿ͔ͭͬͯ໭͖ͬͯͨԫͱҐஔ X4 ͰͿ͔ͭͬͯɾɾɾ 
 ԫ͸੨ͱҐஔ X2 ͰͿ͔ͭͬͯ྘ͱҐஔ X3 ͰͿ͔ͭͬͯɾɾ 
 ੺ʹҐஔ X1 ͰͿ͔ͭͬͯ໭͖ͬͯͨ੨ͱҐஔ X4 ͰͿ͔ͭͬͯɾɾɾ 14
15. ࣮ࡍʹ΍ͬͯΈΑ͏ʢͦͷ̏ʣ Q3. ࠷ޙͷΞϦ͕๮͔ΒམͪΔ·Ͱʹ͔͔Δ࣌ؒ͸Կඵ͔ʁ ◦ ੺͸੨ͱҐஔ X1 ͰͿ͔ͭͬͯ୺·ͰߦͬͯམͪΔ 
 ੨͸ԫͱҐஔ X2 ͰͿ͔ͭͬͯ੺ͱҐஔ X1 ͰͿ͔ͭͬͯɾɾ 
 ྘ʹҐஔ X3 ͰͿ͔ͭͬͯ໭͖ͬͯͨԫͱҐஔ X4 ͰͿ͔ͭͬͯɾɾɾ 
 ԫ͸੨ͱҐஔ X2 ͰͿ͔ͭͬͯ྘ͱҐஔ X3 ͰͿ͔ͭͬͯɾɾ 
 ੺ʹҐஔ X1 ͰͿ͔ͭͬͯ໭͖ͬͯͨ੨ͱҐஔ X4 ͰͿ͔ͭͬͯɾɾɾ • ΞϦͷಈ͖Λͦͷ··γϛϡϨʔτ͍ͯ͘͠ͱେมɾɾɾ • ΋ͬͱγϯϓϧʹͰ͖ͳ͍͔ߟ͑ͯΈΔ 15
16. ࣮ࡍʹ΍ͬͯΈΑ͏ʢͦͷ̏ʣ Q3. ࠷ޙͷΞϦ͕๮͔ΒམͪΔ·Ͱʹ͔͔Δ࣌ؒ͸Կඵ͔ʁ A. Ϳ͔ͭͬͯ޲͖Λม͑Δͷͱ͢Εҧ͏ͷ͸݁Ռͱͯ͠ಉ͡ Ϳ͔ͭΔ৔߹ ͢Εҧ͏৔߹ 16 ΞϦΛ۠ผ͢Δ 
 ඞཁ͕ͳ͍ ΞϦͷ৭Λແࢹ͢ΔͱԼͷ2ͭ͸ಉ͡
17. ࣮ࡍʹ΍ͬͯΈΑ͏ʢͦͷ̏ʣ Q3. ࠷ޙͷΞϦ͕๮͔ΒམͪΔ·Ͱʹ͔͔Δ࣌ؒ͸Կඵ͔ʁ A. Ϳ͔ͭͬͯ޲͖Λม͑Δͷͱ͢Εҧ͏ͷ͸݁Ռͱͯ͠ಉ͡ 17 ans = 0 for i in 1ʙNɹ← ֤ΞϦ if (ӈ޲͖) t = L - p[i]ɹ if (ࠨ޲͖) t = p[i] ans = max(ans, t)ɹ← ࠷େΛߋ৽ print(ans) 0 p1 p2 p3 p4 L ֤ΞϦΛಠཱͯ͠ߟ͑Ε͹Α͍
18. 1. ܾ·ͬͨ࣌ؒʹίϯςετελʔτ 
 ੈքதͷϢʔβʹಉ࣌ʹ໰୊͕ެ։͞ΕΔɻͲͷ໰୊͔Βղ͍ͯ΋OK 18 ڝϓϩͷྲྀΕ
19. 2. Ͳ͏΍ͬͨΒͰ͖Δ͔ߟ͑Δ 19 ࢲ͸͍ͭ΋͜Μͳײ͡ͰࢴͱϖϯΛ༻ҙͯ͠ߟ͑ͯ·͢ɻ 
 ͦͷ··ղ͚ͣʹίϯςετऴྃ࣌ؒʹͳΔ͜ͱ΋ɾɾɾ ڝϓϩͷྲྀΕ
20. 3. ΍Γํ͕ࢥ͍͍ͭͨΒίʔυԽͯ͠ఏग़͢Δ 
 ϓϩάϥϛϯάݴޠ͸ࣗ෼ͷ޷͖ͳ΋ͷͰྑ͍ʢC++, Python, Ruby, Rust, Go, … ΄΅ͳΜͰ΋࢖͑Δʣ 20 ίʔσΟϯά؀ڥ͸ίϯςεταΠτ্ͷΤσΟλͰ΋ࣗ෼ͷPC্ͷΤσΟλͰ΋OK ڝϓϩͷྲྀΕ
21. 4. ίʔυΛఏग़͢Δͱࣗಈςετ͕࢝·Δɻ 
 ͢΂ͯͷςετέʔεʹਖ਼ղ͢Δͱ໰୊ʹԠͨ͡ಘ఺͕Ճࢉ͞ΕΔ 
 1ͭͷέʔεͰ΋౴͕͑ؒҧ͍ͬͯͨΓ੍ݶ࣮ߦ࣌ؒΛΦʔόʔ͢Δͱ0఺ 
 ͨͩ͠Կ౓Ͱ΋ίʔυͷ࠶ఏग़͕ՄೳʢϖφϧςΟ͋Γʣ 
 ςετ1 N = 1 ςετ2 N = 98 ςετ3 N = 10^9 ςετ4 N = 10^6 ộ ộ NGͳྫ OKͳྫ ໿਺ྻڍͷςετέʔεྫ 21 ڝϓϩͷྲྀΕ
22. 5. ίϯςετ੍ݶ͕࣌ؒདྷͨΒऴྃɻ࠷ऴతͳ߹ܭಘ఺͕ߴ͍Ϣʔβ͕উརɻ 
 ߹ܭಘ఺͕ಉ͡৔߹͸ͦͷಘ఺ʹૣ͍࣌ؒͰ౸ୡͨ͠Ϣʔβͷউͪ 
 ݁ՌʹΑͬͯϨʔτ͕มಈ͢Δ 22 ڝϓϩͷྲྀΕ
23. ڝϓϩͷ͸͡Ί͔ͨ ·ͣ͸AtCoder͕͓͢͢Ί 23 “AtCoder͸ɺੈք࠷ߴๆͷϓϩάϥϛϯάαΠτͰ͢ɻ 
 ϦΞϧλΠϜͷΦϯϥΠϯίϯςετͰڝ͍߹͏͜ͱ΍ɺ 
 3,000Ҏ্ͷաڈ໰ʹ͍ͭͰ΋νϟϨϯδ͢Δ͜ͱ͕Ͱ͖·͢ɻ”
24. 1. ·ͣ͸աڈ໰ΛԿ໰͔΍ͬͯΈΔ ◦ AtCoder ʹొ࿥ͨ͠Β࣍ʹ΍Δ͜ͱ ʙ ͜Ε͚ͩղ͚͹े෼ಆ͑Δʂաڈ໰ਫ਼બ 10 ໰ ʙ https://qiita.com/drken/items/fd4e5e3630d0f5859067#%E7%AC%AC-6-%E5%95%8F--abc- 088-b---card-game-for-two-200-%E7%82%B9 ◦ AtCoder ProblemsʢAtCoderͷΞΧ΢ϯτͱ࿈ܞͯ͠ղ͍ͨ໰୊Λ؅ཧͰ͖Δʣ https://kenkoooo.com/atcoder/#/table/ 2. ׳Ε͖ͯͨΒϦΞϧλΠϜͰίϯςετʹग़ͯΈΑ͏ 3. ࠷ۙ͸ڝϓϩʹؔ࿈ͨ͠ຊ΋ͨ͘͞Μग़͍ͯΔͷͰಡΜͰΈΔͷ΋͓͢͢Ί ڝϓϩΛ͸͡ΊͨΒ 24
25. ڝϓϩ͸ָ͍͠ʂ ଞʹ΋΍Δཧ༝͕ͨ͘͞Μ • ܭࢉྔͷײ͕֮਎ʹͭ͘ • ࿦ཧతࢥߟྗ͕஁͑ΒΕΔ • GAFA΍࠷ۙ͸೔ຊاۀͰ΋࠾༻ࢼݧʹಋೖ͞Ε͍ͯΔͨΊ༗རʹͳΔ • ίϯςετʹΑͬͯ͸৆͕ۚग़Δ • ͨ͘͞Μͷఱ࠽ͱઓ͑Δ Ҏ্ɺରઓΑΖ͓͘͠Ͷ͕͍͠·͢ʂ ࠷ޙʹ 25