AtCoderで緑色になったので振り返りつつ数理科学系大学院生に趣味としてオススメする

はじめに

f:id:ekotto32:20200520092440p:plain

先日のAtCoder Beginner Contest(ABC)168で今年の目標にしていたランク緑色まで到達しました!AtCoder界隈では、色変記事といって、ランクが上がったときに自分が何をしたか振り返り記事を書くようで、多数の良記事があります。私も書こうと思ったのですがせっかくなので振り返りをしつつ、私のもう一つのコミュニティであるポスドク・大学院生に「AtCoder・競技プログラミングは院生の趣味の選択肢として結構アリだと思う」という記事を書きます。

私自身、AtCoderを本格的に始めたのは5ヶ月前でもう既にポスドクをやっていましたが、大学院生時代からやっておけば(サービスをそもそも知らなかったのですが、AtCoder自体は2012年あたりからあるようです)よかったなあと思ったので、この記事を書きました。

 

そもそもAtCoderとは?(競プロ勢は読み飛ばしてください)

AtCoderは競技プログラミングのオンラインコンテスト開催サイト名であり、そのサービス(AtCoder jobsのように就職支援も含まれます!!)を提供している会社の名前です。コンテスト参加は無料です。必要なのはPCと電気代と通信費だけです。PCも高いスペックは必要ないです。

コンテストは(典型的なABCと呼ばれるものだと)100分間の間に問題A-Fの6問出題され、解いた問題に応じて得られる点数の合計およびその速さを競うものです。問題文があって、それにそった入力を受け取り、答えを出力するプログラムを書いて、提出すると、20ケースほどのテスト入力にたいして正しく出力されているかチェックされ、全てのテストに正しい答えを出した場合問題クリアとなります。同じ点数を取ったユーザー間では最後の問題を解いた時間+間違えたプログラム提出数に応じたペナルティ時間で順位がつけられます。

atcoder.jp

規程時間終了後、順位に応じて「パフォーマンス」という数値が計算され、今までのコンテストのパフォーマンスに応じて「レーティング」という数字が決まります。レーティングに応じて複数の色(段位みたいなもの)に分かれていて、下から灰色、茶色、緑色、水色、青色、黄色、橙色、赤色...となっています。ランクに応じてどんなスキルが身に付くのか、詳細については、下のAtCoder社長さんのブログが良いと思いますので、ご参考ください。

chokudai.hatenablog.com

AtCoderは日本のサイトなのですが、同様の海外サイトで著名なものにCodeforces、Topcoderなどがあげられます。他のサイトのコンテストに出ていないので詳細な言及は避けますが、問題文が英語である、開催時刻が日本時間の夜中になる可能性がある、コンテストのルールや開催頻度が異なるなどの違いがあるようです。ちなみにAtCoderの人気はうなぎのぼりのようで、最近のコンテストには海外からの参加者も含め、10000人以上が参加しているとのことです。

良い成績を残すには、もちろんプログラミング能力(アルゴリズムや計算にかかる時間を考える、バグらずにコードを書く)も問われますが、所謂一般的な数学の知識(高校数学~大学基礎科目くらい?)も問われる場合があります。例えば前回は時計の針(分針、時針)の間の距離を求める際に、三角関数の知識を用いる問題がありました。もちろん高校で習う知識なので大半の参加者(中学生とか若い参加者もいらっしゃいます)は最低でも三角関数を「知っている」状態ではありますが、「いつも使っているのでパッと解法が浮かんでくる」とスピードの面で有利です。数理科学系の大学院生だと、こういったところにアドバンテージがあるかと思います!

atcoder.jp

もちろん、数理的な能力・プログラミング能力だけではなくて、解法を思いつく発想力や、典型例を応用する能力、また、よりメタな能力として新しいことを学ぶ力が鍛えられるかと思います。競技という側面はありますが、自分との戦いという面が強く、コミュニティの中でいろいろと解説を出してくれている競技者の方がたくさんいらっしゃいますし、ランクが上がった場合(Twitter等で報告すれば)皆に祝福されます。コツコツとやっていってランクが上がったときの楽しさはあつ森を超えます(当社比)!!

