【入社エントリ】新卒でモノグサに入社しました / 就活の振り返り

はじめに

こんにちは、こな(kona0001)です。

2023年4月よりモノグサ株式会社にソフトウェアエンジニアとして入社しました。

モノグサは記憶のプラットフォーム「Monoxer」を開発・提供している会社であり、全国の塾や中学・高校などを対象に事業を展開をしています。もっと分かりやすく説明すると、記憶を定着させることにフォーカスを置いた学習アプリを全国にお届けしています。

モノグサは2023年4月現在120人ほどの規模の会社で、いままさに成長中のベンチャー企業です。そして僕自身も新卒の身であり、ここが１社目の会社となります。

この記事では昨年行った就活の話、そして僕自身の思考整理も含めて、モノグサに入社した理由など書き連ねていこうと思います。会社選びで悩んでいる方の参考になれるような情報も書けたらなと思います。

いわゆる入社エントリ(という名の日記)になります。

RubyでAtcoder青入りしました！

青入り

先日のARC133で初めて黄パフォを出すことができ、念願の青入りを果たすことができました！！

初黄パフォでついに青入り！！！やったー！！！！！
konayukiさんのAtCoder Regular Contest 133での成績：339位
パフォーマンス：2072相当
レーティング：1571→1632 (+61) :)
Highestを更新し、2 級になりました！#AtCoder #ARC133 https://t.co/HMCNwzAb96 pic.twitter.com/P2mp1gLPcA

— こな (@kona0001) 2022年1月22日

入水してからおおよそ1年かかりましたが、無事に青までいくことができて一安心です。
色変記事ということでこれまでの精進具合とか水と青の違いとかを書いていこうと思います。

また競プロ界隈ではユーザ数が少ないRuby使いとしての、青になったうえでの色々な知見も書いてみます。

Rubyでの競プロとの向き合い方が水色の時とかなり変わったので、同じくRubyを使って競プロに取り組んでいる人たちの助けになればなぁと思います。

青達成時のいろいろなデータ

解いた問題数が綺麗に今年の西暦と重なりましたが、偶然こうなりました。運命を感じます。

同レート帯の人たちと比較すると問題はかなり解いている方だと思います。
これは、水色中位の頃まで「徹底的に下から埋める」という精進方法を取っていたからです。
また、RubyのLanguage Owner*1になりたいなぁとか思った時期に非公式コンテストの問題も埋め始めたというのも大きいです。

下からたくさん問題を解いたメリットとして、パフォーマンスの下限値が上がった気がします。
C-D問題くらいにある「たまたま知らなかった、知らないと手も足も出ない典型問題」が無くなり、「どんなに事故っても水パフォは出る」ような感覚が身につきました。

ただしデメリットとして高難度の問題が解けなくなります。
これは改めて思ったことなのですが、青になるために解かないといけない問題って水になるために解かないといけない問題と範囲が全然違う。

例えばDPを例に挙げてみると、問題を難易度順で下から埋めていくとDPの問題がまともに出てくるのって水色diff後半くらいからなんですよね。水diffの問題を下から7割くらい埋めていたとしても、DP問題が全く解けるようにはならない。逆に、下から埋める方針をやめてバランスよく高難度の問題を埋め始めてからDP問題が解けるようになってきました。DPだけじゃなく数学系数え上げ問題なんかも同じ傾向にあると思います。

僕自身、大勝利回がなかったのもこれが原因だと思っています。

最近だと、Xor基底を考える問題がABC236-Fに出ました。

下埋めを徹底したとして、Xor基底が初めて出てくるのは黄diffのXor Battleです(他にあるかもしれません)。
青diff以下をすべて埋めない限りこの知識を知りすらしないと思うと、非効率だと思いません？

ここで言いたいのは、下埋めを徹底すると一部の知識がしばらく身に付かなくなる可能性があるって事です。レートが伸び悩んでいた時、たまには背伸びして難しい問題にチャレンジするべきだったなぁとしみじみ思います。

自分の実力より1-2色分上の高難易度問題では、自分の知らないテクニックをいくつも使わないと解けない事が多々あります。ACするための負担は大きいけどその分得られる知識や経験は間違いなくあるので、レートが伸び悩んでる人はちょっと背伸びして難しい問題に挑戦してみると世界が変わるかもしれません。もちろん解説ACでOKです。

青になるためには

手っ取り早く言うと、精進をしろという事ですね。精進グラフを見ると露骨に出ていますが精進をサボってた時期とレートが停滞した時期がほぼ被るのですから分かりやすいものです。

問題を全く解いていない時期があるのには理由があって、簡単な問題を全部解いてしまったがために新しく問題をACするための負担が大きかったということです。簡単な問題であっても1問解けば競プロ精進モードに入るきっかけになりますよね。今思うとやる気が出ない時用に簡単な問題を取っておくべきだったかもしれません。

そして、自分にとって楽じゃない問題を解く試みもすべきです。毎日1ACとかしてても自分にとって楽な問題ばかりなら成長するうえで意味がないと思います（これは僕も1年前にやってしまっていました）。

これをしないと弱点ができ足を引っ張ることとなります（僕の場合はDP力）。知っている問題に対する早解き力だけ向上させるよりも、解ける問題の幅を広める方がレートは上がりやすいし安定もすると思います。

水と青の違い

水と青の違いは、ズバリ典型の引き出し力と典型に落とし込む力です。
色々な典型を知っていることはもちろん、その先の応用させるところまでできれば青になれるでしょう。これを鍛えるには問題をたくさん解いて学ぶ・慣れるしかないと思います。

また、問題をたくさん解いてると

「この悩み方前にもしたなぁ...その時はUnionfind使ったら上手くいったんだよな。この問題でも使ったら...あ！解ける！」
（参考：https://atcoder.jp/contests/abc206/tasks/abc206_d）

ってなったりします。要するに考察のパターン化ですね。この引き出しも増えれば増えるほど強くなる気がします。
似た話で、いろんな細かい典型のライブラリを用意してあるかとかも水と青の違いな気がします。

別の水と青の違いとして「DP力」も頭に浮かびましたが、正直ここの差が出るのは青と黄だと思っています。

僕自身「水の頃と比較してDP問題が解けるようになりましたか？」と言われると「はい」とは言えない結果になっていますし、むしろ一番の弱点という自覚があります。が、青にはなれました。

また、DP問題が解けなくとも大きくレートを溶かすことはありませんでした。

ただ「DP練習してたらもっと早く青にいけたんだろうなぁ...」ってすごく後悔しています。青以上を目指す方は積極的にDPの練習をするといいと思います。特に、難しいDP問題となると高度典型とセットになってたりするので、精進するうえで得られる知識も多くお得感があります。

青になるまでに身につけたもの・よく使ったもの

色変記事によくあるやつです。水〜青でよく使った物のみ乗せてます。BFS等の基本的な典型は省略しています

•  データ構造
  • BIT(フェニック木)
  • Unionfind
  • Heap(優先度付きキュー)
  • SegmentTree(セグ木)
  • フロー(最大流)
