ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

スクリプト言語などで競プロをすることについて

スクリプト言語」と呼ばれるRubyPythonなどの言語に代表される、比較的実行速度の遅い言語で競技プログラミング(特にAtCoder)をすることについて。

最近色々ともやもやすることが多いので、思っていることを書きます。まさにこれらの言語を使っている方々、これらの言語を使うことについて何か物申したがる方々、そしてコンテストを運営されている方々それぞれに向けて。

長いです。興味があれば読んでください。

私の立場

私は競技プログラミングを始めた当初はRubyを使っていました。AtCoder青まではRubyのみで問題を解いていました。

その後、徐々に速度面での限界を感じてC++への移行をしました。現在はratedコンテストでは(多倍長整数を使いたいなどの)特別な理由がない限りはC++を使っています。

現在AtCoder橙ですが、もし仮にRubyだけを使い続けていたとしたら橙にはなれていない(もしくは、もう数年かかっている)と思っています。

スクリプト言語での競技プログラミングについて

実際に使っている方は十分身に沁みていると思いますが、問題によっては想定解法を実装してもTLEが出てしまい通せないことがあります。これは確かな事実です。

もちろんスクリプト言語の中でもその速度差はあり、私の体感ではPython(いわゆる普通のPython)よりはRubyのほうが多少速いように思います。一方でPythonにはPyPyという高速な実装があり、これはRubyより遥かに高速です。競技プログラミングでもよく活用されています。

なので一概には言えませんが、私がRubyで問題を解いていた頃は、AtCoderのratedコンテストの点数で

  • 400点以下の問題は素直な実装でほぼ通る
  • 500~600点には、定数倍高速化を考慮しない実装では通りにくいものが存在する
  • 700点以上では、体感でおよそ半分ほどの問題は通すために(可読性を損なうレベルの)定数倍高速化が必要か、またはそれでも通らない

という印象です。ただこれはあくまで体感であり、コンテスト開催側が「○○点問題は○○言語でACできることを保証します」と宣言しているわけではありません。

ただしこれは私がRubyで問題を解いていたおよそ1年前の頃の話で、直近のコンテストでは300~400点でもスクリプト言語に厳しい問題が出題される頻度が上がっているように思います。AC者がいることから分かるように、定数倍高速化をすれば通るレベルのものではあります。

A - Darker and Darker

D - Lamp

そのため以前私は「青までならスクリプト言語で問題なく到達できる」と主張していましたが、この傾向が今後も続くようであればRubyで到達できるかは少し怪しいかもしれません。

やはり現在のAtCoderではC++に次いでPythonの利用者が多く(参考)、PythonユーザであればPyPyという強力な武器を使うことができます。AtCoderのコンテスト運営に携わっているとある方が「PyPyなら通ります」ということをよく言われていますし、やはり「PyPyで通る」が1つの基準になっているのかなと想像します。そのぶん他のスクリプト言語利用者には厳しい状況になっていくかもしれません。

また実際に問題をACできないこと以外に、「遅い言語で競プロをすることについてTwitter等で人々が物申す現象が定期的に発生する」というのも、実情としてはつらい点です。「物申す」という表現は失礼かもしれませんが、すみません、あえて書きました。私の受けている印象をそのまま書くとこういう表現になってしまいます。

問題をACしたいなら速い言語を使うべきという主張は「正論」です。ド正論です。正論だからこそ言いたくなってしまうのかもしれませんね。ただし、少なくとも私は「そんなことは百も承知でRubyを使っていた」わけで、分かりきった「べき」論を言及されることに正直良い気はしません。同じような思いのスクリプト言語使いも多いのではないでしょうか。特に最近はユーザが多く目立つからなのかもしれませんが、やたらPythonユーザに対する言及が多いように思います。

スクリプト言語利用者の方へ

先述した通り、問題面でも環境面でも今後より厳しい状況になっていく可能性があります。私は自身の経験もありこれらの言語で競技プログラミングをする人を応援したいと思っていますが、この状況を変えることはとても難しいと思っています。

まずお願いしたいのは、「通せない問題があることを受け入れる」ということです。もっと言うと「特定の言語で通せない問題を出題するコンテストに非がある」ということは決して無いし、「全ての言語でACを取れるようにコンテストを構成すべき」という主張は良くないものだと理解してほしいです。コンテスト運営側としても、想定解法が通らないことはなるべく避けたいと思っているでしょう。しかし実際問題としてこれを本質的に改善することは非常に困難です。