個人的には学んだことが直接役に立たなくてもいいかなと思っていますが(趣味なので)、実際には「あー大学院生時代にこれ知っておけば〇〇のコードもっと速くなったかもなあ」といった件も存在しました。一個人の考えですが、研究は思い通りに進まないものなので、大学院生時代には「研究と違ってやったらある程度進捗があって気分転換になるもの」を趣味とするのはより良い大学院生活を送る一つの方法だと思います。競プロは(もし、自分に合っているなあ、と思うのであれば)ストレスをそこまで貯めずにかつ「趣味だけど、ある程度実用性もある」くらいのポジションでいてくれるので悪くない選択かと思います。

もちろん、同じ数理科学系の大学院生の中にも多種多様な人がいて、素養があって楽に上に行ける人もそうでない人もいるのは重々承知しています。個人に必要な努力の質や量は目標にも応じて変化します。無理のない範囲でやってみる、くらいのスタンスがお勧めです。

と、いうわけで勧誘はこのくらいにして自分の開始当時の様子や緑色に上がるまでやったことをつらつらと書いていきます。 

 

自己紹介(AtCoderはじめる前はどんなだったか)

AtCoderを始める前の自分を思い返してみると、

研究で必要だったので、独学でC++をやっていた(授業等で、体系的に学んだ経験がないので、知識がちぐはぐ)

物理をやっていたので、高校-大学基礎くらいの数学は馴染みがある。最大公約数・最大公倍数がなんたるかはわかっているし、三角関数もわかる。整数問題も(わかるというと語弊があるのですが)苦手ではない。Nが素数であるか判定するのにはSqrt(N)に比例した時間でわかる、というのがわかる。「グラフ」というのが界隈では図を意味するのではなく、辺と頂点によるアレだと認識している。(AtCoderは整数やグラフに関連した問題が多い。最初から知っている必要はないけど苦手意識がない方が楽しくできる。)

標準入出力はできる。四則演算+商の余りを求められる。if, for文は書ける。配列というものを知っている。STL(C++についてる標準ライブラリ)はvector(可変長配列)ぐらいしかしらない。文字列の編集はあまり知らない、substr()は知っている程度。文字から数値、数値から文字への変換もググらないと思い出せない。

計算量という概念は知っている。ランダウの記法(O(n)とか)も物理で似たような議論があるので知っている。実際に計算量を気をつけてプログラミングした経験は指折り数える程度。

(余談ですが計算量という概念について、以下の記事が面白かったです。実務でも大事な時がある。)

qiita.com

再帰という概念は知っているけど、実装したことはない。累積和、幅優先探索(bfs)、深さ優先探索(dfs)、動的計画法(DP)についても言葉を知らなかった。貪欲法という言葉は知らなかったけど、こういった素直なアルゴリズムは自分で時間をかければなんとなく実装できるくらいの感じ。しゃくとり法、いもす法、ダイクストラ法などは今でもあんまりできない。Unifon Find木やセグメント木もできない。

タッチタイピングがあまりできない。速くないし、ミスも多い!(NとMを打ち間違えていることに気づかず、ペナルティでパフォーマンスを約10%損したことがあります)(でも、典型的なコードを先に作っておいて、コピペして最小限を手打ちにすることである程度カバーできます。)

個人の傾向として、簡単な問題を人より速く解くのは得意。難しい問題をじっくり考えるのが苦手。

といった感じだったと思います。いくつかの専門用語が出てきてこれからAtCoderをはじめようかと気になっている方はギョッとするかもしれませんが、5ヶ月前の私もDPとかセグ木とか聞いたこともありませんでした。焦らず少しずつ学んでいければ良いので、あまり過剰に身構える必要はないかと思います。

 

AtCoderを始めた頃~茶色まで

