RubyでAtcoder水色になりました！
競技プログラミング(Atcoder)を始めておおよそ半年、ARC108で入水することができました！！
入水しました！！！めちゃ嬉しい！！！
— こなななななな (@kona0001) 2020年11月21日
konayukiさんのAtCoder Regular Contest 108での成績：712位
パフォーマンス：1651相当
レーティング：1167→1229 (+62) :)
Highestを更新し、4 級になりました！#AtCoder #ARC108 https://t.co/GEeAgUxMic pic.twitter.com/jF2MwsQyHd
内容も速解きでレートを稼いだとかじゃなく、本番AC最高difを更新しての色変だったから嬉しいです。水色は当初から目標にしていた第一の壁だったので、そこを突破できて安心してます。
せっかくの機会なので慣れない文章ですが色変記事というものを書いてみようかなと思います。他の競プロerと違うのは自分がRubyしか使わないということなので、そこを中心に記事を書いていきます。
■ プロフィール
まず簡潔にプロフィールでも。
自分は早稲田の大学院の博士課程にいて、セキュリティとHCIを組み合わせたような研究をしています。
元々競技プログラミングには興味が無かったのですが、弊大学の講義「アルゴリズムとデータ構造」のTAをしてからアルゴリズムの面白さを知り、競技プログラミングにも興味を持ち始めました。この講義の先生が大変面白い方で、細かいエピソードは省きますがお陰様でアルゴリズムとデータ構造を心の底から面白いと思うことができました。ちなみにこの講義で使用した言語がRubyで、先生曰く「アルゴリズムを学ぶうえで一番簡潔にコードが記述できる言語」と仰っていました。これが今年の1月くらいの話になります。自分がRubyを使い始めたきっかけでもあります。
■ 精進のスタイル
まず自分のスタイルとして「徹底的に下埋めをしてパフォの下限値を上げる」事を意識しています。水色になったときの状況がこちら
精進グラフ
ここ最近の頑張りがいい感じですね。基本的に実力と離れすぎてる問題は挑戦しないようにしていました。緑difが埋まってないくらいだとそもそも知らない知識や典型があるだろうなってことで、下から埋めれば知識も見落としなく身につくだろうって考えです。
というのも、ABC174とABC178で簡単めな問題が解けず大爆死したのがあまりにも悔しくて、知らない知識があった事をめちゃくちゃ後悔したのがきっかけです。今でもRepseptとUbiquityって単語を見ると寒気がします。
おかげさまで、緑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になります。本番に通すとなると、ありとあらゆる定数倍高速をする必要が出てきます。
直近で苦しんだ問題でこれだけあります。
・Lamps (HHKB2020 - E) ←これだけは未だにTLEで解けない
幸い２次元グリッドで実行時間が間に合わないような問題は全部水dif以上なので、今のところそんなに支障は無いです。とはいえ青を目指すとなると、この類の問題が設置されるだけでかなり厳しくなると思ってます。
この対処としては２つ考えてて、
・定数高速倍手法を完璧に身につけて本番で頑張ってACする
・飛ばして次の問題を解く
前者は圧倒的に難易度が高いと思ってるので、青を目指す段階ではさっさと飛ばして次の問題を解くつもりです。それはE問題が解けなくともF問題が解ければ青パフォを出せる見込みがあるから。
僕は最近のコンテストでは2000×2000のグリッド問題はすぐに飛ばして１つ先の問題に取り掛かっています。結果はまだ残念ながら振るっていないけど、F問題が解けるようになれば一気にパフォも伸びると思っています。ABC183ではE問題を即飛ばしてF問題が解ける寸前までいけたので、このスタイルが上手くはまればレートも伸びるでしょう。
黄色を目指すとなると話は変わってきて、ABCであれば全完しないといけなくなるから定数高速倍とも付き合う必要が出てきそう。サイアクNoSub戦略も取らなきゃいけなくなるのかなぁ。ここらの話は青になってからまた深く考えていきます。
（オマケ）
・Akari ( ABC182 - E )
とても優しい、神のような２次元グリッド問題。制約が若干ゆるめなうえに実行時間制限も気持ち長い。作問者だいすき。ありがとう。
■ 人口が少ない。参考にできるコードが少ない。情報が少ない。
これも地味に大きなデメリット。Rubyで競プロをする人の数が少ないだけならまだいいのですが、圧倒的に強い人がいないのが困ります。
例えば難しい問題がわからない時に、すでに提出されているコードを参考にすることがあると思います。Rubyの場合、ACしているコードが少なかったり、そもそも１つも無いことがよくあります。ブログ記事で解説を上げている人も全然いないので、結構自力で頑張る必要があります。
Ruby用のテンプレートを上げてくださる方はいるので(ac-library-rb)、そこはかなり嬉しいところです。
自分はテンプレートや関数は必要になったら都度ゼロから実装してストックしています。そのおかげで、データ構造やアルゴリズムに対する理解は同レベル帯の人よりは優れている自信があります。このテンプレートもいつか紹介したいですね。
ところで、Rubyで競プロをする人のコミュニティって存在するのでしょうか？仮にあるのであればすごく気になるし、コミットしたいですね。自分は割と最近競プロを始めた勢なので、そのへんの情報が分からんとです。
ということで不器用なりに自分もRubyに特化した解説記事と、情報発信諸々をしようかなーって考えてます。声がないだけでRubyに特化した競プロ記事は需要がある気がしているので。まだまだ実力的には遠いけど、競プロでrubyといえばkonaみたいな定着はさせたいですw ある意味人口少ないから狙えるのかな、これ笑
■ Rubyを使うメリット
散々Rubyを使う上でのデメリットを述べましたが、もちろん強みもあります。思いつくがままに書き連ねてみます。
・コード記述量が圧倒的に少ない
動的型付け言語だから記述量が圧倒的に少ないし、厳密に型を考えなくてよくなる。オーバーフローもしないし、アルゴリズム部分に集中してコードが書けるようになる。
・記述量が少ないから早解きに向いてる
ヒューリスティックコンでもない限り早く提出すればするほど順位も上がります。その点Rubyはめちゃくちゃ有利だと思います。なんとなくの推測ですが、c++で書くよりも半分以上記述量が減る気がします。
実際に早解きでレートあげたコンテストがこれ
ただし、最近のコンテストだと低難易度帯にいわゆる「崖」となる問題が少なくなっているので、早解きで得られるレートが減っている気がします。少し前までは灰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×競プロの記事も書いていきたいです。
無事に青コーダーになれますように。。。
