RubyでAtcoder青入りしました！
青入り
先日のARC133で初めて黄パフォを出すことができ、念願の青入りを果たすことができました！！
初黄パフォでついに青入り！！！やったー！！！！！
— こな (@kona0001) 2022年1月22日
konayukiさんのAtCoder Regular Contest 133での成績：339位
パフォーマンス：2072相当
レーティング：1571→1632 (+61) :)
Highestを更新し、2 級になりました！#AtCoder #ARC133 https://t.co/HMCNwzAb96 pic.twitter.com/P2mp1gLPcA
入水してからおおよそ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(セグ木)
- フロー(最大流)
- 典型アルゴリズム
- グラフ編
- 数列編
- 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で競技プログラミングをしている人はかなり少ないです。
調べてみると圧倒的な差でびっくりしました。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