昨年の夏くらいに何も知らずにAGC(AtCoder Grand Contest、難しい方のコンテスト)に出て、一回挫折しかけましたが、年末からコツコツABCをやり始めました。Ratedコンテストに出た回数はそこから数えると緑色になるまで18回です。最初のコンテストは37分3完+4ペナ(×5分)=57分で、茶色のパフォーマンスだったようです(この回のC問題は比較的素直な問題で、運がよかったです)。

手元で環境構築はしていなくて、AtCoderコンテストサイトのコードテストページに打ち込んでやっています。キルリングとか補完が使えないので、本当は手元で環境を整えてやる方が良いと思います...ただ、プログラミング始めた頃に私が嫌だったのが環境構築なので、そういった意味では本当に初心者でも気にせずに始めることができるのが良いところです。

その後7-8回かけて茶色まで行きました。AtCoderは参加コンテスト数が少ないうちはレーティングが低めに出る補正がかけられているので、最初のうちはあまりレーティングは気にせずに個々のコンテストの結果(=パフォーマンス)を気にしていました。また、どうしてもコンテスト形式の慣れは必要です。もちろんプログラミングの中身も大事ですし、自分の実力を伸ばすことがまず大事ですが、落ち着いた回答を心がけたりミスをしない仕組みづくりをするなど、総合力でコンテストで良い結果を出すようにしていました。といっても最初は全然ダメで、例えば(もう二度とやらないと誓っていますが)開始20分後から参加して(同じ問題を解いた場合速さで決まるので)順位が大きく下がってレートを下げてしまったこともありますし、コードテスト(後述)をしないまま提出してしょうもないミスをしたことも多々あります。

コンテストを解く際に気をつけていたこととして、コードの内毎回書く部分は予めどこかにストックしておいて、コピペしていました。極力タイプミスをなくすためです。また、典型的な〇〇というアルゴリズムを使えば良いとわかったが実装したことがない際に他人のコードをコピーして問題に合うように修正したりしていました。コードの中身を一行づつ理解できていれば問題ないかと思います。AtCoderの一つの問題に対して書くコードは(我々のようなレベルの問題では)そんなに長くないので、新しい概念でもその場で動くプログラムを組む状態まで持っていくことは可能だと思います。

めんどくさいんでA問題とかスルーしたくなりますが、コーナーケース(業界用語で入力な極端な場合という意味だと思います)で間違った答えを出したり、先述のしょうもないミスをしたりするので、コードテスト(問題に含まれている入力例に対して出力例を正しく返答できるかチェック)しておくのは大事だと思います。戦略として「AB問題早とき!Cはどうせ解けない!」といったことを行う場合にはもしかしたら数秒を争うのでコードテストの時間を端折りたくなりますし、わたしもそうだったのでわかります。ただ、ペナルティが5分なのでそこが大きすぎることを考えると、きちんとテストして提出する方が良いと思っています。

コンテストが終わった後の復習として解説pdfを読むのはオススメです。もちろん時間をかけて解説動画をみた方がきっと良いのですが、そこは解説を読んでもわからなかったら、という形か、あるいは数日後にググって他の方の記事を読んでみるというのも良いかとも思います。基本的にB問題まで解けたらC問題、C問題まで解けたらD問題だけ復習しました。自分がギリギリ解けなかった問題だけ復習して、それ以上の問題は(コンテスト中にCが解けなくて時間をかけてDを考えたけどやっぱダメだった、みたいな場合にC,D両方解説読んだことはありますが)基本的には時間を割く必要はあんまりないかと思います。

いわゆる精進と界隈で言われますが。そういった過去のA問題全埋めやB問題全埋めは行ませんでした。全部解いていたら時間の割りに(それなりにわかっている問題も多いので)得るものは少ないかなと思っていました。ただこれも工夫次第で、多様な問題に触れることを念頭に、各問題をチラッと見て、実装したことないような解法があれば練習がてらやってみる、というのをやっても良かったかなと反省しています。

