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.9k
おしゃれなアルゴリズム
本スライドは某LT用に作成しました.厳密性より,非競プロerに向けて面白さを重視しています.
過去問題の解説です.
eTakazawa
February 22, 2020
Tweet
Share
More Decks by eTakazawa
See All by eTakazawa
感動するアルゴリズム
etakazawa
0
190
Other Decks in Programming
See All in Programming
あのころの iPod を どうにか再生させたい
orumin
2
2.5k
CSC305 Summer Lecture 12
javiergs
PRO
0
120
ソフトウェアテスト徹底指南書の紹介
goyoki
1
110
WebAssemblyインタプリタを書く ~Component Modelを添えて~
ruccho
1
910
Flutterと Vibe Coding で個人開発!
hyshu
1
270
🔨 小さなビルドシステムを作る
momeemt
1
510
MCPで実現するAIエージェント駆動のNext.jsアプリデバッグ手法
nyatinte
6
870
Jakarta EE Core Profile and Helidon - Speed, Simplicity, and AI Integration
ivargrimstad
0
200
kiroでゲームを作ってみた
iriikeita
0
180
A Gopher's Guide to Vibe Coding
danicat
0
170
ワープロって実は計算機で
pepepper
2
1.4k
KessokuでDIでもgoroutineを活用する / Go Connect #6
mazrean
0
110
Featured
See All Featured
What’s in a name? Adding method to the madness
productmarketing
PRO
23
3.6k
Connecting the Dots Between Site Speed, User Experience & Your Business [WebExpo 2025]
tammyeverts
8
480
A Modern Web Designer's Workflow
chriscoyier
695
190k
Chrome DevTools: State of the Union 2024 - Debugging React & Beyond
addyosmani
7
820
How to Ace a Technical Interview
jacobian
279
23k
Code Reviewing Like a Champion
maltzj
525
40k
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
656
61k
Balancing Empowerment & Direction
lara
2
590
Visualization
eitanlees
147
16k
Documentation Writing (for coders)
carmenintech
73
5k
Fantastic passwords and where to find them - at NoRuKo
philnash
51
3.4k
Making the Leap to Tech Lead
cromwellryan
134
9.5k
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