kona0001の日記

Rubyで競プロする人の日記です

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

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

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

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

ModPow(累乗の剰余)

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

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

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

bsearch(二分探索)

Rubyには二分探索を行うためのメソッドbsearch, bsearch_indexがあります。「左側と右側を管理しながらwhileで差が1になるまで回して…」といった二分探索を簡単に実装できます。数値の範囲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)において計算量106を越したらwhileを使ったほうがいいです。びっくりするぐらい実行時間が変わるので、実行時間に困ったときはとりあえずコード内のループをできるだけwhileに変えるといいと思います。よくある制約N=2000で想定解法O(N2)の問題では特に有効です。

長い文字列の入力

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

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

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

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

結び

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

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

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

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

 


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

 

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


■ プロフィール

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

 

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

 

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

 

■ 精進のスタイル

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

f:id:kona0001:20201124152620p:plain

f:id:kona0001:20201124152633p:plain

f:id:kona0001:20201124152649p:plain

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

精進グラフ

f:id:kona0001:20201124152843p:plain

 

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

 

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

 

C - Repsept

f:id:kona0001:20201124153911p:plain

悪夢その1 パフォ721

C - Ubiquity

f:id:kona0001:20201124154003p:plain

悪夢その2 パフォ613

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

 

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

 

f:id:kona0001:20201124155751p:plain

大爆死からの反省

 

■ 身に着けた知識

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


- 水になるのに必須だと思ったもの
  • 計算量の見積もり力
  • 全探索
  • bit全探索
  • 剰余の逆元
  • 高速な組み合わせ計算
  • modの巡回性質
  • べき乗の高速計算
  • 包除原理
  • 式変形
  • 高速な素数判定
  • エラトステネスの篩
  • gcd、lcmの理論
  • 累積和
  • imos法
  • 貪欲法
  • 尺取り法
  • 幅優先探索
  • ダイクストラ
  • メモ化再帰
  • 区間スケジューリング
  • Unionfind
  • ヒープ
- 言うて入水する時点では使わないと思ったもの
  • DP (難しい問題で出る事多いから解けなくてもそんな問題ない)
  • 二分探索 (緑dif以下で二分探索する問題、意外と出ない)
  • 深さ優先探索 (幅優先で十分)
  • SegmentTree (このレベル帯では過剰)


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

 

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

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

 

■ 計算量の許容が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できない訳じゃないから、自分の実力を上げるのが手っ取り早いよねってスタンスです。

 

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

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

 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)

 

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

 

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

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

飛ばして次の問題を解く

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

 

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

 

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

 

(オマケ)

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


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

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

 

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

 

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

github.com


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

 

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

 

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

 

Rubyを使うメリット

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

 

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

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

 

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

 

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

f:id:kona0001:20201124163047p:plain

日立コン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×競プロの記事も書いていきたいです。

 

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