Baby steps to migratory bird

元半導体系エンジニア、今Webエンジニアの雑記

はじめてのRubyKaigi 予習編

いよいよ明日からRubyKaigiですね。

rubykaigi.org

今回RubyKaigiに初めて参加するので、事前に情報収集したことをまとめてみました。

少しでもRubyKaigiチョットワカルための手助けになれれば嬉しいです。

RubyKaigiについて

そもそもRubyってどんなカンファレンスなのだろう?ということについては、 RailsDM 2018 Day4のKeynoteでamatsudaさんが話されていたので、資料へのリンクを貼っておきます。

A RubyKaigi Talk - Speaker Deck

数あるカンファレンスが方向性を模索する中、技術的に最高の質を担保していくぞという意気込みを全面に押し出されています。

会場

今回福岡空港から博多駅まではかなり近いのですが、そこから福岡国際会議場は少し行きづらいなと思っていところ、 SmartHRさんが会場/福岡空港/博多駅/天神駅の区間でシャトルを出してくださるようです!

詳しくはこちら↓

SmartHR シャトルバスの乗り方 #RubyKaigi2019 (4月18日〜20日) | 株式会社SmartHR

Japan Taxiさんがタクシースポンサーなのでタクシー情報も探してみたのですが、あいにく見つけられず。見つけたら追記します。

昼の部:セッション

先日開催されたRejectKaigiの「RubyKaigi 2019タイムテーブル徹底解説」にて、@a_matsudaさん & RubyKaigi運営チームによる各スピーカー&セッションの紹介があったので、そのときのメモを添えて。

ちなみにRubyKaigiでは英語の発表があるのですが、通訳があるトラックとないトラックがあります。

トラック 場所 通訳
A Main Hall (3F) あり
B Multi-purpose Hall (2F) なし
C 409 + 410 (4F) なし
D International Conference Room (5F) あり

1日目 (4/18)

9:00- 受付

10:00-11:10

トラック 発表タイトル スピーカー メモ
A (3F) The Year of Concurrency Yukihiro "Matz" Matsumoto 【Keynote】Ruby3のなにか

11:20-12:00

トラック 発表タイトル スピーカー 資料 メモ
A (3F) Ruby 3 Progress Report Matz & the Ruby Core Team 資料 Ruby3の進捗レポート

12:00-13:30 ランチ

下のグルメ情報をチェック!

13:30-14:10

トラック 発表タイトル スピーカー 資料 メモ
A (3F) Performance Improvement of Ruby 2.7 JIT in Real World Takashi Kokubun 資料 MJIT, Railsも早くなる?
B (2F) How to take over a Ruby gem Maciej Mensfeld 資料 Rubyemsの乗っ取られをどう防ぐか (最近話題ですね)。本職がセキュリティの人
C (4F) Terminal Editors For Ruby Core Toolchain ITOYANAGI Sakura まだ Pure Ruby互換のライブラリ作った
D (5F) How to use OpenAPI3 for API developer ota42y 資料 SwaggerがOpenAPI3になる、Rackでうまく使えるように対応

参加予定:Ruby Gemのセキュリティの話が気になります。

14:20-15:00

トラック 発表タイトル スピーカー 資料 メモ
A (3F) Write a Ruby interpreter in Ruby for Ruby 3 Koichi Sasada まだ Ruby3向けのインタプリタ、Cで書いてた部分をRubyで書いた
B (2F) Determining Ruby Process Counts: Theory and Practice Nate Berkopec まだ Speed shopの人、GCパラメータの解説
C (4F) Pathfinder - Building a Container Platform in Ruby Ecosystem Giovanni Sakti まだ コンテナマネージャを自作した話
D (5F) Pragmatic Monadic Programing in Ruby joker1007 資料 Rubyの黒魔術、モナドを実装する試み

参加予定:迷い中。。

15:00-15:40 おやつタイム

15:40-16:20

トラック 発表タイトル スピーカー 資料 メモ
A (3F) A Type-level Ruby Interpreter for Testing and Understanding Yusuke Endoh 資料 型の話、VMをもう一個作る
B (2F) Compiling Ruby to idiomatic code in static languages Alexander Ivanov&Zahary Karadjov まだ トランスパイラ、例えばRubyで書いたライブラリをPythonで使える的な。型もつけられる
C (4F) Writing Debuggers in Plain Ruby! Fact or fiction? Genadi Samokovarov まだ Web consoleの作者、Pure Rubyでデバッガー
D (5F) Ruby for NLP Yoh Osaki 資料 Rubyで自然言語処理