• 典型アルゴリズム
  • グラフ編
    • LCA(共通祖先をセグ木使って求めるやつ)
    • 最小全域木(クラスカル法、優先度付きキュー使うやつ)
    • 木DP
    • 全方位木DP
    • ゲームDP(引き分け有り・無しどちらでも)
    • 木上の頂点間の経路を0(N)で求めるやつ
    • オイラーツアー
  • 数列編
    • bitDP
    • 桁DP
    • 部分列DP
    • 期待値DP
    • メモ化再帰
    • 座圧
    • 尺取り法
    • スライド最小値・最大値
    • 最長増加数列
    • 循環
    • 転倒数
    • 半分全列挙
    • 三分探索
    • マージテク
    • BIT使ってsetでの二分探索みたいなことをするやつ
    • 累積和をみて同じ数値のところを見るやつ
    • 総量が変わらないときMODを取るやつ
    • 中央値求めるとき二分探索するやつ
    • Xorは桁一つずつ見るってやつ
    • a[i]-iをするやつ
    • 高速な二次元累積和の計算
    • Z-Algorithm(文字列に関するやつ)
  • 数学編
    
    • 幾何ライブラリの整備(回転処理とか距離とか)
    • 中国剰余定理
    • フェルマーの小定理(M^(P-1)≡1 (Mod P))
    • 行列累乗

青を目指すのなら理解しておきたい。

この中でも特に使ったのがUnionfind・優先度付きキュー・転倒数・木DP・メモ化再帰・座圧あたりかな。

細かい典型とかもっとあるけど書くと大変なので割愛します。
大事なのはこれらの典型を『使いこなせる』ことで、問題に応じてアレンジできるくらいの理解度が必要でしょう。

Rubyでの競プロについて

僕はRubyを使って競技プログラミングをしています。
その理由は、コードを書いていて一番楽しいかつアルゴリズムをそのまま記述できる言語だと思っているからです。

しかしながら競技プログラミング界隈ではユーザ数が圧倒的に少なく、またRubyをメインで使用している強い人もいません。

更に言語自体の実行速度も遅く、制約の厳しい問題ではTLEに悩まされる事も多々あります。

水色になった頃はRuby一筋でいけるところまで頑張ってみようと思いましたが、少し前くらいから考え方が変わったのでここに書き記しておこうと思います。

Rubyのメリット

• コード記述量が短い
• すべてがオブジェクトでありそれに対する操作が直感的(たとえば true.! とか)
  • かなり日本語に近い文法でコードが書けます。逆に英語圏の人はここはデメリットかも
• 関数型プログラミングが書ける
• 多倍長整数だからオーバーフローを気にしなくていい
• gcd,lcm,modpowなどのメソッドが言語に組み込まれている
• コードを書いていて楽しい（主観）

Rubyのデメリット

• 実行速度が遅い
• 競技人口が少ない
• 知見も少ない
• set、heapが言語に組み込まれていない
  • setの代わりにhashはありますが、set内で二分探索しようとするとlower_boundが無いためBITなどのデータ構造を使う必要がでてきます
• 強い人がいないため難しい問題になるとAC提出が無かったりする

同系統の言語としてPythonが挙げられるので、Pythonとの違いも書いてみます。

Pythonとの比較

• 実行速度は実はPythonより速い
  • PyPyには圧倒的に負けます
• デフォ設定で再帰回数もPythonよりかなり多く実行できる
• 高速化モジュールなどはない(numpyみたいなの*2はある)
• 競技人口の圧倒的な差
• Python使いには赤コーダーをはじめ強い方が何人かいるが、Ruby使いにはせいぜい青コーダーしかいない(Rubyメインで黄色コーダー以上の方がいたらごめんなさい。アクティブの提出を見る感じいないという認識です)

まとめると、書き心地は最高だけど実行速度と競技人口が致命的に思えます。

実行速度について

結論から言って、Rubyだけしか使わないと黄色以上になるのはかなり厳しいと思いました。
その理由として水diff後半くらいの問題から制約が厳しく設定されることが多く、RubyだとどうしてもACできない・もしくは相当定数倍高速化しないと通せなくなるからです。

だいたいの目安で計算回数1.5×10^7が限界でしょう。これを越す問題はACをするのに相当な努力が必要となります。
問題なのがこの基準をオーバーする制約があまりにも多いということです。

以下、Rubyだと通せない/通すのが難しい制約です。

• N<=5000のO(N^2) 解法　ほぼ通せないうえにかなり多い制約です
• N<=300のO(N^3) 解法　これも多いです。ひどい時だとN<=500とかあります
• N<=20のO(N 2^N) 解法　bitDP系はだいたいアウト
• N<=16のO(3^N)解法　部分集合に着目する系もアウト
• N<=200000のO(Nlog^2(N))解法　二分探索内でソートとかするとアウト
• N<=2000のO(N^2logN)解法　二乗解法に二分探索が混ざるとアウト

なかなかに絶望的ですね。

特にN<=5000やN<=300の制約だとABC-EやARC-Cくらいから出ますし、そういった問題が出た時に理不尽な思いをしたこともしばしばです。

水になるくらいではあまり気にならなかったのですが、青になるくらいだと3回に1回ものコンテストの割合で制約の壁にぶち当たる印象です。
めっちゃ頑張れば解けないこともないのですが、その労力に見合っているかどうかは意識したほうがいいと思います。

例えば定数倍高速化のために不自然な実装を強いられた挙句TLEが出る危険性があるのであれば、ぎこちなくとも最初から別の高速な言語で書いた方が総合的に得ということです。

ここでとても嬉しいニュースなのですが、Rubyには文法はほぼそのままで高速なコンパイル言語となったCrystalが存在します。
情報の少なさがデメリットですが、まったく影響無いくらいにはRubyの気持ちでコードが書けます。
そのうえで速度が10倍以上の速さで実行でき、2.0×10^8くらいまでの量なら計算しても問題ないです。
使うっきゃないですね。

ただし、多倍長整数でなくなるためオーバーフローに気を付けないといけないところや、整数型のint32とint64の指定、Tuple型の存在など、静的型付け言語の仕様に慣れる必要はあるでしょう。
これは各種ジャンルの問題を計30問くらい解けば全く問題ないくらいには書けるようになります（自分はそうでした）。

そんなにハードルも高くないと思うので、Rubyが大好きで競プロでも使い続けたいという方はCrystalでも書けるようにしておくといいと思います。

というのも、最近Crystalのコードをちゃんと書けるようになったことで問題に対する見方が大きく変わった事があるからです。
それが「真にRubyだけしか使ってないと二乗解法や三乗解法にどんどん疎くなっていく」ということです。

緑くらいで経験することが多いのですが、いろいろ問題を解いていくと制約N<=2000とかN<=300の問題でTLEに悩まされ、不毛な時間を過ごすことになります。
そうしていくうちに「この制約の問題は大変だから後回しにしよう」とか「これは無理だ、飛ばそう」となりがちです。

