Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
おしゃれなアルゴリズム
Search
eTakazawa
February 22, 2020
Programming
7
4.8k
おしゃれなアルゴリズム
本スライドは某LT用に作成しました.厳密性より,非競プロerに向けて面白さを重視しています.
過去問題の解説です.
eTakazawa
February 22, 2020
Tweet
Share
More Decks by eTakazawa
See All by eTakazawa
感動するアルゴリズム
etakazawa
0
160
Other Decks in Programming
See All in Programming
私のEbitengineの第一歩
qt_luigi
0
450
Kotlin 2.0 and Beyond
antonarhipov
2
150
Regular Expressions, REXML, Automata Learning
makenowjust
0
220
Rubyとクリエイティブコーディングの輪の広がり / The Growing Circle of Ruby and Creative Coding
chobishiba
1
270
Android開発以外のAndroid開発経験の活かしどころ
konifar
2
1k
開発を加速する共有Swift Package実践
elmetal
PRO
0
420
【TID2024】模擬講義:プログラマと一緒にゲームをデザインしてみよう!
akatsukigames_tech
0
660
KSPの導入・移行を前向きに検討しよう!
shxun6934
PRO
0
280
API Platform for Laravel
dunglas
0
320
LangChainでWebサイトの内容取得やGitHubソースコード取得
shukob
0
160
状態管理ライブラリZustandの導入から運用まで
k1tikurisu
3
470
エンジニア1年目で複雑なコードの改善に取り組んだ話
mtnmr
3
2k
Featured
See All Featured
How to Think Like a Performance Engineer
csswizardry
16
960
Agile that works and the tools we love
rasmusluckow
327
20k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
26
2k
Pencils Down: Stop Designing & Start Developing
hursman
119
11k
Designing Dashboards & Data Visualisations in Web Apps
destraynor
227
52k
The Cult of Friendly URLs
andyhume
76
6k
Designing with Data
zakiwarfel
98
5k
Large-scale JavaScript Application Architecture
addyosmani
508
110k
Creatively Recalculating Your Daily Design Routine
revolveconf
215
12k
Web development in the modern age
philhawksworth
205
10k
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
89
16k
Testing 201, or: Great Expectations
jmmastey
36
7k
Transcript
͓͠ΌΕͳΞϧΰϦζϜ @utsubo_21 ※ ຊεϥΠυLT༻ʹ࡞͠·ͨ͠ ɹݫີੑΑΓɼඇڝϓϩerʹ͚ͯ໘ന͞Λॏࢹ͍ͯ͠·͢
ࠓ·Ͱղ͍ͨ ΞϧΰϦζϜͷͷத͔Β
ಛʹ͓͠Ζ͔ͬͨΛ pickup
• মΛ͍ͯ͠·͢ • ॏͳ͍ͬͯΔ෦͕ੜম͚ʹ • ͍͔ͭ͘ΛऔΓআ͘͜ͱͰ Ͱ͖Δ͚ͩ৯ΒΕΔ෦Λ͍ͨ͘͠ Question
* CODE FESTIVAL 2015 ຊઓ মͷୡਓ
• মΛ͍ͯ͠·͢ • ॏͳ͍ͬͯΔ෦͕ੜম͚ʹ • ͍͔ͭ͘ΛऔΓআ͘͜ͱͰ Ͱ͖Δ͚ͩ৯ΒΕΔ෦Λ͍ͨ͘͠ Question
* CODE FESTIVAL 2015 ຊઓ মͷୡਓ
• মΛ͍ͯ͠·͢ • ॏͳ͍ͬͯΔ෦͕ੜম͚ʹ • ͍͔ͭ͘ΛऔΓআ͘͜ͱͰ Ͱ͖Δ͚ͩ৯ΒΕΔ෦Λ͍ͨ͘͠ Question
* CODE FESTIVAL 2015 ຊઓ মͷୡਓ
• মΛ͍ͯ͠·͢ • ॏͳ͍ͬͯΔ෦͕ੜম͚ʹ • ͍͔ͭ͘ΛऔΓআ͘͜ͱͰ Ͱ͖Δ͚ͩ৯ΒΕΔ෦Λ͍ͨ͘͠ Question
* CODE FESTIVAL 2015 ຊઓ মͷୡਓ
Question • ೖྗ - (Ґஔɼ͞) × Nݸ ( N
≦ 10^5 ) - ͷ͞ M ( M ≦ 10^5 ) • త - ֤ʹ͍ͭͯম͔͘ম͔ͳ͍͔બͼɼ ͕ॏͳΒͣম͚Δ͞ͷ૯Λ࠷େԽ͠ग़ྗ 1 2 3
Question • ೖྗ - (Ґஔɼ͞) × Nݸ ( N
≦ 10^5 ) - ͷ͞ M ( M ≦ 10^5 ) • త - ֤ʹ͍ͭͯম͔͘ম͔ͳ͍͔બͼɼ ͕ॏͳΒͣম͚Δ͞ͷ૯Λ࠷େԽ͠ग़ྗ 1 2 3
Question • ೖྗ - (Ґஔɼ͞) × Nݸ ( N
≦ 10^5 ) - ͷ͞ M ( M ≦ 10^5 ) • త - ֤ʹ͍ͭͯম͔͘ম͔ͳ͍͔બͼɼ ͕ॏͳΒͣম͚Δ͞ͷ૯Λ࠷େԽ͠ग़ྗ 1 2 3
͏গ͠ෳࡶͳྫ ྫɽ
͏গ͠ෳࡶͳྫ ؒͷґଘ͕૿͑ɼ͍͠… ྫɽ
• ”͕ॏͳ͍ͬͯΔ” or ”Կͳ͍” ۠ؒ ͕͞Ք͛ͳ͍ • ”શମͷ͞M
ʔ ম͚ͳ͍۠ؒͷ͞” Ͱ͕͑ग़Δ ղ๏Λࢧ͑Δߟ͑ํ ম͚Δ෦Λ͘ → ম͚ͳ͍෦Λ͘
ղ๏ ͋ΔͷબͼํΛͨ࣌͠ͷ ম͚ͳ͍෦ͷ͞ΛΓ͍ͨ 1 2 3
ղ๏ ఱ࠽తͳͻΒΊ͖Ͱ ͷ͞ʹ߹ΘͤͯҹΛॻ͍ͯΈΔ
ղ๏ 1 2 3 ఱ࠽తͳͻΒΊ͖Ͱ ͷ͞ʹ߹ΘͤͯҹΛॻ͍ͯΈΔ
ղ๏ ͞Βʹఱ࠽తͳͻΒΊ͖Ͱ ”Կͳ͍” ෦Λද͢ҹΛՃ
ղ๏ ࠨ͔ΒӈҹΛḷͬͯΈΔ
ղ๏ ྫ͑ɼͷܦ࿏
ղ๏ ɹɹͷΈΛম͘߹Λදݱ ʢͱ”Կͳ͍”۠ؒ 4ͭʣ 1 1 ”Կͳ͍”۠ؒ
ղ๏ “Կͳ͍”۠ؒͷ͞ΛΓ͍ͨ ʢ㲎 શମͷ͞ʔম͚ͳ͍෦ͷ͞ʹম͚Δ͞ʣ
ղ๏ ҹʹίετΛ༩ 1 1 1 1 1 1
1 1 0 0 0
ղ๏ ܦ࿏্ͷҹͷίετͷ૯ ʹ ম͚ͳ͍෦(Կͳ͍෦)ͷ͞ ʹͳ͍ͬͯΔ 1 1 1
1 1 1 1 1 0 0 0
ղ๏ ”ॏͳ͍ͬͯΔ” ෦Ͳ͏දݱ͢Δ͔
ղ๏ ”ॏͳ͍ͬͯΔ” ෦Ͳ͏දݱ͢Δ͔ → ٯ͖ͷҹΛுΓ·͢ʢίετ1ʣ 1 1 1
ղ๏ ઌͱಉ༷ʹࠨ͔ΒӈҹΛḷΔ
ղ๏ ྫ͑ɼͷܦ࿏
ղ๏ 1 1 1 1 1 2 ɹɹͱɹɹΛম͘߹Λදݱ
1 2 ”Կͳ͍”۠ؒ ”ॏͳ͍ͬͯΔ”۠ؒ
ղ๏ 1 1 1 1 ম͚ͳ͍۠ؒͷ͞ 4 ”Կͳ͍”۠ؒ
”ॏͳ͍ͬͯΔ”۠ؒ
ղ๏ ·ͱΊ 1 1 1 1 1 1
1 1 1 1 1 ࠨ͔Βӈͷܦ࿏্ͷίετͷ૯ ʹ ম͚ͳ͍෦ͷ͞
ղ๏ ·ͱΊ 1 1 1 1 1 1
1 1 1 1 1 ͭ·Γɼࠨ͔Βӈͷ࠷ܦ࿏ ʹ ম͚ͳ͍෦ͷ͕͞࠷খͷͷબͼํ
ղ๏ ·ͱΊ 1 1 1 1 1 1
1 1 1 1 1 ͭ·Γɼ࠷ܦ࿏͕͔Εྑ͍ → ؆୯ʂ
ղ๏ ·ͱΊ 1 1 1 1 1 1
1 1 1 1 1 ͭ·Γɼ࠷ܦ࿏͕͔Εྑ͍ → ؆୯ʂ ܭࢉྔతʹɿ શ୳ࡧ O(2^N) → ຊख๏ O((M+N)logM)
͋ͱ͕͖ • ࠷ܦ࿏ʹؼணͰ͖ͯ࠷ߴʹ͓͠ΌΕ - মʹߦ͘ͱ͖ࢥ͍ग़ͯ͠Ͷ • ໘നΈΛײͨ͡ํڝϓϩ͍ͬͯͩ͘͞ • ࠷େԽΛ͢Δ࣌Կ͔ͷ࠷খԽʹ ஔ͖͑ΒΕͳ͍͔ߟ͑Δ
- “࠷େԽΛ࠷খԽʹมܗͯ͠ɼ࠷খΧοτʹؼண” ׂͱయܕΒ͍͠ʢࢀߟɿ೩͢ຒΊΔʣ https://www.slideshare.net/shindannin/project-selection-problem
͓·͚ • ൈ͚͍ͯΔେࣄͳߟ - ઌͷܦ࿏Ͱɼ3ຕҎ্͕ॏͳΔબͼํΛ දݱͰ͖ͳ͍ - ॏͳͬͨ෦Λ༨ܭʹίετͱͯ͠Χϯτͯ͠ ͠·͏ɽ͕ɼͦͦ3ຕҎ্ॏͳΔͷબͼํ ɼ࠷దղʹͳΓಘͳ͍
• ެࣜϖʔδͷղઆΛಡΜͰ͍ͩ͘͞ • ࢲ͕ॻ͍ͨίʔυͪ͜Β https://www.slideshare.net/chokudai/code-festival-2015-final https://code-festival-2015-final-open.contest.atcoder.jp/submissions/10197952