中年プログラマの競プロ事始
これはなに
自分がここ2年ほど趣味として競技プログラミングをやった経緯と感想です。いわゆるプログラマの定年と呼ばれる35歳を過ぎてから始めたのですが、思ったよりも楽しめました。自分のようなシニアと呼ばれるプログラマが競プロに興味を持ってくれたらいいなと思って書きました。
競技プログラミング（競プロ）とは
競技プログラミング（以後、競プロ）は、プログラミングをして順位を競うコンテストです。コンテストはたいていオンラインで毎週のように開かれており、誰でも参加できます。形式としては、与えられた時間内にいくつかの問題を解くコードを提出して、その正解数と提出までにかかった時間を競うというものです。たいていは、コードの実行時間および使用メモリに制限があり、その制限内で実行できるコードを書く必要があります。またコードが正解かどうかは出題者が用意したテストケースをパスするかどうかで判定されます。
多くのコンテストでは結果に応じて参加者のレーティングが変化し、参加者はレーティングを上げるために鎬を削る、という構図になっています。
始めた経緯と2年の振り返り
2年ほどまえに外資系の会社に転職しようとして始めました。その会社は面接対策用のドキュメントをリクルータが共有してくれるのですが、その中にコーディング面接の対策としてTopcoderのEasyの問題をウォームアップとして解くとよい、とありました。
Topcoderは海外の競プロコンテストですが、その過去問は誰でも見れます。ただ、自分は何を勘違いしたか、レーティングを上げてDiv. 1と呼ばれる上位のコンテストに参加できるようにならないとDiv. 1の過去問は見れないと思いこんでしまい、とりあえずレーティングを上げようと参加しました。
結果的にはその面接はうまくいかなかったのですが、競プロのおもしろさに気付き、また将来コーディング面接の対策にもなるかなと思って始めた次第です。
競プロを始めようと思い立って、まず選ばなければならないのがどのコンテストに参加するかです。Topcoderをそのままやってもよかったのですが、サイトが分かりにくいこと、開催時刻が日本時間に優しくないことにためらいがありました。
定期的にコンテストを開催しているサイトでは次のものがありましたが、この中ではAtCoderが日本時間に優しく、また素人目での判断ですが、いい問題が多いように思ったので、AtCoderに参加することに決めました。問題文が日本語かつ短めなので、とっつきやすそうに見えたというのもあります。
ほかにもGoogle Code JamやICFPCのように年に1回開催されるもの、1週間などの長期間かけてヒューリスティクスな問題を解くいわゆるマラソン形式のコンテストなどもあります。
さて、AtCoderに参加することに決めたわけですが、最初はAtCoder Beginner Contest（ABC）とAtCoder Regular Contest（ARC）の違いも分かっておらず、初めて参加したコンテストがARCで4問中1問しか解けなくて自分はこんなにできないのかと落ち込みました1。
コンテストの違いが分かってからはABCに狙いを定め、最低月に1度は参加するという目標を立ててコンテストに参加しました。ABCは初級者向けのコンテストで現在はAからFまで6問の問題がほぼ難易度順に並んでいます。プログラマになって10年ほど働いたシニアな方だったら、おそらく問題AとBはすぐに解けて、問題Cはなんとか解けるくらい、Dは時間内だと厳しい、という感じではないでしょうか。
自分も当初はそのような感じでしたが、過去問を解いて勉強しているうちに、半年ほどで問題Dはすこし考えたら解けるようになり、そのあたりで水色レート（1200）に、最終的に2年かけて青レート（1600）に到達しました。2年間のレーティングの推移はつぎのようになります2。
自分の勉強法ですが、まず蟻本と呼ばれる『プロラミングコンテストチャレンジブック』を買い、初級編まで読みました。出てくるアルゴリズムは自分で実装して、自分用のライブラリを作っておくといいと思います。
あとはAtCoder Problemsというサイトを利用してひたすら過去問を解いて、解けない問題は解説を読むということの繰り返しです。なお、AtCoder Problemsはたいへんお世話になりました。過去のコンテスト問題一覧だけでなく、難易度で問題を絞ることもできるので便利です。他にも何日連続でAC（正解を提出することです）したかを表示してくれるStreakという機能があるので励みになります。
![プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～](https://m.media-amazon.com/images/I/41oruV+aJIL._SL160_.jpg "プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～")
自分の場合は最初の壁がABCの問題Dだったので、最初は毎朝ABCの問題Dを1問解くことを目標にしました。数時間かけても解けないということはザラで、そういうときは解けるまで数日かけたりもしていました。ちまたの競プロの勉強法を見ると、簡単な問題をとにかく大量に解くことや、20分かけて解けなかったら解説を見ろ、というものが多いですが、自分はむかしから1つの問題を長い時間をかけて解くのが好きなので、効率は無視してそういう方法をとっていました。このあたりは向き不向き、好き嫌いが分かれるところだと思います。趣味なので、好きな勉強法でたのしく続けるのがよいでしょう。
問題Dがあっさり解けるようになってからは、問題EやF、あるいはそれと同程度の難易度の過去問を解いていました。また、蟻本の中級編を読み進めました。
それに加えて、解いた問題の解法や学んだ知識や証明をScrapboxにまとめていました。これは自分の考えを整理するうえでもとてもよかったですし、ときには記事を書いている最中に自分の証明に穴があることに気付いたりもしました。もしよければこういう記事を書いてみることをおすすめします。
他には制限時間内に解く練習をするためにAtCoder Problemsのバーチャルコンテストも利用しました。これは誰でも過去問をいくつか組み合わせてコンテストを作れる機能なのですが、有志によって「あさかつ」という名前のコンテスト（7/26はこれ）が毎朝開かれています。どうも制限時間内に解くのが苦手だと思ったので、時間内に解く練習にこのコンテストにしばらく参加していました。すでに知っている問題が出ることもありましたが、分かっている解法をさっとコードに落としこむ訓練になりました。
競プロをやってよかったこと
箇条書きに書いてみます。
- 問題を考えることがたのしい
- ちょうどよい暇つぶしになる
- 容赦なく現実を突き付けられる
1. 問題を考えることがたのしい
そのまんまですが、自分は競プロのたのしさの大部分は問題を考察すること、解くことのたのしさだと思います。
これは自分の中のぼんやりしたイメージなのですが、自分が問題を解くときはこんなふうです。まず、問題というのはじっと見つめていても解けることはありません。手当たり次第に解法を試すのも（すくなくとも自分は）うまくいきません。そのかわり、シンプルな入力についてどうなるか手で確かめる、2次元の問題だったら1次元の場合を考えてみる、制約を外す、あるいは制約を足す、似た問題に変換できないか考える、問題を分割する、などなどといったことをします。
そのようにさまざまな角度から眺めると徐々に問題の輪郭がわかってきます。それはなにかよく分からない物体の表面を撫でている感じに近いでしょう。ずっと撫でていると次第に輪郭がわかっていき、いくつかの引っかかりが見つかります。そしてその引っかかりをうまく掴むことができれば、問題を理解することができ、そこからおのずと解法も導かれます。
この、引っかかりを掴む感覚がとても気持ちよい。これは数学パズルでも同じですが、問題の芯の部分、背骨をがっしり捉えることが大事で、なんとなく、こういう感じで解けるかなと解法ありきで考えると（すくなくとも自分は）必ず間違えるのがおもしろいところです。
さらに競プロの場合はアルゴリズムに落としこむという点で計算量やメモリの制約が効いてきます。たとえば、問題のサイズが小さいときは単純に3重ループで解ける問題があったとしても、問題のサイズが大きくなると飛躍的に難しくなる。同じ問題でも制約によって解き方がガラリと変わるのは競プロの魅力の1つでしょう。
2. ちょうどよい暇つぶしになる
これは自分だけかもしれませんが、歩いているときや電子レンジを待っているとき、温泉につかっているときに、なにか考えることがほしくなります。たとえば仕事で考えている問題だったり詰将棋でもいいのですが、競プロの問題というのは、問題を覚えることは容易で考えるのに時間がかかるという点で、まさにそのような暇つぶしにうってつけです。
コードを書いて確認するにはコンピュータが必要ですが、考えるだけなら紙とペンがあれば十分なので、たとえば旅行中のちょっとした時間や長距離フライトの機内で考えるのにもよいでしょう。
とある新潟の雪深い温泉で露天風呂につかりながら競プロの問題が解けるまで出ないぞと決心してずっと考えていたことがあるのですが、世界に自分しかいないような感じがしてとてもたのしかったのを覚えています。なお、解けたと思って部屋に戻ってから確認したら全然ダメだったのもいい思い出です。
3. 容赦なく現実を突き付けられる
現実は非情です。コンテストでうまくいかなければ、順位は悪くなりレーティングも下がります。多少の運もありますが、基本的には自分の実力通りの結果しか出ません。
時間が足りなくて焦ることもあります。ABCは100分ですが、6問すべてを解こうとすると、ほぼ寄り道している暇はありません。いつもはすんなり解けるはずの問題Cでつっかかって、そのつっかかったことに焦るということもあります。
これは10年くらいプログラマをやっているとちょっと新鮮です。というのは、それくらい経験を積むと、よくいえば総合力で対応、悪くいえば誤魔化しが効くようになるのです。シンプルに自分の一部の能力を評価されるということは減り、ほかの能力や経験でカバーすることを覚えていきます。これは悪いことではありませんが、ともすると自分ができる方なんじゃないかと錯覚してしまいます。
しかし競プロのコンテストに出ると、競プロという一点において自分よりはるかに出来る人たちを目の当たりにして軽く自信を喪失します。そういった経験を定期的にするということは、シニアな人ほど大事で得難いものであると思います。
コンテストに失敗した夜はとても悔しくて、なぜ解けなかったんだろうと歯噛みする経験も数えきれませんでしたが、それはよい刺激であったと思います。競プロに限らず、ある程度シニアな人はそういう機会を意識的に持つとよいかもしれません。
合わなかったところ
とくに自分にとって競プロが合わないというか、むずかしいなと思うことはつぎのものでした。
- 参加時間帯が厳しい
- 早解きに興味が持てない
1. 参加時間帯が厳しい
ABCは土日どちらかの21:00 - 22:40というスケジュールですが、家庭持ちにとってはやや辛い時間です。外食すると21:00に帰ってくることは難しいですし、家で食べるとしても自分は家人に料理してもらっているので夕食の時間を調整してもらわなければなりません。
このあたりは家族の理解を得て、月に1回程度という頻度だったのもあってなんとかなりましたが、一人暮らしならもっと楽だと思います。
なおCodeforcesのコンテストは23:30に始まることもあるので、夜型の人はそちらが都合いいかもしれません。
2. 早解きに興味が持てない
これは、ほぼ愚痴ですが、自分はあまり早解きは得意ではありません。頭の回転が遅いのは確かなので単純に不得手のようです。自分はどちらかというと1週間でもずっと同じ問題を考えるのが好きで、そのせいか、あまり早解きのテクニックを磨くのに興味を持てませんでした。また、数学的に自分の解法が最適であることを証明しようとして、むやみに時間をかけてしまうこともありました。
これはとくに問題セットが易しめのコンテストではかなり不利です。とはいえ、趣味でやっているものなので、自分はこういうスタイルで楽しもうと割り切って、早解きは諦めて参加していました。
なお、いままで参加したことはほぼないのですが、マラソンコンテストやヒューリティクスコンテストと呼ばれるタイプのコンテストだと、また事情は変わってくるかもしれません。
よくある想定質問と回答
最後に、シニアプログラマから受けそうな競プロについての想定質問とそれに対する自分の回答を載せます。なかには実際に受けたことがある質問も入っていますし、自分が競プロをやる前に抱いていた疑問もあります。
Q. コーディング面接で有利ですか？
端的に言えばYesです。
経緯で、とある外資系の企業のコーディング面接のために始めたと書きましたが、その企業からは1年後にまた受けないかというお誘いを受け、2回目では通りました。この会社はコーディング面接の比重が高く、面接では競プロの知識と技術は有利に働いたと思います。とはいえ、AtCoderのレーティングでいえば、水色くらいあれば十分だと思います。
また、自分は個人的な信条から利用していませんが、コーディング面接に特化した問題を提供しているサービスもあります。競プロをやるよりそっちの方が効率的だといわれたらそうかもしれません。
ただ1つ言えることは、コーディング面接で出そうな問題を片っ端から解いて解法を暗記して、運良く面接に通ったとしても、それはプログラマとしては得るものが少ないだろうということです。
それよりも、問題をどう理解するか、アルゴリズムをどう問題に適用するかといったことを競プロを通して学べれば、コーディング面接に通ること以上の糧になるでしょう。老害っぽい物言いですが、コーディング面接に通ることだけを目標に競プロをやるのはややもったいないと思います。
Q. 業務で役に立ちますか？
直接的に役立つことはそれほど頻繁にはないでしょう。前職では、たまたま競プロの知識が直接役立てられそうなタスクがあったのですが、とてもいい経験になりました。
その経験をまとめた記事：動的計画法によるDVDのディスク分割の改善
とはいえ、こういうタスクが頻繁にあるかというと、仕事にもよりますがふつうはそんなにないでしょう。とくに短時間のコンテストに出てくるような問題はどちらかというと数学パズルに近く、業務で扱う問題とはやや方向性が違うといえます。
ではまったく役に立たないかというと、そんなことはありません。たとえばアルゴリズムをいくら学んでも、それを問題に適用できるかどうかはまた別の話です。競プロをやることによって、そのあたりの嗅覚は鍛えられるように思います。また、頭に浮かんだアルゴリズムをコードに落としこむところも、バグなく実装するにはある程度の慣れが必要です。たとえば二分探索は誰でもアルゴリズムは知っていますが、バグなくシンプルに書くにはちょっとコツがいります。しかし、ほとんどの教科書はアルゴリズムの概要や疑似コードだけ書いて細かい実装の留意点までは書いていません。これも実際に競プロに取り組んで始めてわかったことでした。
競プロと業務の関係は、将棋で例えると詰将棋と実戦の違いのようなものかもしれません。詰将棋だけ強くても実戦が強いとは限りませんが、それでも実戦で間違いなく役立つ能力です。競プロもすぐに役立つわけではありませんが、ある程度やると業務でも「あ、これはこういうアルゴリズムが適用できそう」という問題が見えるようになります。そういうチャンスを得やすくなるという意味でも有用なのではないかと思います。
なお余談ですが業務ではNP困難かどうか見抜くことがたまに求められます。言い換えると、ある問題の最適解を現実的な時間内に得る方法があるか、それともヒューリスティクスに近似解しか得られないのかを判断する必要に迫られることがあります。これは競プロのコンテストではあまり求められないことの1つな気がします3。
個人的には"The Algorithm Design Manual"という本でそのあたりは勉強してとてもためになりました。とてもいい本なので、興味がある人はぜひ読んでみてください。"War Story"という筆者の経験談コラムもおもしろいですし、内容はやや古いですが、とても実際的な内容だと思います。なお日本語訳は評判が悪いので自分は英語版を読みました。また、辞書的に使う本なのでKindleよりは紙版の方が読みやすいかもしれません。
- 作者:Skiena, Steven S S.
- 発売日: 2010/10/13
- メディア: ペーパーバック
Q. 競プロerはコードが汚い？
これはたまに同世代のソフトウェアエンジニアから聞く話です。「競プロをやっていた人はコードが汚いので採用したくない」と言い放っていた同世代のエンジニアも見たことがあります。
とりあえず、自分のコードは汚くないと信じています。そして、まわりに競プロをがっつりやっている同僚がいたことがないので、自分のこの質問に対する答えは「分からない」です。
たとえば競プロのコードでは時間的な制約もあるため i や j などの1文字変数を多用しますし、人によってはメソッド名もかなり適当です。では業務でそういうコードを書くかといったら、そういうことはないでしょうし、そういうコードがあったらレビューで指摘すればよいことです。レビュー上のコミュニケーションに難があるとしたら、それはおそらく競プロとはまた別の問題でしょう。
もう少し本質的な問題として、競プロで書くようなコードが他の人にはぱっと理解できない可能性はあると思います。たとえば、整数 a を b の倍数へ切り下げるのを a / b * b と書いたり、切り上げるのを (a + b - 1) / b * b と書くのは競プロに慣れている人にはぱっと分かるかもしれませんが、慣れていない人には分からないかもしれません。あるいは動的計画法を知らない人にいきなり動的計画法のコードを見せたら、たぶん理解できないと言われるでしょう。
ただ、これも競プロどうこうよりは、どういうコードを「読みやすい」とするかの合意を得る問題でしょう4。競プロに限らず、たとえばReactのようなフレームワークに慣れているかどうか、関数型プログラミングの経験があるかといったそれぞれのバックグラウンドによって「読みやすい」コードは異なります。このあたりのコミュニケーションは経験によって得るものなので、もしかすると競プロだけやってチーム開発をやったことがない人は不得手なのかもしれません。
それでも、できることなら面接官を担当する方は「競プロをやっていた人だから」と色眼鏡で見ないでくれるといいなと思います。それよりも、自身で競プロを経験してよりよい面接の形式や採用基準を考えてみるのはいかがでしょうか。
なお、自分が前職で書いた動的計画法のコードは、コメント以外に解説記事を書いて、できるだけ動的計画法を知らない同僚も理解できるように努力しました。
Q. 家族とくに子供がいてコンテストに参加できないんだけれど？
ちいさい子供がいると、おそらくコンテストに出るのはほぼ不可能だろうと思います。Codeforcesのように日本時間深夜に開催されるコンテストもありますが、120分程度とはいえ、そのあいだは一切邪魔が入らない環境が必要ですし、勉強する時間も取りづらいと思います。
自分は子供を持ったことがないので推測でしかいえませんが、たとえば、子供の面倒をみているときに問題を考えることはできるかもしれませんし、コンテストに参加しなくても、隙間時間で過去問を解いたり本を読んで勉強することはできるかもしれません。
そして機会があればぜひコンテストに参加してみてください。コンテストはコンテストで楽しいものです。
最後に
冒頭にも書きましたが、この記事は自分のようなシニアなプログラマが競プロに興味を持ってくれたらと思って書きました。
自分が学生のころは競プロはまだそれほどメジャーではなく、CS専攻でなかった自分は存在も知りませんでした。一方でいまは競プロがメジャーになったものの、どちらかというと若い人、とくに大学生がもっぱら参加しているイメージです。
しかし、そういったことに気後れせずに参加してみると、シニアはシニアなりにたのしめることに気付けるのではないかと思います。なにより、シニアにとっては就活を気にせずに純粋に競プロを楽しめるというアドバンテージがあります。もし興味をもったらぜひ趣味として始めてみてください。
さて、自分はというと、競プロを2年前に始めるときに「AtCoderで青レートになる」を目標にしたのですが、それを達成したいまはつぎをどうしようかなと考えているところです。ここ数ヶ月はスプラトゥーン2にハマっていてほとんど競プロをやっていなかったのですが、つぎにやるならCodeforcesに参加するか、ヒューリスティクスコンテストに参加しようかと考えています。