参加予定:D

16:30-17:10

トラック 発表タイトル スピーカー 資料 メモ
A (3F) Fibers Are the Right Solution Samuel Williams まだ Fiber周りのコード、Rubyコミッタの最若手
B (2F) A Bundle of Joy: Rewriting for Performance Matthew Draper まだ Rails commiter、bundler遅いので書き直した(動くやつ)
C (4F) A Deep Learning Adventure Paolo Perrotta まだ メタプログラミングRubyの著者、Deep learning本書いた(イントロ的な内容になりそう)
D (5F) RMagick, migrate to ImageMagick 7 Shizuo Fujita 資料 RMagickのメンテの話。予定より進捗遅れてるけど、色々やってるよ

参加予定:A

17:20-18:00

トラック 発表タイトル スピーカー 資料 メモ
A (3F) Pattern matching - New feature in Ruby 2.7 Kazuki Tsujimoto 資料 Pattern matching (今回のRubyKaigiの目玉)、Ruby2.7
B (2F) Building Serverless Applications in Ruby with AWS Lambda Alex Wood まだ AWS SDK Rubyのメンテナ、Ruby with Lambdaの話
C (4F) GraphQL Migration: A Proper Use Case for Metaprogramming? Shawnee Gao 資料 RubyのメタプロでGraphQLを使いこなす
D (5F) Compacting GC for MRI v2 Aaron Patterson 資料 Compacting GC for MRI v2 (タイトルそのままや。。)

参加予定:A

2日目 (4/19)

8:30-10:00 朝食

2日目の朝はRubyKaigi会場とお隣の福岡サンパレスホテルで朝食をいただけます。

Official Breakfast sponsored by Medley

Stripe - RubyKaigi Breakfast with Stripe

10:00-11:10

トラック 発表タイトル スピーカー メモ
A (3F) All bugfixes are incompatibilities nagachika 【Keynote】ガッツリな話

11:20-12:00

トラック 発表タイトル スピーカー メモ
A (3F) How RSpec works Sam Phippen RSpecメンテナ
B (2F) Six Years of Ruby Performance: A History Noah Gibbs おなじみ?のノアコーナー、Rubyのパフォーマンスの話
C (4F) Practical mruby/c firmware development with CRuby Hitoshi HASUMI (メモりそこないました。。)
D (5F) Better CSV processing with Ruby 2.6 Kouhei Sutou & Kazuma Furuhashi CSVのパフォーマンスの話

参加予定:D, RubyData関連でCSV気になります。

12:00-13:30 ランチ

下のグルメ情報をチェック!

13:30-14:10

トラック 発表タイトル スピーカー メモ
A (3F) intimate Chat with Matz and mruby developers about mruby Hiromasa Ishii mruby漫談
B (2F) Zeitwerk: A new code loader Xavier Noria Zeitwerk (Rails6に入る)、A new code loader
C (4F) Yabeda: Monitoring monogatari Andrey Novikov ロシア方面出身の火星人?、Rubyのモニタリングの話
D (5F) Ovto: Frontend web framework for Rubyists Yutaka HARA Ovto、るびまに予習資料あり

参加予定:B

14:20-15:00

トラック 発表タイトル スピーカー メモ
A (3F) State of Sorbet: A Type Checker for Ruby Jake Zimmerman & Paul Tarjan Stripe with Sorbet、今年OSS化
B (2F) Actionable Code Coverage Michael Grosser Coverageライブラリの話
C (4F) RubyData Workshop RubyData team ワークショップ、おやつタイムまでぶちぬき、おすすめ
D (5F) Terminal curses Shugo Maeda Rubyでテキストデータ、cursesの話、時代はTUI

参加予定:C, RailsDMでの発表を聞いて以来RubyDataが気になっているので、ワークショップに出てみようと思っています。

15:00-15:40 おやつタイム

15:40-16:20