結果として何が起こるかというと、二乗解法や三乗解法を想定としたアルゴリズムが身に付かなくなります。
DP問題なんかは二乗想定が多いですし、二次元問題なんかは二乗解法が必須です。
最短経路問題を解くワーシャルフロイドにおいても、Nが300を越すとだけでまともにACできなくなります。

ここがRuby使い全員の弱点になるわけですね。（Python使いの人もこのあたりの話は共通かと思います）
Ruby使ってる人は制約N<=2000とかN<=300を見ると嫌な気持ちになる人が多いのではないでしょうか。

Crystalをまともに使いはじめてから、この事にハッと気づかされました。
なんならACしていないABCの問題の多くが制約N<=5000だったみたいな経験も最近しました。

Crystalを使い始めたことで二乗解法や三乗解法の問題を考察することが増え、幅が広がって実力向上にもつながりました。

また、Crystalが常に視野に入っていることで雑な実装をする事が候補に入ってくることも利点でした。
Rubyで書くととても間に合わないような愚直DPがCrystalだと通せるのであれば、そっちの方が楽だよねって感じ。
bitDPのループをひとつ増やしても間に合うようになったり、DP配列を参照したり使いまわす必要もなくなったり、意図してなかった恩恵がすごいです。

とまあこの経験をしたのが本当に最近の話だったので、少し前までは極力全部Rubyで頑張るって思っていましたが、Crystalに本腰入れる前と後とでここまで考え方が変わるのかとびっくりしています。

これからも高速な言語はどんどん使った方が身になるし、楽なので、計算量ちょっとでも怪しいって思ったら積極的にCrystal使って書こうと思います。

ちなみに、今もCrystalをメインで使っている橙コーダーの方がいらっしゃるようです。
僕もよくコードを参考に見たりしていますが、そういった存在があるってだけでもめちゃくちゃ心強いです。

RubyとCrystal、実は競プロにおいてめちゃくちゃポテンシャルが高い組み合わせなんじゃないかって思ってます。
早解きのRubyと速度のCrystalで、暖色コーダーになってみたいものです。

Rubyの実行速度についてまとめると、高速な言語に触れると世界が広がるよっていうことと、RubyにはCrystalっていう文法ほぼそのままの静的言語があるよってことですね。

競技人口について

Rubyで競技プログラミングをしている人はかなり少ないです。

• 参考：ABC236本番中でのA問題AC者数
  
  • Ruby - 75
  • Python - 1739
  • C++ - 5628

調べてみると圧倒的な差でびっくりしました。Pythonの10分の1以下なんですね...

これがデメリットになるのが、参考になるコードが少なくなることです。
また、解説記事の充実度もめちゃくちゃ下がります。

Pythonのコードを読めばよくねって話にもなりますが、気持ち的に下がりませんか？僕は下がります。

そして高レートを目指すうえで気になってくるのが、黄diffくらいの問題からRubyでのAC者0人の問題が増えてくるって事です。
RubyでACできてる人が一人もいない状態。これ、結構絶望します。

実装難易度が高い問題とか「みんなどういう風に実装してるんだろう？」って見に行くけど、提出が無いことすら多々あります。
つまりRubyでの競プロは、強い人から学びづらい環境にあることが確かだと思います。

そしてこれは余談なのですが、高難易度問題のAC提出がコードゴルフ*3勢に支配されている事があります。

Rubyはとてもよく考えられた言語なので、必要最小限の記述でアルゴリズムを記述できます。
なのでコードゴルフをするための言語として選ばれることもあるみたいです。

が、精進のためにそのコードを参考にできるかと言われるとちょっと違うと思っています。

他のAC者がどんなコードを書いてるのか見に行って
「わーい、いっぱい提出あるー！」って思ってよく見てみると全部コードゴルフだったみたいな。

ちょっと残念な気持ちになります。
（RubyでのACが保証されて安心するみたいな気持ちも生じます）

まとめると、Rubyでの競プロ環境は発展途上といえるでしょう。
もっと人口が増えればまた全然違う環境になっていくと思います。

先にも書きましたがRuby+Crystalのポテンシャルはとんでもなくあると思っているので、少しでも人口が増えるような努力もしたいものです。
（ABCの解説記事とか書きたいけどモチベーション維持がきつそう...）

それでもRubyでの競プロは楽しいよって話

デメリットを長々と書きましたが、それでもRubyでの競プロはめちゃくちゃオススメしたいし、他の言語に乗り換える気も一切ありません。
Rubyは書いていて不便が無いし、間違いなく一番楽しい言語だと思います。
（Ruby以外の言語で「コード書くのが楽しい」って声はあまり聞きませんが、どうなんでしょうね？Ruby使いとそれ以外でのコーディングの楽しさに有意差が出るのか、ちょっと気になります。）

そして言語処理系の不整合もほとんどありません。
知る限り、除算(/)の解釈が曖昧ってことくらい。

またRubyはフロントエンドのイメージがあるかもしれませんが、関数型プログラミングもできるので実は数学的記述に強かったりもします。

Rubyは特に初心者の方や、これから競プロを始める人には一番推したい言語です。
唯一、endの多さは気になる方が多いかもしれません。
（余談ですが個人的に、RubyのendとPythonのコロン(:)は同じような印象があります。）

まあ乗り換え先の言語としてあえて推すものでもないなとは思います。

ここまで読んでくれた方にはぜひ、Rubyという言語での競プロに触れていただきたいです。
そして、楽しいと感じていただければ幸いです。

おわりに

無事に青になれましたが、自分の周りで青-水を反復している方を多数見かけるので自分もしばらくはそうなる気がします。
それでもめげずにコンテストには出続けたいです。

当面の目標は青を安定させることでしょうか。
どこかで橙パフォも取ってみたいです。
そのうち、ひょこんと黄色になりたいなぁって思ってます。
まだまだ伸びの限界はきてない感覚ですが、どうなることやら。

とても色変記事とは思えないような内容になりました。
もっと簡潔に文章を書けるようになりたいです。

最後に、水～青期間で解いたお気に入りの問題をいくつか張って締めようと思います。
水diff多めです。

• ABC200-D - Happy Birthday! 2
• ARC126-B - Cross-free Matching 
• ARC119-C - ARC Wrecker 2
• ARC120-C - Swaps 2
• ABC232-E - Rook Path
• ARC132-C - Almost Sorted
• ABC216-G - 01Sequence

*1:言語毎のACランキングのことです

*2:numo-narrayが使えます

*3:いかに短いコードでACできるか、を競うものです

本番で使えるRubyの定数倍高速化手法【競技プログラミング | Atcoder】

※本記事の対象はRubyで解く競技プログラミングにある程度慣れた方です。

参考までに、緑（rating:800）くらいの方からを対象にしています。 「ABCのC問題でTLEが取れない…」という方はそもそも解法が間違っている可能性があるので(ABC189-Cを除く)、別の方の記事もしくは公式解説を見る事をオススメします。

はじめに

Rubyで競技プログラミングをする際に、TLE(Time Limit Exceeded)に悩まされる事が多々あります。その原因として挙げられるのは以下の４つです。

