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
Competitive Programming in Ruby (101)
Search
yhara
September 10, 2016
Programming
0
680
Competitive Programming in Ruby (101)
yhara
September 10, 2016
Tweet
Share
More Decks by yhara
See All by yhara
静的型付けプログラミング言語Shiika
yhara
0
18k
それは残像だ
yhara
4
4.2k
スモートーク
yhara
0
2.8k
Ovto: Frontend web framework for Rubyists
yhara
0
7.1k
Ruby, Opal and WebAssembly
yhara
2
2.4k
Rubyで競技プログラミング(入門編)
yhara
0
1.8k
良いデバッグログはプロジェクトの資産である
yhara
54
18k
Let's make a functional language!
yhara
0
6.3k
Recent Updates (近況報告)
yhara
0
590
Other Decks in Programming
See All in Programming
ペアーズにおけるAmazon Bedrockを⽤いた障害対応⽀援 ⽣成AIツールの導⼊事例 @ 20241115配信AWSウェビナー登壇
fukubaka0825
6
2.1k
初めてDefinitelyTypedにPRを出した話
syumai
0
430
[Do iOS '24] Ship your app on a Friday...and enjoy your weekend!
polpielladev
0
120
광고 소재 심사 과정에 AI를 도입하여 광고 서비스 생산성 향상시키기
kakao
PRO
0
180
Micro Frontends Unmasked Opportunities, Challenges, Alternatives
manfredsteyer
PRO
0
120
Amazon Qを使ってIaCを触ろう!
maruto
0
420
OSSで起業してもうすぐ10年 / Open Source Conference 2024 Shimane
furukawayasuto
0
110
EMになってからチームの成果を最大化するために取り組んだこと/ Maximize team performance as EM
nashiusagi
0
100
我々のデザインシステムは Chakra v3 にアップデートします
shunya078
2
150
Figma Dev Modeで変わる!Flutterの開発体験
watanave
0
160
Kaigi on Rails 2024 〜運営の裏側〜
krpk1900
1
270
どうして僕の作ったクラスが手続き型と言われなきゃいけないんですか
akikogoto
1
130
Featured
See All Featured
The Art of Programming - Codeland 2020
erikaheidi
52
13k
The Straight Up "How To Draw Better" Workshop
denniskardys
232
140k
Building a Modern Day E-commerce SEO Strategy
aleyda
38
6.9k
"I'm Feeling Lucky" - Building Great Search Experiences for Today's Users (#IAC19)
danielanewman
226
22k
Fantastic passwords and where to find them - at NoRuKo
philnash
50
2.9k
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
10
720
The World Runs on Bad Software
bkeepers
PRO
65
11k
Why Our Code Smells
bkeepers
PRO
334
57k
Git: the NoSQL Database
bkeepers
PRO
427
64k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
356
29k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
665
120k
Making the Leap to Tech Lead
cromwellryan
133
8.9k
Transcript
Compe&&ve Programming in Ruby (101) RubyKaigi 2016 Kyoto A1er Party
LT (2016-09-10) @yhara (Yutaka Hara) RubyKaigi 2016 Kyoto LT (2016-09-10) 1
RubyKaigi 2016 Kyoto LT (2016-09-10) 2
Recently I'm trying Compe22ve Programming with my colleagues RubyKaigi 2016
Kyoto LT (2016-09-10) 3
Compe&&ve Programming RubyKaigi 2016 Kyoto LT (2016-09-10) 4
Programming contest RubyKaigi 2016 Kyoto LT (2016-09-10) 5
Write a program fast and correctly RubyKaigi 2016 Kyoto LT
(2016-09-10) 6
Need C(++, #) or Java? RubyKaigi 2016 Kyoto LT (2016-09-10)
7
You can use Ruby too! RubyKaigi 2016 Kyoto LT (2016-09-10)
8
Sites which supports Ruby • Sphere Online Judge • Aizu
Online Judge • yukicoder • AtCoder ←Today's topic RubyKaigi 2016 Kyoto LT (2016-09-10) 9
atcoder.jp • AtCoder Grand Contest • AtCoder Regular Contest •
AtCoder Beginner Contest • AtCoder Typical Contest RubyKaigi 2016 Kyoto LT (2016-09-10) 10
Don't join the contest RubyKaigi 2016 Kyoto LT (2016-09-10) 11
Try previous contests first ! RubyKaigi 2016 Kyoto LT (2016-09-10)
12
! • Any%me • No %me limit RubyKaigi 2016 Kyoto
LT (2016-09-10) 13
• AtCoder Grand Contest • AtCoder Regular Contest • AtCoder
Beginner Contest • AtCoder Typical Contest RubyKaigi 2016 Kyoto LT (2016-09-10) 14
AtCoder Beginner Contest • A: Very easy • B: Easy
• C: Easy? • D: Not really easy RubyKaigi 2016 Kyoto LT (2016-09-10) 15
But Ruby is slow...? ! RubyKaigi 2016 Kyoto LT (2016-09-10)
16
No problem! RubyKaigi 2016 Kyoto LT (2016-09-10) 17
Algorithm Ma-ers ! RubyKaigi 2016 Kyoto LT (2016-09-10) 18
Example: one-line Reversi RubyKaigi 2016 Kyoto LT (2016-09-10) 19
one-line Reversi • Given N pieces, flip Q ranges •
Calculate the final state ••••••••• 1..4 2..6 8..9 ɹɹ↓ ◦•••◦◦•◦◦ RubyKaigi 2016 Kyoto LT (2016-09-10) 20
Just flipping each pieces? ranges.each do |r| r.each do |i|
line[i] = !line[i] end end RubyKaigi 2016 Kyoto LT (2016-09-10) 21
RubyKaigi 2016 Kyoto LT (2016-09-10) 22
200,000 pieces ! 200,000 ranges ! RubyKaigi 2016 Kyoto LT
(2016-09-10) 23
Billions of flips ! ranges.each do |r| # <- 200,000
times r.each do |i| # <- 50,000 times or so line[i] = !line[i] end end RubyKaigi 2016 Kyoto LT (2016-09-10) 24
⏰ Time Limit = 2 sec. RubyKaigi 2016 Kyoto LT
(2016-09-10) 25
Be#er algorithm Memorize where color changes 10001 23005 ɹɹɹɹ↓ɹɹ↓ •••...•◦...◦•••
RubyKaigi 2016 Kyoto LT (2016-09-10) 26
Passed! ! RubyKaigi 2016 Kyoto LT (2016-09-10) 27
You can try Compe//ve Prograaming in Ruby ! (at least
for beginner contest) RubyKaigi 2016 Kyoto LT (2016-09-10) 28
! BTW ! RubyKaigi 2016 Kyoto LT (2016-09-10) 29
RubyKaigi 2016 Kyoto LT (2016-09-10) 30
ABC037-D • I couldn't pass with Ruby ! • Traversing
1000x1000 maze • Maybe with Ruby3...? RubyKaigi 2016 Kyoto LT (2016-09-10) 31
Crystal passes ※CrystalɿRuby-like sta0cally typed language RubyKaigi 2016 Kyoto LT
(2016-09-10) 32
Pypy2 passes ※Pypy2ɿFaster Python implemanta2on RubyKaigi 2016 Kyoto LT (2016-09-10)
33
Python3 passes!? ! RubyKaigi 2016 Kyoto LT (2016-09-10) 34
RubyKaigi 2016 Kyoto LT (2016-09-10) 35
RubyKaigi 2016 Kyoto LT (2016-09-10) 36
RubyKaigi 2016 Kyoto LT (2016-09-10) 37
(DON'T TRY THIS AT HOME !) RubyKaigi 2016 Kyoto LT
(2016-09-10) 38