トラック 発表タイトル スピーカー メモ
A (3F) A light weight JIT compiler project for CRuby Vladimir Makarov Stripe with Sorbet、今年OSS化
B (2F) Building a game for the Nintendo Switch using Ruby Amir Rajan Swithのゲームをmrubyで作った
C (4F) Crystalball: predicting test failures Alex Rodionov Celenium driver gemのメンテナ、テスト回した時にどこを通ったかを紐付ける。リグレッションテストを効率的に回す。期待度かなり大
D (5F) The fastest way to bootstrap Ruby on Rails Uchio KONDO Rubyでコンテナ

参加予定:C

16:30-17:10

トラック 発表タイトル スピーカー メモ
A (3F) Benchmarking your code, inside and out Emily Stolfo elastic searchの中の人、ベンチマークとパフォーマンスの話。かなり規模がでかいやつ
B (2F) Beyond puts: TruffleRuby’s Modern Debugger Using Chrome Kevin Menard これすごそう。 ChromeのDev toolを使ってRubyのデバッグをできるようにする
C (4F) Building Homebrew in Ruby: The Good, Bad and Ugly Mike McQuaid Homebrewのメンテナ、ver2.0のお披露目の話?
D (5F) What is Domain Specific Language? Tanaka Akira DSLとはなにか?、DSLと普通のライブラリの違いにもんもんとしていたが納得できる結論がでた

参加予定:A or C

17:20-18:30

トラック 発表タイトル スピーカー メモ
A (3F) LT LT LT

3日目 (4/20)

8:30-10:00 朝食

3日目の朝はRubyKaigi会場で朝食をいただけます。

Official Breakfast sponsored by Medley

10:00-11:10

トラック 発表タイトル スピーカー メモ
A (3F) Ruby Committers vs the World CRuby Committers ぐだぐだやるw

11:20-12:00

トラック 発表タイトル スピーカー メモ
A (3F) (partially) Non-volatile mruby Yurie Yamane(team yamanekko) & Masayoshi Takahashi スタティックなmruby
B (2F) Fuzzing native Ruby code with Kisaten Ariel Zelivansky Fuzzing、すごくテッキーになりそう
C (4F) The Selfish Programmer Justin Searls すごくいい話?
D (5F) Cleaning up a huge ruby application Sangyong Sim one shot coverage、実際に使われていないコードを削除

参加予定:D

12:00-13:30 ランチ

下のグルメ情報をチェック!

13:30-14:10

トラック 発表タイトル スピーカー メモ
A (3F) The challenges behind Ruby type checking Soutaro Matsumoto type、去年の続き
B (2F) JRuby: The Road to Ruby 2.6 and Rails 6 Charles Nutter & Thomas E Enebo JRuby on Rails6
C (4F) Running Ruby On The Apple II Colin Fulton 16bitでRubyをコンパイル(8bitでもいける?)
D (5F) Best practices in web API client development Go Sueyoshi APIクライアントの話

参加予定:D or A

14:20-15:00

トラック 発表タイトル スピーカー メモ
A (3F) The future of the Bundled Bundler with RubyGems Hiroshi SHIBATA RubyGems, Bundlerの未来
B (2F) Pre-evaluation in Ruby Kevin Deisz 事前実行で最適化
C (4F) dRuby 20th anniversary hands-on workshop Masatoshi SEKI dRubyのワークショップ(おやつの時間打ち抜きでやる)
D (5F) Performance Optimization Techniques of MessagePack-Ruby Sadayuki Furuhashi MessagePack、世界最速オーサライズシリアライゼーションプロトコル

参加予定:B or D

15:00-15:40 おやつタイム

15:40-16:20

トラック 発表タイトル スピーカー メモ
A (3F) Reducing ActiveRecord memory consumption using Apache Arrow Kenta Murata pluckを使ってメモリ使用量を削減
B (2F) Ruby Serverless Framework Tung Nguyen Ruby on Jetsの作者(Lambdaで動くRailsみたいなやつ)
C (4F) Play with local vars Tatsuhiro Ujihisa Rubyのローカル変数面白いよ
D (5F) Timezone API nobu Timeにゾーンの情報をもたせるよう変更した

参加予定:A or C

16:30-17:10

トラック 発表タイトル スピーカー メモ
A (3F) The send-pop optimisation Urabe, Shyouhei 今回一番テッキーな話。rubyの返り値を無視させると、色々最適化できる
B (2F) TruffleRuby: Wrapping up compatibility for C extensions Petr Chalupa TruffleRuby、Javaで書かれているRubyがClangで動く
C (4F) Working towards Bundler 3 Colby Swandale 未来のBundlerの話
D (5F) Red Chainer and Cumo: Practical Deep Learning in Ruby Naotoshi Seo & Yusaku Hatanaka GPU

