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
760
Competitive Programming in Ruby (101)
yhara
September 10, 2016
Tweet
Share
More Decks by yhara
See All by yhara
静的型付けプログラミング言語Shiika
yhara
0
20k
それは残像だ
yhara
4
4.5k
スモートーク
yhara
0
3k
Ovto: Frontend web framework for Rubyists
yhara
0
7.6k
Ruby, Opal and WebAssembly
yhara
2
2.7k
Rubyで競技プログラミング(入門編)
yhara
0
1.9k
良いデバッグログはプロジェクトの資産である
yhara
54
18k
Let's make a functional language!
yhara
0
6.4k
Recent Updates (近況報告)
yhara
0
650
Other Decks in Programming
See All in Programming
One Enishi After Another
snoozer05
PRO
0
150
When Dependencies Fail: Building Antifragile Applications in a Fragile World
selcukusta
0
110
CSC305 Lecture 08
javiergs
PRO
0
270
コード生成なしでモック処理を実現!ovechkin-dm/mockioで学ぶメタプログラミング
qualiarts
0
250
kiroとCodexで最高のSpec駆動開発を!!数時間で web3ネイティブなミニゲームを作ってみたよ!
mashharuki
0
860
Leading Effective Engineering Teams in the AI Era
addyosmani
7
570
開発組織の戦略的な役割と 設計スキル向上の効果
masuda220
PRO
6
1.1k
Software Architecture
hschwentner
6
2.3k
The Past, Present, and Future of Enterprise Java
ivargrimstad
0
410
AI Coding Meetup #3 - 導入セッション / ai-coding-meetup-3
izumin5210
0
3.4k
Reactive Thinking with Signals and the Resource API
manfredsteyer
PRO
0
100
Writing Better Go: Lessons from 10 Code Reviews
konradreiche
3
5.8k
Featured
See All Featured
Imperfection Machines: The Place of Print at Facebook
scottboms
269
13k
KATA
mclloyd
PRO
32
15k
Agile that works and the tools we love
rasmusluckow
331
21k
Building Flexible Design Systems
yeseniaperezcruz
329
39k
The Illustrated Children's Guide to Kubernetes
chrisshort
49
51k
Principles of Awesome APIs and How to Build Them.
keavy
127
17k
Performance Is Good for Brains [We Love Speed 2024]
tammyeverts
12
1.2k
ピンチをチャンスに:未来をつくるプロダクトロードマップ #pmconf2020
aki_iinuma
127
54k
Visualizing Your Data: Incorporating Mongo into Loggly Infrastructure
mongodb
48
9.7k
Balancing Empowerment & Direction
lara
5
700
How GitHub (no longer) Works
holman
315
140k
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
9
990
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