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
730
Competitive Programming in Ruby (101)
yhara
September 10, 2016
Tweet
Share
More Decks by yhara
See All by yhara
静的型付けプログラミング言語Shiika
yhara
0
19k
それは残像だ
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
630
Other Decks in Programming
See All in Programming
RubyKaigiで得られる10の価値 〜Ruby話を聞くことだけが RubyKaigiじゃない〜
tomohiko9090
0
100
抽象データ型について学んだ
ryounasso
0
210
TypeScript を活かしてデザインシステム MCP を作る / #tskaigi_after_night
izumin5210
4
480
人には人それぞれのサービス層がある
shimabox
3
470
TVer iOSチームの共通認識の作り方 - Findy Job LT iOSアプリ開発の裏側 開発組織が向き合う課題とこれから
techtver
PRO
0
710
FastMCPでMCPサーバー/クライアントを構築してみる
ttnyt8701
2
100
CQRS/ESのクラスとシステムフロー ~ RailsでフルスクラッチでCQRSESを組んで みたことから得た学び~
suzukimar
0
190
〜可視化からアクセス制御まで〜 BigQuery×Looker Studioで コスト管理とデータソース認証制御する方法
cuebic9bic
2
270
Use Perl as Better Shell Script
karupanerura
0
660
OpenNext + Hono on Cloudflare でイマドキWeb開発スタックを実現する
rokuosan
0
110
TypeScript LSP の今までとこれから
quramy
0
110
CRUD から CQRS へ ~ 分離が可能にする柔軟性
tkawae
0
230
Featured
See All Featured
What's in a price? How to price your products and services
michaelherold
245
12k
Building Better People: How to give real-time feedback that sticks.
wjessup
368
19k
Bootstrapping a Software Product
garrettdimon
PRO
307
110k
The Illustrated Children's Guide to Kubernetes
chrisshort
48
50k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
34
2.3k
Product Roadmaps are Hard
iamctodd
PRO
53
11k
Build your cross-platform service in a week with App Engine
jlugia
231
18k
Helping Users Find Their Own Way: Creating Modern Search Experiences
danielanewman
29
2.6k
Navigating Team Friction
lara
186
15k
Docker and Python
trallard
44
3.4k
VelocityConf: Rendering Performance Case Studies
addyosmani
329
24k
Raft: Consensus for Rubyists
vanstee
137
7k
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