参加予定:A

17:20-18:30

トラック 発表タイトル スピーカー メモ
A (3F) Optimization Techniques Used by the Benchmark Winners Jeremy Evans 【Keynote】sequel、loader(恐ろしく早いフレームワーク)、ellvis、テクニカルな話

クロージング

夜の部:パーティ

RubyKaigi前日から、毎夜どこかでイベントがあります。 公式パーティ以外は申込みが必要です。

Parties - RubyKaigi 2019

RubyistはKaigi後、川に集まる習性があるらしいです。。 デカ外人さんにも会いたい人は川情報をお見逃しなく。

去年の様子↓

アフターイベント

RubyKaigi翌日にもイベントがあります。 僕はランニングイベントに申し込んだので、頑張って早く起きねば!

rubykaigi5k.connpass.com

fukuokarb.connpass.com

グルメ情報

tech.smarthr.jp

mrubyforum.blogspot.com

mrubyforum.blogspot.com

まとめ

色々てんこもりな4日間、とても楽しみです!!

【振り返り】GCJ2019 Round 1A: Pylons

今日はGoogle Code Jamの3回あるRound1のうちの初日でした。

先週末の予選を終えてからAtcoderに登録し簡単な問題を解いてみたのですが、 流石に1週間でRound1をパスできるほど甘くなかったです^^;

マス目を埋める問題は初見だったので、"マス目 競技プログラミング"でググりつつ「DPとは。。」という気持ちになり、 これは素手じゃ戦えんなと悟りPCを閉じて走りに行きました(完)

とこれだけでは何も残らないので、競技プログラミングの先輩が公開しているコードをRubyで書き直しつつ振り返っていきます。

問題概要

  • R行C列のマス目が与えられる
  • 全てのマス目を1回ずつ通る道順を求める
  • 次に移動するとき、今のマスから見て前後斜め直線状のマスを選ぶことはできない (チェスならクイーン、将棋なら飛車+角行が移動できる位置)
  • 実現できない場合は"IMPOSSIBLE"、できる場合は"POSSIBLE"を返し道順を出力する

制限

  • 時間:20sec / テストセット
  • テストセット1: T=16, 2≦R≦5, 2≦C≦5
  • テストセット2: 1≦R≦100, 2≦R≦20, 2≦C≦20

コードの解析

今回もすでにけんちょんさんが記事をアップしていたので、ありがたく拝読させて頂き、まずはRubyに焼き直してみました。

GCJ 2019 Round 1A A - Pylons - けんちょんの競プロ精進記録

ちなみに今回採用すべき解法はDPではないらしく、GCJの解説によるとKnight's tourというチェスのナイトのような動き(将棋だと桂馬)を採用したアルゴリズムが1つの解のようです。

# ルート生成
def route_generator(h, w)
  # ダメなパターンを先に除外
  return false if h == 2 && w < 5
  return false if h == 3 && w < 4
  return false if h == 4 && w < 4

  # ルートを作る
  arr = route(h, w)

  # 対称なグリッド対策
  if (h % 2 == 0) && h == w
    arr = avoid_conflict(h, w, arr)
  end

  arr
end


def route(h, w)
  arr = []

  (0...w).each do |j|
    (0...h).each do |i|
      if i % 2 == 0
        arr << [i, j]
      else
        (h == 2) ? arr << [i, (j + 3) % w] : arr << [i, (j + 2) % w]
      end
    end
  end

  arr
end

def avoid_conflict(h, w, arr)
  p = arr[h*w - h]
  arr.delete_at(h*w - h)
  arr << p

  arr
end

# 解答のための形作り
def answer_formatter(h, w)
  answer = ""
  swapped = false

  if h > w
    h, w = w, h
    swapped = true
  end

  if arr = route_generator(h, w)
    answer << "POSSIBLE\n"
    arr.each do |el|
      if swapped
        el[0], el[1] = el[1], el[0]
      end

      answer << "#{el[0]+1} #{el[1]+1}\n"
    end
  else
    answer << "IMPOSSIBLE\n"
  end

  answer
end


t = gets.chomp.to_i

t.times do |i|
  h, w = gets.chomp.split(" ").map(&:to_i)
  answer = answer_formatter(h, w)
  puts "Case ##{i + 1}: #{answer}"