1. そもそも解法が間違っている　…　①
2. Whileが抜け出せていない　…　②
3. 実装が悪い　…　③
4. 言語的に通せない　…　④

①はそもそも解法が間違っていて、計算量が爆発している一番よくある例ですね。ABC(Atcoder Biginner Contest)でいうところのC問題から意識する必要があります。この場合どのように実装を変えても、なんなら高速な言語に書き換えてもTLEは取れません(例外もありますが)。

解法そのものを変え、計算量の削減をする必要があります（本記事では扱いません）。

②はたま～に起こる、whileなどのループを抜け出せていないパターンです。この場合コードを見直すことで修正できることが多いですが、それに気づけない場合泥沼にハマって抜け出せなくなります。 回避方法として、プログラムの挙動をアルゴリズムとして記述し、具体的なシミュレートをすると気づける事が多いです。紙に書くなどして整理すると、この類のTLEは回避しやすくなるでしょう(この場合バグによるWAも同様に回避しやすくなります)。

ここからが本題で、③と④の場合。

同じ解法であっても、実装によって処理速度が大幅に変わる事があります。

特に、計算量(10⁶)を超える辺りからちょっとコードの書き方を変えるだけで100msもの実行時間が短くなったりします。AtcoderやCodeforcesでは基本的に実行時間制限が2secと短いので、100msの短縮が計算量の大きな問題でACできるかどうかに深く関ってきます。例えば、二次元グリッド問題(座標平面に沿って操作を行っていう問題)で想定解法なのにTLEが出るのはRuby競プロあるあるだと思います。

本記事では僕が意識して実戦している「定数倍高速化手法」についてまとめていきます。 ④については、記事の最後で触れています。

※定数倍高速化：いわゆる処理速度の高速化。同じアルゴリズムでより早く処理するためのテクニック。

以下、実行環境はAtcoderのコードテストを用いています（厳密な計測はしていませんのであしからず。。）Ruby verionは2.7.1です。

定数倍高速化手法

１．繰り返しではWhileを使う(重要度★★★★★)

繰り返し処理においてforやtimesは遅いので、Whileを使うようにしましょう。これは多重ループの際に本領を発揮します。

#ループ回数を数えるプログラム
n = gets.to_i
cnt = 0
for i in 0..n
    for j in 0..n
        cnt += 1
    end
end

#whileで高速化
n = gets.to_i
cnt = 0
i = 0
while i < n
    j = 0
    while j < n
        cnt += 1
        j += 1
    end
    i += 1
end

n	100	1000	2000	5000
for	61	106	201	1002
while	64	86	150	615

計算量: O(N²), 単位[ms]

別途インデックスを定義する必要がありコードが冗長になりますが、処理速度とのトレードオフと考えましょう。また注意点としてスキップ処理にnextを用いるとインデックスが更新されないので、正しい処理をさせるためにコードが難解になる可能性があります。

#nまでの偶数の和を数えるプログラム
n = gets.to_i
cnt = 0
for i in 1..n
    next if i%2==0
    cnt += i
end

n = gets.to_i
cnt = 0
i = 1
while i < n
    next if i%2==0  # ここでスキップ処理が入ると
    cnt += i
    i += 1  # インデントの更新も処理されなくなる
end

２．二次元配列は一次元配列として参照する（重要度★★★★☆）

動的計画法などで、dp[i][j]という書き方をすることがよくあります。ここで

dpi = dp[i]

のように、一つ目の添え字を参照して用いることで処理速度がグっと早くなります。

#n×nの配列を1回ずつ参照するプログラム
n = gets.to_i
dp = Array.new(n){Array.new(n,1)}
cnt = 0
for i in 0..n-1
    for j in 0..n-1
        cnt += dp[i][j]
    end
end

#一次元配列として参照するプログラム
n = gets.to_i
dp = Array.new(n){Array.new(n,1)}
cnt = 0
for i in 0..n-1
  dpi = dp[i]
  for j in 0..n-1
    cnt += dpi[j]
  end
end

n	100	1000	2000	5000
二次元参照	65	119	295	1481
一次元参照	63	114	275	1374

計算量: O(N²), 単位[ms]

（上のプログラムでは1個だけしか参照していませんが、参照すればするほど速くなります）

三次元の場合にも、二次元の参照を経てから一次元参照とすることで同様に高速になります。速くなる理由としてメモリアクセスがどうのこうのという原理があるわけですが、この記事では省略します。

３．文字列は文字配列として処理する（重要度★★★★★）

文字列は遅いです。Rubyでは

string = "文字列"
string[0] # => "文"

のように文字列に対して添え字を指定することで一文字取り出せますが、この処理は遅いです。対策として文字列に対するメソッドcharsを使いましょう。これは、文字列オブジェクトを文字の配列オブジェクトに変換するとても便利なメソッドです。

string = "文字配列"
string = string.chars # => ["文","字","配","列"]
string[0] # => "文"

こうすることで、一文字ずつ見ていく処理は変換前と同じ処理を同じコードで行うことが出来ます。ただし、複数文字を同時に扱う場合には注意が必要です。 ついでに、分解した後の文字配列オブジェクトはjoinメソッドを用いることで文字列に復元できます。

string = "文字列"
string = string.chars # => ["文","字","列"]
string.join # => "文字列"

４．一行処理＋ifは後置if

※追記あり
コメントにて「後置ifでも処理速度が変わらない、もしくは逆転することもあった」との報告を受けました。自分としては通常ifを後置ifに変えて処理速度が100msほど早くなった問題があったため(どれかは忘れました…)本記事のリストに入れていましたが、どうも不確実のようです。議論にはなると思うので、項目自体は消さずに残しておきます。条件等検討ついたらまた改めて追記します。

※再度追記
結論から言って後置ifでも実行時間は速くなりませんでした。Atcoderのジャッジシステムの計測値のぶれによるものでした。参考までに、同じコードを2回提出したら片方が2051msでTLEが出て、もう片方が1859msでACできたことを確認しました。そのタイミングで後置ifに変更しACできた経験から、間違った知識がインプットがされていたみたいです。お騒がせして申し訳ないと共に、指摘していただき本当にありがとうございました…！

４．グラフなどで配列を使わない（重要度★★☆☆☆）

グラフや優先度付きキューなどで配列を使わないようにすると処理速度が速くなります。たとえば頂点数2のグラフにおいて、「頂点1から頂点2まで距離5である」というのを

N = 2
graph = Array.new(N+1){Array.new}
graph[1] << [2,5]

と記述するところを、mod(N)空間を用いることで配列を使わずに

N = 2
graph = Array.new(N+1){Array.new}
graph[1] << 2+5*N

と記述できます。これを取り出すためには

graph[1].each do |v|
    to = v%N  # => 行き先
    distance = v/N  # => 距離
end

