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
750
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.4k
スモートーク
yhara
0
2.9k
Ovto: Frontend web framework for Rubyists
yhara
0
7.5k
Ruby, Opal and WebAssembly
yhara
2
2.6k
Rubyで競技プログラミング(入門編)
yhara
0
1.9k
良いデバッグログはプロジェクトの資産である
yhara
54
18k
Let's make a functional language!
yhara
0
6.4k
Recent Updates (近況報告)
yhara
0
640
Other Decks in Programming
See All in Programming
アセットのコンパイルについて
ojun9
0
130
CJK and Unicode From a PHP Committer
youkidearitai
PRO
0
110
はじめてのMaterial3 Expressive
ym223
2
900
Navigating Dependency Injection with Metro
zacsweers
3
3.5k
楽して成果を出すためのセルフリソース管理
clipnote
0
190
プロパティベーステストによるUIテスト: LLMによるプロパティ定義生成でエッジケースを捉える
tetta_pdnt
0
4.3k
Putting The Genie in the Bottle - A Crash Course on running LLMs on Android
iurysza
0
140
チームのテスト力を鍛える
goyoki
3
930
RDoc meets YARD
okuramasafumi
4
170
2025 年のコーディングエージェントの現在地とエンジニアの仕事の変化について
azukiazusa1
24
12k
ユーザーも開発者も悩ませない TV アプリ開発 ~Compose の内部実装から学ぶフォーカス制御~
taked137
0
190
Ruby×iOSアプリ開発 ~共に歩んだエコシステムの物語~
temoki
0
350
Featured
See All Featured
Producing Creativity
orderedlist
PRO
347
40k
Side Projects
sachag
455
43k
The Success of Rails: Ensuring Growth for the Next 100 Years
eileencodes
46
7.6k
Speed Design
sergeychernyshev
32
1.1k
A Tale of Four Properties
chriscoyier
160
23k
Documentation Writing (for coders)
carmenintech
74
5k
Creating an realtime collaboration tool: Agile Flush - .NET Oxford
marcduiker
31
2.2k
How To Stay Up To Date on Web Technology
chriscoyier
790
250k
The Psychology of Web Performance [Beyond Tellerrand 2023]
tammyeverts
49
3k
Designing Experiences People Love
moore
142
24k
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
656
61k
Embracing the Ebb and Flow
colly
87
4.8k
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