end

アルゴリズム

公式の解説を読むといくつかアルゴリズムが紹介されていました。 力任せ探索と乱択アルゴリズムは、時間が許せばそのうち結果が出るが、問題によっては計算量が爆増してしまうため最後のテストセットまでクリアできないことが多そうです(現実問題では札束で殴って許されるケースもありますが、、)。

  • Brute-force search (力任せ探索)
  • Randomized algorithm (乱択アルゴリズム)
  • Dynamic Programming (DP、動的計画法)
  • Greedy Algorithm (貪欲法)

動的計画法と貪欲法については、これから勉強していく予定です。

動的計画法の導入としては下記のブログで、パフォーマンス的な利点も含めてわかりやすく説明されていました。

動的計画法(Dynamic Programming)をサルでも分かるように説明する - その1(フィボナッチ数列) - ベルリンのITスタートアップで働くソフトウェアエンジニアのブログ

まとめ

さっそくアルゴリズムの壁に直面したので、下記記事を参考に修行していこうという機運が高まりました。 Round 1Bではもう少し良い結果を出せるように頑張ります。

qiita.com

また今回もC++のコードを読解したのですが、リファレンスが利用しやすくて思ったより捗りました。あとRuby書くの楽すぎるでしょ!という気持ちも高まりました笑

PG::NotNullViolation: ERRORを解消する

DBにとあるレコードを保存しようとしたところ、下記のエラーにハマったのでそのメモ。

ActiveRecord::NotNullViolation: PG::NotNullViolation: ERROR:  null value in column "hoge_cd" violates not-null constraint
DETAIL:  Failing row contains (fuga, ccc, 2019-04-01, 2019-04-03).
: INSERT INTO "foo" ("bar_id", "hoge_type_cd", "created_at", "updated_at") VALUES ($1, $2, $3, $4,) RETURNING "id"

※テーブル構造やデータは若干修正しています

環境

  • 言語: Ruby 2.4
  • FW: Rails 5.1
  • DB: PostgreSQL

状況

  • hoge_typeに対してsimple_enumでenumを利用
  • shemaの定義は大丈夫そう
  • as_enumもモデルに記述済
# db/schema.rb

  create_table "foo", force: :cascade do |t|
    t.integer   "baar_id",             null: false
    t.integer  "hoge_type_cd",     default: 1, null: false
    t.datetime "created_at"
    t.datetime "updated_at"
  end
# app/models/foo.rb

class Foo < ActiveRecord::Base
  as_enum :hoge_type, {
      xxx: 1,
      yyy: 2,
      zzz: 3,
  }, prefix: true

end

結論

定義も大丈夫だしなんでエラーが出るんじゃ!と悶々してたんですが、 結論としてはhoge_enumに対してas_enumで定義していない値(今回はccc)を保存しようとしているのが原因でした。

# app/models/foo.rb

class Foo < ActiveRecord::Base
  as_enum :hoge_type, {
      xxx: 1,
      yyy: 2,
      zzz: 3,
      ccc: 4, # ここに追記
  }, prefix: true

end

辿り着くまでに見た記事など

Rails標準のenumとgemを使うのだとどちらがいいかは、今後調べたいです。

【WIP】【振り返り】GCJ2019 Qualification Round: You Can Go Your Own Way

今日は下記記事の2問目について少しずつ振り返りを進めていきます。

roo-ashi.hatenadiary.com

ちなみにGoogle Code Jamのサイトに行くと、今でもSubmitしたコードを採点してくれます。

今回もけんちょんさんの記事を参考にRubyで実装していきます。

GCJ 2019 Qual B - You Can Go Your Own Way - けんちょんの競プロ精進記録

本番でSubmitしたコード

def route_choice(str)
  route = ''
  rival_route = str
  while
  if check_last_motion(rival_route) == 'S'
    route.insert(0, 'E')
  else
    route.insert(0, 'S')
  end
    rival_route.chop!
    if rival_route == ''
      break
    end
  end
  route
end

def check_last_motion(str)
  str[-1]
end

def add_motion(route, motion)
  route.insert(0, motion)
end

t = gets.chomp.to_i

t.times do |i|
  n = gets.chomp.to_i
  str = gets.chomp
  route = route_choice(str)
  puts "Case ##{i + 1}: #{route}"