とすればいいです。頂点数が多い場合や、距離にマイナスが入る場合は変換作業を工夫する必要があります。ですが、基本的に頂点数が(10⁶)以上になることは無いので、変換した値が大きすぎて処理速度が落ちることもそうそう起こりません。Rubyの多倍長整数であるというメリットをふんだんに使っていきましょう。（可読性がどうしても下がるのは仕方がないと割り切りましょう。。。）

これを用いたACコード（他にも様々な定数倍高速化を用いています）
Submission #22908498 - ZONe Energy Programming Contest

(ZONeエナジープロコン - E問題(Sneaking))

５．文字の比較を数値で行う（重要度★☆☆☆☆）

最終手段です。これを使わないとACできなかった問題は今のところ１つだけです。とはいえかなり実行時間が早くなったので、最終手段として知っておくといいかも。例えばグリッド問題では、マス目に行き止まりなら「#」、通れるなら「.」のように入力が与えられがちです。これを、文字コードの数値として管理し、数値同士の比較を行います。例えば「#」の文字コードは35で、「.」の文字コードは46です。壁が行き止まりかどうかみるなら

grid[i][j] == 35

通れるかどうかなら

grid[i][j] == 46

のようにすることで、処理速度が速くなります。余談ですが上記のコードは

gridi = grid[i]
gridi[j] == 46

とすることでより速く処理できます(２の二次元配列参照のテクニック)
文字を文字コードに変換するのはord関数やbytes関数でできます。覚えておくといつか使うときが来るかもしれません。

これを用いたACコード（他にも様々な定数倍高速化を用いています）
Submission #19542530 - KEYENCE Programming Contest 2021

(キーエンスプロコン2021 - C問題(Robot on Grid))

６．bit演算を使う（重要度★★☆☆☆）

bit演算に代替できるものはそうした方が早いです。例えば

#2のべき乗
2.pow(n)  #こっちよりも
1<<n  #こっちの方が早い

#偶奇判定
n%2 == 1  #こっちよりも
n&1 == 1  #こっちの方が早い

この２つは結構使います。偶奇判定の方は可読性と引き換えに処理がとても速くなります。

演算回数	107
pow	1260[ms]
シフト演算	1061[ms]

演算回数	107
n%2	555[ms]
n&1	464[ms]

７．配列の複製は最小限にする（重要度★★☆☆☆）

配列やハッシュを複製し、元の配列を参照しないように値の更新をしたいときはdupというメソッドが使えます。

arr = [2,3,5,7]
tmp = arr.dup
tmp[0] = 1
p tmp[0]  # => 1  コピー先の値は変わるが
p arr[0]  # => 2　コピー元の値は変わらない

これはとても便利なメソッドである反面、計算量が配列の大きさ分かかります。厳密には「配列を参照し、値の更新が行われるときに初めて配列の複製をO(N)かけて行う」らしいです。

Array#dupは、レシーバと返り値の配列が内部で同じ配列をシェアするのでO(1)で動き、どちらかの要素が破壊的に変更されるタイミングで別のものとして複製を作る。RubyのCopy on Write。

— ユニ (@universato) 2021年5月30日

※ユニさん。Rubyの言語仕様まわりでいつもお世話になっています……！

ということでむやみにdupを多用するのはやめましょう。定数倍高速化とは若干異なりますが、先日のABC(ABC203-E - White Pawn)で引っかかったポイントとなったので紹介しました。改めて考えるとコピーサイズ分の計算量かかるの当たり前なんだよな……。

またこの話とは別に、二次元配列に対して雑にdupを使うと痛い目に合うので丁寧に1行ずつdupしていきましょう(1敗)。

※雑に解説すると二次元配列に対するdupは参照が残り複製ではなくなる。

まとめ

以上、Rubyにおける定数倍高速化手法についてでした。あらためて見返すとRubyならではの高速化手法はそんなに無かったかも。

まとめとしては、１と２と３さえ意識できていればだいたいの問題は通せると思います。特にWhileは書きづらいですが、シンプルに処理が速くなるので慣れるためにも積極的に使うといいでしょう。（可読性は大きく落ちるので競プロ以外での仕様は微妙かも。）

ここに紹介したもの以外にも「枝刈り全探索」や「賢いダイクストラ」など、アルゴリズムレベルでの定数倍高速化手法もあるので調べてみるといいです。言語関係なく実践できるので記事も充実しておりオススメです。学びも多いです。

最後に

僕は定数倍高速化を学んでから、通せるようになった問題の幅が広がったという実感があります。それまで(4*10⁶)くらいの計算量が限界だと思っていたのが、だいたい(10⁷)までの計算量の問題が通せるようになりました。大きな成長です。大嫌いだった二次元グリッド問題も苦手意識がかなり無くなりました。

ですが、どうしても言語的な限度はあります。

例えばABC187-FやABC189-Cは、想定解法ではどうしてもRubyでACできません。

例えば典型テクニックである半分全列挙は、少し工夫して実装しないとTLEになります。

例えば巡回セールスマン問題は、頂点数18でも上手く実装しないと実行時間ギリギリになります。

こういうのは「仕方ない」と割り切る必要があります。

今のところ水色difficulty以下の問題は全て解きましたが、RubyでACできなかった問題はありませんでした。これから青を埋めていくところですが、RubyでのAC者が一人もいない計算量厳しめの問題が出始めます。不安ですが、どこまでRubyでいけるのか挑戦してみようと思います。

スクリプト言語である以上、速度はどうしても早い言語に負けてしまいます。それ以上に、スクリプト言語であることのメリットを有効活用できればいいと思います。

例えば間違えなく早解きでは有利です。

例えばRuby以上に書いてて楽しい言語は無いです(これは個人差あり)。

同じスクリプト言語であるPythonのメリットは「教材の多さである」と言う人がいます。その通りですが、これはRubyでも十分達成可能だと思っているので、負けじと質の良い記事をたくさん発信していきたいです。

いろいろな高速化を紹介しましたが、それでもRubyで解けない時、残念ですがそのときは別言語を使わざるを得ないでしょう。移行先としてはC++、Rustあたりかな？Pythonへの移行はあまりオススメしません(Python自体はRubyより遅いです。PyPyは早いらしいですが、それでもTLEに悩まされている報告を見ます)。

また、ほぼほぼRubyのコードのまま実行できるコンパイル言語Crystalがあり、これはとてもオススメです。配列の型宣言が厳密になったくらいで、コードが基本そのままで速度が10倍とかになります。僕は、どうしても困ったときにはCrystalを使っています。ただし、ユーザーの少なさ・教材の少なさがデメリットになります。

この記事で一人でもTLEに苦しむ人が減ればいいなぁ。 あともっとRuby広まれ

- 参考にした記事 : Ruby競プロTips(基本・罠・高速化108 2.7x2.7)
Rubyに関するTipsがすべて詰まっています。文量は多いですが、具体的な計測値も出しつつ定数倍高速化手法やその他Tipsについてまとまっています。Ruby使いは必見です。

Rubyで競プロをするときに覚えておくと嬉しい機能

Rubyで競プロをする際に、知っていると地味に嬉しい機能をまとめてみました。

