Competitive Programming in Ruby (101)

Transcript

1. 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

2. RubyKaigi 2016 Kyoto LT (2016-09-10) 2

3. Recently I'm trying Compe22ve Programming with my colleagues RubyKaigi 2016

   Kyoto LT (2016-09-10) 3

4. Compe&&ve Programming RubyKaigi 2016 Kyoto LT (2016-09-10) 4

5. Programming contest RubyKaigi 2016 Kyoto LT (2016-09-10) 5

6. Write a program fast and correctly RubyKaigi 2016 Kyoto LT

   (2016-09-10) 6

7. Need C(++, #) or Java? RubyKaigi 2016 Kyoto LT (2016-09-10)

   7

8. You can use Ruby too! RubyKaigi 2016 Kyoto LT (2016-09-10)

   8

9. Sites which supports Ruby • Sphere Online Judge • Aizu

   Online Judge • yukicoder • AtCoder ←Today's topic RubyKaigi 2016 Kyoto LT (2016-09-10) 9

10. atcoder.jp • AtCoder Grand Contest • AtCoder Regular Contest •

    AtCoder Beginner Contest • AtCoder Typical Contest RubyKaigi 2016 Kyoto LT (2016-09-10) 10

11. Don't join the contest RubyKaigi 2016 Kyoto LT (2016-09-10) 11

12. Try previous contests first ! RubyKaigi 2016 Kyoto LT (2016-09-10)

    12

13. ! • Any%me • No %me limit RubyKaigi 2016 Kyoto

    LT (2016-09-10) 13

14. • AtCoder Grand Contest • AtCoder Regular Contest • AtCoder

    Beginner Contest • AtCoder Typical Contest RubyKaigi 2016 Kyoto LT (2016-09-10) 14

15. AtCoder Beginner Contest • A: Very easy • B: Easy

    • C: Easy? • D: Not really easy RubyKaigi 2016 Kyoto LT (2016-09-10) 15

16. But Ruby is slow...? ! RubyKaigi 2016 Kyoto LT (2016-09-10)

    16

17. No problem! RubyKaigi 2016 Kyoto LT (2016-09-10) 17

18. Algorithm Ma-ers ! RubyKaigi 2016 Kyoto LT (2016-09-10) 18

19. Example: one-line Reversi RubyKaigi 2016 Kyoto LT (2016-09-10) 19

20. 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

21. 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

22. RubyKaigi 2016 Kyoto LT (2016-09-10) 22

23. 200,000 pieces ! 200,000 ranges ! RubyKaigi 2016 Kyoto LT

    (2016-09-10) 23

24. 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

25. ⏰ Time Limit = 2 sec. RubyKaigi 2016 Kyoto LT

    (2016-09-10) 25

26. Be#er algorithm Memorize where color changes 10001 23005 ɹɹɹɹ↓ɹɹ↓ •••...•◦...◦•••

    RubyKaigi 2016 Kyoto LT (2016-09-10) 26

27. Passed! ! RubyKaigi 2016 Kyoto LT (2016-09-10) 27

28. You can try Compe//ve Prograaming in Ruby ! (at least

    for beginner contest) RubyKaigi 2016 Kyoto LT (2016-09-10) 28

29. ! BTW ! RubyKaigi 2016 Kyoto LT (2016-09-10) 29

30. RubyKaigi 2016 Kyoto LT (2016-09-10) 30

31. ABC037-D • I couldn't pass with Ruby ! • Traversing

    1000x1000 maze • Maybe with Ruby3...? RubyKaigi 2016 Kyoto LT (2016-09-10) 31

32. Crystal passes ※CrystalɿRuby-like sta0cally typed language RubyKaigi 2016 Kyoto LT

    (2016-09-10) 32

33. Pypy2 passes ※Pypy2ɿFaster Python implemanta2on RubyKaigi 2016 Kyoto LT (2016-09-10)

    33

34. Python3 passes!? ! RubyKaigi 2016 Kyoto LT (2016-09-10) 34

35. RubyKaigi 2016 Kyoto LT (2016-09-10) 35

36. RubyKaigi 2016 Kyoto LT (2016-09-10) 36

37. RubyKaigi 2016 Kyoto LT (2016-09-10) 37

38. (DON'T TRY THIS AT HOME !) RubyKaigi 2016 Kyoto LT

    (2016-09-10) 38