end

考え方がわかるとシンプルな実装になりますね↓

競技プロerにならったコード

def route_choice(str)
  route = ''
  
  (0...str.size).each do |letter|
    if str[letter] == 'E'
      route << 'S'
    else
      route << 'E'
    end
  end
  
  route
end


t = gets.chomp.to_i

t.times do |i|
  n = gets.chomp.to_i
  str = gets.chomp
  route = route_choice(str)
  puts "Case ##{i + 1}: #{route}"
end

ちょっと味気ないのでワンライナーにしてみました。 (もしかしてgetsするところも含めてワンライナーできるんでしょうか:eyes:)

ワンライナー

def route_choice(rival_route)
  (0...rival_route.size).inject('') {|route, idx| rival_route[idx] == 'E' ? route << 'S' : route << 'E'}
end


t = gets.chomp.to_i

t.times do |i|
  n = gets.chomp.to_i
  str = gets.chomp
  route = route_choice(str)
  puts "Case ##{i + 1}: #{route}"
end

まとめ

2問分の振り返りを通じて、一見数字や経路など情報量が多そうな対象をそのまま鵜呑みにせず、ただの文字列とみなすことで計算量を減らすのがコツなのだなぁと思いました。

【WIP】【振り返り】GCJ2019 Qualification Round: Foregone Solution

昨日の記事の1問目について少しずつ振り返りを進めていきます。

roo-ashi.hatenadiary.com

ちなみにGoogle Code Jamのサイトに行くと、今でもSubmitしたコードを採点してくれます。

まずはけんちょんさんの記事を参考にRubyで実装していきます。

GCJ 2019 Qual A - Foregone Solution - けんちょんの競プロ精進記録

競技プロerにならったコード

def separator(n)
  a = ''
  b = ''
  
  (0...n.size).each do |idx|
    if n[idx] != '4'
      a << '0'
      b << n[idx]
    else
      a << '1'
      b << '3'
    end
    
    a = '' if a == '0' # leading zero対策
  end

  return a, b
end

t = gets.chomp.to_i

t.times do |i|
  n = gets.chomp
  a, b = separator(n)
  puts "Case ##{i + 1}: #{a} #{b}"
end

自分が本番でSubmitしたコードよりかなりシンプルです。

本番でSubmitしたコード

def include_digit_four?(num)
  /4/ =~ num.to_s
end

def find_index_of_four(num) # 中身が同じメソッドを書いてしまった 汗
  /4/ =~ num.to_s
end

def one_digit_separator(arr, num)
  index = find_index_of_four(arr[0])
  b = arr[1] + 10 ** (arr[0].to_s.size - index - 1)
  a = num - b
  return a, b
end

def separator(num)
  arr = [num, 0]
  while
    arr = one_digit_separator(arr, num)
    if !include_digit_four?(arr[0]) && !include_digit_four?(arr[1])
      break
    end
  end
  return arr[0], arr[1]
end

t = gets.chomp.to_i

t.times do |i|
  n = gets.chomp.to_i
  a, b = separator(n)
  puts "Case ##{i + 1}: #{a} #{b}"
end

ToDo

Webアプリの機能に導入したケースを想定して下記でも追記していく予定です。

  • Class/Module定義
  • 4以外のキーが壊れた場合

【参加ログ】Google Code Jam 2019: Qualification Round

Google Code Jam 2019のQualification Roundに参加したのでその記録です。

Google Code Jamとは

Googleが主催しているプログラミングコンテストです。 今年は予選から3回戦まではオンライン、決勝は1つの会場で行われます (今年はカリフォルニアのGoogleオフィス)。

codingcompetitions.withgoogle.com

今年のスケジュール

フェーズ 開始 (JST) 終了 (JST) 制限時間 通過条件
Qualification Round 4/6 08:00 4/7 11:00 27hrs 30pts取得
Round 1A 4/13 10:00 4/13 12:30 2.5hrs 上位1500位まで
Round 1B 4/29 01:00 4/29 03:30 2.5hrs 上位1500位まで
Round 1C 5/4 18:00 5/4 20:30 2.5hrs 上位1500位まで
Round 2 5/18 23:00 5/19 01:30 2.5hrs 上位1000位まで
Round 3 6/8 23:00 6/9 01:30 2.5hrs 上位25位まで
World Finals 8/9 4:30 8/9 08:30 4hrs