最近自分以外が書いたRubyのコードを見る頻度が増えたのですが、「ここはこう書いたらお得なのになぁ」と思う事がたまにあります。Rubyはすべてがオブジェクトであり、用意されているメソッドも豊富に思えます。自分がまだまだ知らないようなメソッドも多いことでしょう。

そこで、自分がRubyで競プロをする際に「これは便利だ」と思う割に、知らない人もいそうなものを羅列していきます。（掲載基準は自分がその機能を知ったときに特にびっくりしたものですｗ）思いつき次第追加していきます。

ModPow(累乗の剰余)

競プロでよくある「1000000007で割ったあまりを求める」問題で頻出な累乗の剰余ですが、自分で関数を定義して効率よく乗算をするプログラムを書いている人を見かけます。 Rubyだとこれが言語機能として標準で使えます。

MOD = 10**9+7
2.pow("とても大きい数",MOD) 
# => 2の累乗。pow関数の第二引数にMODを渡せる

剰余を計算してくれるだけでなく、高速な累乗の計算もしてくれるのでめちゃくちゃ便利です。

bsearch(二分探索)

Rubyには二分探索を行うためのメソッドbsearch, bsearch_indexがあります。「左側と右側を管理しながらwhileで差が１になるまで回して…」といった二分探索を簡単に実装できます。数値の範囲Rangeに対して実行することもできるし、ソートされたArrayオブジェクトに対しても同様に使えます。

(0..10**12).bsearch{|v| v >= 500}
# => 500が返される

(0..10**12).bsearch{|v| v >= -500}
# => 0が返される

(0..10**12).bsearch{|v| v >= 10**15}
# => nilが返される

[2,3,5,7,11].bsearch{|v| v > 5}
# => 7が返される(条件を満たす中で一番左の配列の値)

[2,3,5,7,11].bsearch_index{|v| v > 5}
# => 3が返される(条件を満たす中で一番左の配列のインデックス)

複雑な条件であってもブロック内で簡単に記述できますが、ブロックには返り値(boolean)が必要なことに注意です(左側がfalse、右側がtrue)。

nil || 数値

何かしらの処理をした後で変数にnilが代入されてしまい困るケースがあります。例えば上述した二分探索では、指定範囲内に満たすものが一つもない場合nilが返されます。多くのケースで一番右側の壁となっている数値が代入できれば嬉しいですが、これは論理演算子||を使うことで簡単に処理できます。

[2,3,5,7,11].bsearch{|v| v > 15} || 16
# => 16が返される(二分探索部分での返り値がnilなので、代わりに16が返される)

またこれとは別に、ある変数がnilの場合のみ右辺の値を代入する||=という記法も存在します。

x = nil
y = 5
x ||= 10
y ||= 15
p x  #=> 10
p y  # => 5

より厳密に、論理演算子||は「左から順に評価し真となる値を返す」という処理を行います。が、競プロにおいて||を同一の式で2つ以上使うことはあまりないと思います。

x = nil || false || 3 || true
p x  # => 3

GCD(最大公約数),LCM(最小公倍数)

Rubyにはユークリッドの互除法を用いたGCDおよびLCMを求めるメソッドが標準で用意されています。

12.gcd(16)  # => 4が返される
4.lcm(6)  #=> 12が返される

ただし、ユークリッドの互除法の考え方自体は競プロにおいて問われることがあるので、これらを地力で実装できる知識は付けたほうがいいでしょう。また、3つ以上のGCDやLCMを求めたいときは、injectまたはreduceメソッドを使うといいです。

(※2/23追記：simanmanさんから情報いただきました、ありがとうございます！)

# 1～10のLCMを求める
(1..10).inject(:lcm)

#12,16,18のGCDを求める
[12,16,18].inject(:gcd)

出力周り(putsでの改行、joinを用いた出力)

putsとArray(簡単に1行ずつ出力する)

putsの引数にArrayオブジェクトを渡すと、要素がひとつずつ改行された状態で出力されます。使えるかどうかは出力形式次第ですが、何かと使いやすいので積極的に使いましょう。

ans = [2,3,5,7,11,13]
puts ans  # => 配列の要素が一つずつ改行して出力される
puts ans[3..5]  #=> 配列の特定範囲の出力も簡単

join(一列に並べる)

たまにある出力形式で「答えの配列を一行に、要素同士をスペース入れる」ものがあります。そんな時に便利なのがjoinメソッドです。joinメソッドは「配列の要素の間に、joinの引数で指定された文字列を挿入した文字列オブジェクト」を返してくれます。つまりarray.join(" ")のようにスペースを引数に取ることで、一列にスペースで区切られて並んだ配列を出力することができます。

ans = [2,3,5,7,11,13]
puts ans.join(" ")
# => 2 3 5 7 11 13　が出力される

定数倍高速化

Whileでループを早くする(お手軽な定数倍高速化)

Rubyのブロックは遅いです。つまり、ブロックを使わずにループを回すと実行時間が早くなります。具体的には、forやtimesではなくwhileを使いましょう。

#遅い
n = 10000000
cnt = 0
n.times do |i|
  cnt += i
end

#早い
n = 10000000
cnt = 0
i = 0
while i < n
  cnt += i
  i += 1
end

これは完全に経験則なのですが、Rubyでの競プロ(Atcoder)において計算量10⁶を越したらwhileを使ったほうがいいです。びっくりするぐらい実行時間が変わるので、実行時間に困ったときはとりあえずコード内のループをできるだけwhileに変えるといいと思います。よくある制約N=2000で想定解法O(N²)の問題では特に有効です。

長い文字列の入力

文字列の長さが大きい場合、文字列の一部分の参照(一文字ずつ取り出すなど)はとても実行時間が遅くなります。文字列の長さが100を超す場合は、一文字ずつ配列に格納した方がいいです。 (※2/23追記：simanmanさんからcharsメソッドの情報いただきました、ありがとうございます！)

input = gets.chomp.split("") 
# splitメソッドで文字列をひとつずつ分解し、配列に格納する

input = gets.chomp.chars
# 上と同じ処理。こっちのほうが簡潔で分かりやすい

これはgrid問題なんかでも使えます。「1行ずつ文字列オブジェクトとして取り出す」のではなく、「2次元配列として文字をひとつずつ格納する」方が取り扱い的にも速度的にも安心です。

結び

他にもRubyにおける細かいテクニックはたくさんあるので、思いつき次第追加していきます。（間違ったことがあったらコメントで指摘していただければ嬉しいです＞＜）

最後に、参考にしたサイトのリンクを貼って結びとします。こちらも素晴らしい記事なのでぜひ見てみてください！

• Ruby競プロTips(基本・罠・高速化108 2.7x2.7)
  • Rubyで競プロをする時に役立つ機能や仕様の総まとめです。文量は多いですが、Rubyで競プロをしている人なら絶対最後まで見るべきです！
• 【Ruby】使いこなせると便利。||演算子のいろんな使い方 - Qiita
  • 本記事でも紹介した論理演算子について、とても分かりやすく書かれています！