その上で、「可能な限りハンデを緩和するテクニックを身に付ける」ようにしましょう。同じような処理に見えても、書き方1つで大きく実行時間は変わるものです。これは同じ言語を使っていて、競プロ歴が長い人やレートの高い人を頼るのが一番です。

Pythonであればこちらの記事が非常に有用です。

Python 競技プログラミング高速化tips (PythonでAtcoderをやる際に個人的に気を付けてること) - じゅっぴーダイアリー

Rubyについては私が記事を書いていますが、あまり高速化技法に触れられていない点は申し訳ないです…

Rubyで競プロするときのTips - ARMERIA

そして、より高いレートを目指すのであれば「いずれは他の言語に移行する必要がある」ことを頭の片隅に入れておいてください。これも言語ごとの事情や今後の出題傾向に大きく依存しますが、目安としては「青になったらそろそろ」という感じです。言語の移行は簡単に出来ることではないですが、出来る限り道を用意していけたらと思っています。

そうではない方々へ

スクリプト言語を使っているのはあなたと同じ競プロerであり人間です。そのことを忘れないでください。

…と言うのも変な話ですが、こう言いたくなるくらい現状はつらいと思っています。わざと過激なことを言いたがるような一部の人は別としても、それに限らずこの話題は「正論の言及」をしたがる人が多いようです。

私の知る限り、スクリプト言語である程度の期間競プロをやっている人のほとんどは言語のデメリットを受け入れた上で競プロをしています。自分でも理解している正論をことあるごとに投げつけられるとつらい…ということは、この話題に限らず多くの人は経験があるのではないでしょうか。

そうではない人への言及、特に「通せない問題があることについてコンテスト運営に文句を言う人」への批判も見られます。確かにそのような人も中にはいるでしょうし、それは違うと私も思います。ただ得てしてこのような言及は攻撃的になりやすく、連鎖的に言及範囲が広くなり先述の「正論の言及」が発生しがちです。つらいです。

たかがTwitter、それなりの節度を持って好きなことを書けば良いと思います。ここで書いたことを辞めてくれと強制することもしないしできません。ただ、その言語を使っている当事者たちはそれを見てどう感じているのか、よかったら一度考えてみてください。私はつらいです。

コンテストを運営されている方々へ

言語間の速度差に関する問題は運営の方も頭を悩ませていると思います。よく言われるような、言語ごとの実行時間制限や制約の大幅な緩和をしてしまってはコンテスト全体の公平性を維持できない、という論は私も全く正しいと思います。

本音を言えば、先程書いた「400点以下の問題はRubyPythonの素直な実装でほぼ通る」状態はなるべく維持するように問題選択をしてくれたら嬉しい、とは思っています。AtCoder(特にBeginner Contest)の運営思想として、いわゆる「アスリート」指向の競技者に限らず広く参加者を集めたい、という思いがあるのであれば尚更です。ただ通ることを「保証する」ことはとても手間がかかると思うので、あくまで問題選択の指針として、です。

また、運営の方も我々参加者もTwitterがかなりの情報共有場になっているので、Twitterで頻繁に話題になっていると十分周知されていると勘違いしがちですが、実際にはそうでない参加者の方が多くいると思います。「全言語でACできることは保証していない」などの記述がAtCoderのサイトでちゃんと分かるようになっていると良いと思います。例えば非公式コンテストのs8pcではトップページにそのような記載がありますが、これと似たような記載が公式ratedにあってもいいのかなと。

あと例えばCodeforcesのDiv.3コンテストだと、時間制限が厳しい問題の問題文には「この問題では、Python利用者はPyPyを使うことを推奨します」という注意書きがあったりします。AtCoderもBeginner Contestであればそのような注意書きを入れるのも一案なのかな、と思っています。

文句を言われることは運営の方にとっても本意でないと思いますが、それらの文句は「悪意」ではなく「無知」によるものではないかと考えています。これらがより広く・公式に周知されるよう、今後改善されていくことを期待します。

おわり

同じ趣味を持つ人同士で、同じように問題を解いて、知識を共有して、レートを競い合って、なのに何故「遅い言語」の話題になるとこうなってしまうんだろう。この状況が少しでも変わるきっかけになればいいなと思い、この記事を書きました。

読んでくださってありがとうございました。