※Round1はA/B/Cのどれかで通過すればOKです (全部参加でき、A~Cで合わせて4500名が通過)

※決勝はCAの現地会場で実施されます。

スケジュールへのリンク

出題形式

今年のQualification Roundでは4種類の問題が与えられ、 問題に対して課された制約ごとに、ポイントが与えられます。

今回の配点はこんな感じです。

問題 Test set1 Test set2 Test set3
Foregone Solution 6pts 10pts 1pts
You Can Go Your Own Way 5pts 9pts 10pts
Cryptopangrams 10pts 15pts
Dat Bae 14pts 20pts

例えば、N桁の整数に関する問題に対して、 計算量でテストセットの難易度別にポイントが加算されるといった具合です。

  • Test set1 (6pts): 1 < N < 105
  • Test set2 (10pts): 1 < N < 105
  • Test set3 (1pts): 1 < N < 10100

ちなみにテストセットにはVisible/Hiddenの2種類があり、 Visibleは解答を送信した時点で正否がわかりますが、Hiddenはコンテスト期間が終わって初めて正否が公開されます。

それでは今回自分が解いた問題 (2問目まで) について書いていきます。

1問目: Foregone Solution (6pts, 10pts, 1pts)

問題

  • 100桁以下のNが与えられる
    • Nの全桁のうち、最低1つに4が含まれる
  • a + b = N
    • a, bはどの桁にも4を含まない整数

問題へのリンク

制約

  • Test set1: 1 < N < 105
  • Test set2: 1 < N < 109
  • Test set3: 1 < N < 10100

考えたこと

まずはコンテストの形式に慣れるため、最初から全テストを通すことは狙わずにサブミットしていこうと考えました。 そのため、最初はNをシンプルに1ずつずらしていくという力技の処理で書いてみました。 案の定Test set2でランタイムエラーとなったため、4を検知したら1と3に分けるよう決め打ちするように変更したところパスしました。

自分の解答

1回目

def separator(num)
  a = 1
  while
    b = num - a
    if !include_digit_four?(a) && !include_digit_four?(b)
      break
    end
    a += 1
  end
  return a, b
end

def include_digit_four?(num)
  /4/ =~ num.to_s
end

t = gets.chomp.to_i

t.times do |i|
  n = gets.chomp.to_i
  a, b = separator(n)
  puts "Case ##{i + 1}: #{a} #{b}"
  # Case #x: A B
end

最終版

def include_digit_four?(num)
  /4/ =~ num.to_s
end

def find_index_of_four(num) # 中身が同じメソッドを書いてしまった 汗
  /4/ =~ num.to_s
end

def one_digit_separator(arr, num)
  index = find_index_of_four(arr[0])
  b = arr[1] + 10 ** (arr[0].to_s.size - index - 1)
  a = num - b
  return a, b
end

def separator(num)
  arr = [num, 0]
  while
    arr = one_digit_separator(arr, num)
    if !include_digit_four?(arr[0]) && !include_digit_four?(arr[1])
      break
    end
  end
  return arr[0], arr[1]
end

t = gets.chomp.to_i

t.times do |i|
  n = gets.chomp.to_i
  a, b = separator(n)
  puts "Case ##{i + 1}: #{a} #{b}"
end

2問目: You Can Go Your Own Way (5pts, 9pts, 10pts)

問題

問題へのリンク

  • N x Nのマス目が与えられる
    • 北西 (左上) の最頂点がスタート、南東 (右下) の最頂点がゴール
    • 東 (右) か南 (下) 方向にのみ進める
  • ライバルの道順が与えられる (例:SEEESSES)
    • マス間の移動で、ライバル同じ進み方をすることが出来ない (同じマスに止まることはできるが、そこから同じ方向に進めない)。

制約

  • Test set1 (6pts): 2 ≤ N ≤ 10
  • Test set2 (10pts): 2 ≤ N ≤ 103
  • Test set3: (1pts) 1 < N < 104

考えたこと

紙に書きながら動き方を考えたところ、常にライバルと違う方向に進めば良さそうなことに気づきました (要はスタートからゴールまでの対角線に対して、反転させた経路を通れば良い)。

実装中はゴールから逆順に経路を決めていくイメージで実装を進めていたので、かなり冗長な書き方になってますが、本当は簡単なループでいけますね。。