RubyでAtcoder水色になりました！

競技プログラミング(Atcoder)を始めておおよそ半年、ARC108で入水することができました！！

入水しました！！！めちゃ嬉しい！！！

konayukiさんのAtCoder Regular Contest 108での成績：712位
パフォーマンス：1651相当
レーティング：1167→1229 (+62) :)
Highestを更新し、4 級になりました！#AtCoder #ARC108 https://t.co/GEeAgUxMic pic.twitter.com/jF2MwsQyHd

— こなななななな (@kona0001) 2020年11月21日

内容も速解きでレートを稼いだとかじゃなく、本番AC最高difを更新しての色変だったから嬉しいです。水色は当初から目標にしていた第一の壁だったので、そこを突破できて安心してます。

せっかくの機会なので慣れない文章ですが色変記事というものを書いてみようかなと思います。他の競プロerと違うのは自分がRubyしか使わないということなので、そこを中心に記事を書いていきます。

■ プロフィール

まず簡潔にプロフィールでも。

自分は早稲田の大学院の博士課程にいて、セキュリティとHCIを組み合わせたような研究をしています。

元々競技プログラミングには興味が無かったのですが、弊大学の講義「アルゴリズムとデータ構造」のTAをしてからアルゴリズムの面白さを知り、競技プログラミングにも興味を持ち始めました。この講義の先生が大変面白い方で、細かいエピソードは省きますがお陰様でアルゴリズムとデータ構造を心の底から面白いと思うことができました。ちなみにこの講義で使用した言語がRubyで、先生曰く「アルゴリズムを学ぶうえで一番簡潔にコードが記述できる言語」と仰っていました。これが今年の1月くらいの話になります。自分がRubyを使い始めたきっかけでもあります。

■ 精進のスタイル

まず自分のスタイルとして「徹底的に下埋めをしてパフォの下限値を上げる」事を意識しています。水色になったときの状況がこちら

実は3カ月くらい競プロに触れてない期間がありました

精進グラフ

ここ最近の頑張りがいい感じですね。基本的に実力と離れすぎてる問題は挑戦しないようにしていました。緑difが埋まってないくらいだとそもそも知らない知識や典型があるだろうなってことで、下から埋めれば知識も見落としなく身につくだろうって考えです。

というのも、ABC174とABC178で簡単めな問題が解けず大爆死したのがあまりにも悔しくて、知らない知識があった事をめちゃくちゃ後悔したのがきっかけです。今でもRepseptとUbiquityって単語を見ると寒気がします。

C - Repsept

悪夢その１　パフォ721

C - Ubiquity

悪夢その２　パフォ613

おかげさまで、緑difを全部解いたあたりからどれだけ爆死してもパフォが1100程度でとどまるようになりました。下埋め最大のメリットだと思います。茶difの初めてみるような難しい問題であっても、緑difを全部解く力があればゴリ押せるように感じます（ABC184 - C - Super Ryuma みたいな）。

もちろん水dif以上にまだまだ知らない知識やテクニックを要する問題がたくさんあるので、本番でぶち当たると手も足も出ないことが多いです。これは長い目を見て、下埋めしながら確実に解ける問題を増やせればいいなぁって思ってます。

大爆死からの反省

■ 身に着けた知識

水色になるにあたって身に着けた知識を羅列してみます。とはいえ色変記事には有り余るほど同じようなことが書かれているので、大事だと思ったもののみ書いていきます。

- 水になるのに必須だと思ったもの

• 計算量の見積もり力
• 全探索
• bit全探索
• 剰余の逆元
• 高速な組み合わせ計算
• modの巡回性質
• べき乗の高速計算
• 包除原理
• 式変形
• 高速な素数判定
• エラトステネスの篩
• gcd、lcmの理論
• 累積和
• imos法
• 貪欲法
• 尺取り法
• 幅優先探索
• ダイクストラ法
• メモ化再帰
• 区間スケジューリング
• Unionfind
• ヒープ

- 言うて入水する時点では使わないと思ったもの

• DP　（難しい問題で出る事多いから解けなくてもそんな問題ない）
• 二分探索　（緑dif以下で二分探索する問題、意外と出ない）
• 深さ優先探索　（幅優先で十分）
• SegmentTree　（このレベル帯では過剰）

ぶっちゃけ、下埋めして緑全部埋めたくらいになると上に挙げた知識は全部身に付くのであえて挙げる必要もなかった気がします。この中でも特に「全探索」と「累積和」と「幅優先探索」と「Unionfind」は使う頻度が高かった気がしたので、時間が無い方はこの辺を優先して学習するといいかも。

◆ Rubyで競プロをするということ

RubyやPythonなどのスクリプト言語は実行速度が遅いため競プロにおいて不利、とよく言われます。これはまさにその通りだと思います。これまでに出場したコンテストで感じた不利な部分を羅列してみます。

■ 計算量の許容がc++とかと比較して2桁少ない

Rubyだと10^6くらいの計算量から実行時間が怪しくなります。10^7となるとほぼ不可能です。一方でc++だと10^8くらいまでの計算量は通せるようで、ずるいと思うことがしばしばあります。

例えば DNA Sequence (ARC104 - B) では想定解法が計算量2.5×10^7であり、RubyだとACできません（もちろん別の簡単な解法もあり、それだとACできる）。また Coprime (ABC177 - E) ではc++でなんと10^9解法が通るみたいです。

こういうのを見るとかなり不遇を感じてしまいますが、Rubyを使う以上覚悟はするべきです。言語選択を含めての競技であり、Rubyを選んでレートが下がったのであればそれは言語のせいではなく使う人が原因です。

もちろん後にも書きますが、Rubyを使うメリットもあるのでそことのトレードオフだと思っています。（一番理想なのはメリットデメリットを把握した上で言語を使い分けることだけど、学習リソースが大きそうなので後回しにしてます...><）

まあぶっちゃけその問題が解ければ他の言語が気になることも無くなるし、絶対にACできない訳じゃないから、自分の実力を上げるのが手っ取り早いよねってスタンスです。

■２次元グリッド問題が通らない

これが一番デメリットとして大きいです。Rubyを使う以上覚悟しろとは言いましたがこれだけはなんとかして欲しいです。２次元グリッド問題はその名の通り、２次元のマス目上で何か操作をしていく問題です。その制約がだいたい

　1 <= H,W <= 2000

なのですが、これだと想定解法であっても最低計算量(4.0×10^6)で、愚直に処理をすると基本TLEになります。本番に通すとなると、ありとあらゆる定数倍高速をする必要が出てきます。

直近で苦しんだ問題でこれだけあります。

・Picking Goods (ABC175 - E)

・Wizard in Maze (ABC176 - D)

・Lamps (HHKB2020 - E)　←これだけは未だにTLEで解けない

・Queen on Grid (ABC183 - E)

・Third Avenue (ABC184 - E)

幸い２次元グリッドで実行時間が間に合わないような問題は全部水dif以上なので、今のところそんなに支障は無いです。とはいえ青を目指すとなると、この類の問題が設置されるだけでかなり厳しくなると思ってます。