茶色になるころには、文字列の操作について昔より詳しくなりましたし、mapやvectorなどのC++のSTLを簡単な場合ならスッと実装できるようになりました。「昔の研究の〇〇の場面でこれ知ってたらもっと楽に□□できたかも」と思ったりしたので、茶色になるだけでも(研究で簡単なプログラミングをする場合は)ちょっと役に立つ場合があるかもしれません。

 

茶色から緑色になるまで

Atcoder Problemsというサイトがあって、茶色になるまえから知っていましたが、茶色になったあたりから活用するようになりました。何日連続でAC(Accepted, 正解すること)したか表示される機能があって、これを目安に一日一問解くようにしていました。解く問題の難易度はその日によってマチマチで、時間があるときには自分がギリギリ解けるくらいの問題や、ググって解法を調べないと解けないくらいの問題を解きましたが、時間がないときには簡単に解法を思いつく問題をとりあえず解いていたりしました。「毎日15分くらいでいいのでコツコツ問題に触れる」というのは実力アップにとても重要だと思います。

https://kenkoooo.com/atcoder/#/table/

私の現状の埋まり具合下記のようになっていて、あんまり精進が足りてないのがわかるかと思います。

f:id:ekotto32:20200524052216p:plain

また、chromeの拡張等をつかっていくつかAtCoderサイトの表示をカスタマイズしました。本来であれば茶色になるまえからやっておけば良かったです。

 

greasyfork.org

greasyfork.org

greasyfork.org

どれも好きですが、上二つはコンテスト中により詳細な情報が目に入るので、もしかしたら使いたくない人もいるかもしれません。

茶色になったころ(少し前だったかも?)、それまでAtCoderを始めるまでの貯金でやっていた自分がもうちょっとできるようになりたいと思って、勉強したのが累積和でした。実際Webで検索すると多くの人の解説記事があります。私はいろんな記事でトライして(自分に合った記事を見つけたというよりは、単純にその記事を読んだときにモチベーションが最も高かっただけかもしれませんが)とある記事である程度実装までできるようになりました。記事を読む→コピペでもいいから実装する→見ずになんとなく実装にトライしてみる→ダメだった場合、実装のどこかで論理を理解していないのでそこをやり直す、といったステップを踏んだように記憶しています。早速勉強したそのあとすぐか、あるいはその次のコンテストで累積和を使う問題が出たような記憶があります。

茶色になってからもう少ししてできるようになったことで一番本質であったと現在思っているのが、全探索です。もともと、情報系やコーディング畑ではないので、どちらかというと長いコードをしっかり書いて探索するよりは発想でうまく計算の楽をすることを念頭に置く、きれいに問題を解きたいタイプでした(「ハンマーを持つと問題が全部釘にみえる」に通ずるところもあります)。しかし、全探索で間に合うのにそうやってしまうのは競技プログラミングの基本からはちょっと外れてしまうのかな、と思うようになり、問題をみるとまず全探索できるか、というのを検討するようになりました。本質的な技術というよりは意識の問題が大きかったと思いますが、最初はこれが本当にできていなくて、AtCoderに慣れてきて茶色になれた頃から少しづつ意識的に問題をみるようになりました。全探索できるかという点においては計算量という概念が必要で、元々計算量についてはなんとなく知識がありましたが、解説記事等一通り眺めて勉強しなおしました。問題をみてしっかりコードを書けば時間内に全探索できるケースだ、ということが判断できるようになったのがレートを上げるためには一番大きかったと思います。

その他のアルゴリズムについて話しておくと、私のやったことの中にDP,DFS,BFSがあります。動的計画法(DP)については、茶色になった後累積和を学び終えたころにQiita等を参考にして簡単な問題について実装してみました。複数の解説記事があがっているので、各々が合う記事をみつけてやってみるのをお勧めします。深さ優先探索(DFS)、幅優先探索(BFS)についても同様です。DPをやってこちらに移るのが理解がより容易になるかと思います。もちろん実装できたり手法自体を理解したりすることも大事ですが、問題をみて「「最短経路」と問題にあるし、BFSかも?」とか「全通り試すにはDFSが使えそうだな」といったように、どういう場合にこの解法に落ち着くのか、といった判断を行えることがまず大事だと思います。