雑だけどこんなイメージ

route = ''
(1..N.size).each do |letter|
  if N[letter] == 'E'
     route << 'S'
  else
     route << 'E'
  end
end

自分の解答

def route_choice(str)
  route = ''
  rival_route = str
  while
  if check_last_motion(rival_route) == 'S'
    route.insert(0, 'E')
  else
    route.insert(0, 'S')
  end
    rival_route.chop!
    if rival_route == ''
      break
    end
  end
  route
end

def check_last_motion(str)
  str[-1]
end

def add_motion(route, motion)
  route.insert(0, motion)
end

t = gets.chomp.to_i

t.times do |i|
  n = gets.chomp.to_i
  str = gets.chomp
  route = route_choice(str)
  puts "Case ##{i + 1}: #{route}"
end

結果

1, 2問目ともTest set3までパスしていて、41ptsで予選通過となりました。

振り返り

今回事前の準備なしで取り組んだのですが、色々詰まりつつも結構楽しかったです。 普段のノリでメソッドの意味合いを考えつつ進めていたのですが、競技的には余分で削ぎ落とすべき要素なのかもしれません。

さっそくアップされていた競プロの先輩達の振り返り記事を読んでみると、実装の仕方や観点が違い勉強になります。

GCJ 2019 Qual A - Foregone Solution - けんちょんの競プロ精進記録

GCJ 2019 Qual B - You Can Go Your Own Way - けんちょんの競プロ精進記録

Google Code Jam 2019 Qualification Round : A. Foregone Solution, B. You Can Go Your Own Way - kmjp's blog

PostgreSQLのバージョンを上げたらRails consoleが開かなくなった時の対処メモ

色々アップデートしてたらRails consoleが開かなくなり対処したのでそのメモです。

>bin/rails c

(Traceback省略)

/Users/(ユーザー名)/.rvm/gems/ruby-2.5.1/gems/bootsnap-1.4.1/lib/bootsnap/load_path_cache/core_ext/kernel_require.rb:21:in `require': dlopen(/Users/(ユーザー名)/.rvm/rubies/ruby-2.5.1/lib/ruby/2.5.0/x86_64-darwin16/readline.bundle, 9): Library not loaded: /usr/local/opt/readline/lib/libreadline.7.dylib (LoadError)
  Referenced from: /Users/(ユーザー名)/.rvm/rubies/ruby-2.5.1/lib/ruby/2.5.0/x86_64-darwin16/readline.bundle
  Reason: image not found - /Users/(ユーザー名)/.rvm/rubies/ruby-2.5.1/lib/ruby/2.5.0/x86_64-darwin16/readline.bundle

エラーをみると/usr/local/opt/readline/lib/libreadline.7.dylib (LoadError)あたりが怪しそうなのでググってみると出てきたのが以下↓

github.com (即効でRailsのissueじゃねぇ!ってクローズされてて吹いたw)

リンク先だといくつか対処法が書いてあるので整理します。 結論としては1が良いのかなと思います。

0. 開発環境

  • macOS sierra (10.12.6)
  • Rails 5.2.2
  • Ruby 2.5.1 (rbenv)

1. シンボリックリンクを作成する(し直す?)

2019/3/2時点だとこれでいけました。

ln -s /usr/local/opt/readline/lib/libreadline.8.0.dylib /usr/loc al/opt/readline/lib/libreadline.7.dylib

下記記事とHomebrewのサイトを見てみると、 最近PostgreSQLのバージョンを上げた影響でreadlineのバージョンも上がったため、

(原因)readline 7を読みに行ったが対象がない

(事象)LoadError

(対処)元の呼び出しでもreadline 8.0を呼び出せるようにシンボリックリンクを作成する。

という流れになったのだと予想。

thinkami.hatenablog.com

formulae.brew.sh

ちなみにシンボリックリンクとは?

www.itsenka.com

ln -s hoge fugaの意味について

http://www.turbolinux.co.jp/products/server/10s/manual/command_guide/command_guide/ln.html

ln の引数の順番で迷わなくなった - Qiita

2. rb-readlin gemを入れる

rb-readline gem

これでも一応動くようになりましたが、最近メンテされてないし。。

3. rbenv (またはrvm) を入れ直す

今回は試してないが、入れ直す時にリンクが作成されるのでは?と予想

まとめ

他にもバージョン上げた時に応用効きそう