この対処としては２つ考えてて、

・定数高速倍手法を完璧に身につけて本番で頑張ってACする

・飛ばして次の問題を解く

前者は圧倒的に難易度が高いと思ってるので、青を目指す段階ではさっさと飛ばして次の問題を解くつもりです。それはE問題が解けなくともF問題が解ければ青パフォを出せる見込みがあるから。

僕は最近のコンテストでは2000×2000のグリッド問題はすぐに飛ばして１つ先の問題に取り掛かっています。結果はまだ残念ながら振るっていないけど、F問題が解けるようになれば一気にパフォも伸びると思っています。ABC183ではE問題を即飛ばしてF問題が解ける寸前までいけたので、このスタイルが上手くはまればレートも伸びるでしょう。

黄色を目指すとなると話は変わってきて、ABCであれば全完しないといけなくなるから定数高速倍とも付き合う必要が出てきそう。サイアクNoSub戦略も取らなきゃいけなくなるのかなぁ。ここらの話は青になってからまた深く考えていきます。

（オマケ）

・Akari ( ABC182 - E )
とても優しい、神のような２次元グリッド問題。制約が若干ゆるめなうえに実行時間制限も気持ち長い。作問者だいすき。ありがとう。

■ 人口が少ない。参考にできるコードが少ない。情報が少ない。

これも地味に大きなデメリット。Rubyで競プロをする人の数が少ないだけならまだいいのですが、圧倒的に強い人がいないのが困ります。

例えば難しい問題がわからない時に、すでに提出されているコードを参考にすることがあると思います。Rubyの場合、ACしているコードが少なかったり、そもそも１つも無いことがよくあります。ブログ記事で解説を上げている人も全然いないので、結構自力で頑張る必要があります。

Ruby用のテンプレートを上げてくださる方はいるので(ac-library-rb)、そこはかなり嬉しいところです。

github.com

自分はテンプレートや関数は必要になったら都度ゼロから実装してストックしています。そのおかげで、データ構造やアルゴリズムに対する理解は同レベル帯の人よりは優れている自信があります。このテンプレートもいつか紹介したいですね。

ところで、Rubyで競プロをする人のコミュニティって存在するのでしょうか？仮にあるのであればすごく気になるし、コミットしたいですね。自分は割と最近競プロを始めた勢なので、そのへんの情報が分からんとです。

ということで不器用なりに自分もRubyに特化した解説記事と、情報発信諸々をしようかなーって考えてます。声がないだけでRubyに特化した競プロ記事は需要がある気がしているので。まだまだ実力的には遠いけど、競プロでrubyといえばkonaみたいな定着はさせたいですw　ある意味人口少ないから狙えるのかな、これ笑

■ Rubyを使うメリット

散々Rubyを使う上でのデメリットを述べましたが、もちろん強みもあります。思いつくがままに書き連ねてみます。

・コード記述量が圧倒的に少ない

動的型付け言語だから記述量が圧倒的に少ないし、厳密に型を考えなくてよくなる。オーバーフローもしないし、アルゴリズム部分に集中してコードが書けるようになる。

・記述量が少ないから早解きに向いてる
ヒューリスティックコンでもない限り早く提出すればするほど順位も上がります。その点Rubyはめちゃくちゃ有利だと思います。なんとなくの推測ですが、c++で書くよりも半分以上記述量が減る気がします。

実際に早解きでレートあげたコンテストがこれ

日立コン2020　なんとこれでパフォ1577

ただし、最近のコンテストだと低難易度帯にいわゆる「崖」となる問題が少なくなっているので、早解きで得られるレートが減っている気がします。少し前までは灰dif問題を解くだけで青パフォが出かけたりしたものですが、いまやそんなコンテストは滅多にありません。つまり、実力で1つ上の問題を解かない限りパフォが出づらくなってしまいました。最近のAtcoderのコンテスト難易度調整力は素晴らしいですね。

なので、Rubyのメリットのひとつである「早解き力」は最近実感することはほぼありません（とはいえパフォ100-200くらいは盛れてるのかな？）。

・純粋なオブジェクト志向言語による直感的なコード
Rubyは全てがオブジェクトなので、操作が容易だし直感的。最近気に入っているのが、幅優先探索をする際にキューが空かどうか判断するのに

　queue.empty?.!

とする記法。否定のために変数の頭にカーソル持ってくの何気に面倒かったから、この記法を知ってからめちゃくちゃ使ってます。見た目はだいぶ気持ち悪いけどね。ArrayやHashに対する操作もどんどんメソッドで重ねられるからそういうのも好き。

・言語に組み込まれた豊富なメソッド
外部ライブラリを使う必要が全くない。そこそこ最近知ってびっくりしたのが、gcdとlcmが言語に組み込まれていたこと。

　6.gcd(4)　=> 2
　3.lcm(5)　=> 15

みたいな。他の言語の事詳しいわけじゃないけど、Rubyにはこういうのが多い気がします。ついでにオブジェクト志向っぽさが全力で出ててそこも好きw　あと正規表現が言語に組み込まれてるのもすごくいい。最近はあまり使う機会ないけど、言語仕様のレベルでパターンマッチできるのはかなり魅力的だなって思います。

・書いてて楽しい
結局はここに落ち着く気がするw　Rubyってなんだか書いててすごく楽しいんですよね。きれいにコードに落とせるっていうか、違和感ある表記がないっていうか……言語化しづらいけどこれはRuby使ってる人なら全員共感してくれると思っています。

あとこれは余談ですが、Rubyのelsif記法に慣れてからPythonのelif記法が気持ち悪くてたまらなくなりました。ブロック前のコロン:も気持ち悪い。要するにRubyに慣れすぎちゃったって話です。逆の話もよく聞くので(Python使いの人がRubyのelsifやendを気持ち悪がる)、結局は使い手の好みや慣れの問題ですね。

■ これからの話

無事に水色になれたということで、次の目標も掲げます。正直自分がすんなり水色になれたのは、青色になる事を目標に精進してきたから、というのが大きな理由だったと思います。水色を目指して精進してたら、多分いけて緑後半くらいとか直前でグダリまくったような気がします。

同じ理由で次は黄色を目指そうと思います。黄色コーダーになるためには何が必要か？新しい知識？経験？コンテスト参加回数？今の自分レベルで言えることは、とにかくひたすら精進するしかないってことかな。今のところまだまだ成長の余地があると感じてるから、何か大きな壁にぶち当たるまでは問題を下から解きまくろうと思います。直近のコンテスト(ABC184)でも知らなかった知識を使う問題が出たし（確率DPと半分全列挙）、身につけるべき物はまだまだたくさん出てくるでしょう。

■ 締め

青にいけるのがいつになるか分からないけど（もしかしたら一生来ないのかもしれないし）、引き続き精進していこうと思います。当面は緑に落ちないように、願わくばレートをあげられるように頑張りたいです。あとこれからはちらほらRuby×競プロの記事も書いていきたいです。

無事に青コーダーになれますように。。。