ダイクストラ法や、しゃくとり法など、典型的なアルゴリズムは他にも何個かありますが、私はまだできていません。緑色になるために全てを知っている必要はないですし、同じ緑の人でもきっとできることはそれぞれ違っているかと思います。コンテストにたくさんでそうなものから覚えた方が、自分のレーティングが上がる機会もそれだけ増えるのでアプローチの一つかと思います。あるいは、自分がとっつきやすいものから取り組んでいくのもモチベーションを保つ上で一つの手かもしれません。緑色の次の水色になるには典型的な解法・アルゴリズムのほとんどをある程度こなせる必要があると思っていて、それが緑色から水色にあがることが特に難しいと(個人的に)思っていることの一つです。

 

まとめ&これから

というわけで、AtCoderと自分の今までの取り組みについて簡単に紹介してきました。個人差はありますが、緑色までは自分の得意なことだけ(私で言えば簡単な問題の早解き+少数の典型アルゴリズムの習得)である程度進めると思います。もちろん、大学院生の中にも多種多様な方がいらっしゃるので一概に言えませんが、特に数理系の方で競技プログラミングの面白さに目覚めるかたは一定数いると思います。研究に役立つこともありますがかといって近すぎもせず、私個人としては息抜きとして良い選択肢でありつつ、楽しんで学び続けられたと思っています。あまり目線を高くせずに、まずは茶色や緑色を目指して気軽に無理のない範囲で時間のある週末に参加してみることをお勧めします!

ただ、個人的に趣味としては「楽しい」「負担にならない」などが重要だと思っています。もちろんどんどんレベルが高いところを狙う段階になってくると逆に苦しくなることもあるので、個人の判断で適度にやめるのも良いかと思います。

私個人としては、もちろんうまくいかなかった時の苦しさはなかったといえば嘘になるのですが、目標を達成したときの面白さを感じたので、これからも頑張って次の水色を目指したいと思います。とはいってもここからは一段と厳しいのは重々承知しているので、焦らず半年くらいかけてコツコツとやっていきたいと思います。データ分析コンペであるKaggleに出てみたいという目標もあるので、そちらと折り合いを付けつつ、うまく時間を割り振っていけたらいいなと思います。

思えば今まで二回ほどABCDを素早く解いて水色パフォーマンスを出しましたが、E問題を時間内に解いたことはないので、Dまで落ち着いて素早く解けるようになりつつ、時々Eを解けるようになりたいなと思っています。DP,DFS,BFSといった典型アルゴリズムについて、まだしっかり自分のものにした感覚はないので、関連した問題を解いて精進していきます。

参考文献

学習する上でお世話になったもので、上記以外の物をお礼も込めてリストアップしておきます。

qiita.com

qiita.com

上記二つは最初に読んでみるとイメージがわくかもしれません。

 

qiita.com

この記事は「便利ツール」の欄でお世話になりました。

 

下記はいろいろな解法を調べるときにお世話になっています。

drken1215.hatenablog.com


qiita.com

 

qiita.com

 

最後に色変記事について、すべてが自分にとって正解とは限られませんが、atcoder 〇〇色と検索するとその色になった人等の記事がたくさんヒットすると思います。また、単純に中身関係なく他のプレイヤーの成功をみるとモチベーションアップにもなると思います。

AtCoderで茶色から緑色に上がるには何を勉強すればよいか - テストステ論

AtCoderで緑色になりました - Qiita

 

こういったメタな情報を集めやすくなって皆の実力が上がっていて、とある色になるまでの実力がどんどん上がっていっている?という話もあるようです。事実かどうかはわかりませんが。良いことも悪いことも含んだ話かもしれませんが、何か考えるとっかかりがあることは初心者にとってはありがたいことだと思いますし、私自身他の方の解説記事がなければ緑色に来られなかったでしょう。自分の力で情報を集めて、自分の糧にできる人が伸びて行きやすいのかもしれません。