はじめに
ＦＦＲＩセキュリティ セキュリティエンジニアの大野です。本記事ではセキュリティからは離れて、AtCoder に関する感想を書きます。 AtCoder に参加し始めてから約 2 年半経過した 2021 年 6 月に目標としていた水色に到達出来たので、それまでの感想となります。
以下が現在(2021/07/20 現在)の私のレートです。レートや色のレベル感については、AtCoder 社の社長によるブログを参考にしてください。
そもそも私が参加したきっかけは、学生時代のゼミで競技プログラミングの本に関する輪講でした。 また水色を目標としたのは、Paiza のスキルチェックを解いたり AtCoder の過去問を見たりした結果、「水色なら半年くらいで到達できるでしょ」という軽い気持ちでした。
AtCoder とは
AtCoder とは、競技プログラミングのコンテストを運営している会社で、毎週土曜日、もしくは日曜日にコンテストを開催しています。 また、 AtCoder 社が開催するコンテンストそのものを指して AtCoder と呼ぶ場合があります。この記事内で「AtCoder に参加」といった場合はこちらを指します。 コンテストの種類には、AtCoder Beginner Contest(通称、ABC)や、AtCoder Regular Contest(通称、ARC)などがあります。そして、それぞれ出題される問題の難易度が異なります。 AtCoder のコンテストでは、開始時間になったら参加者全員が一斉に問題を解き始め、制限時間内にどれだけ問題を多く、早く解けるのかを競います。
コンテスト中に AC (Accepted：正答) できた問題の数と時刻に応じて、レートが増減します。 参加者のレートは大体 0 ~ 4000 の範囲に収まり、レート 2799 までは 400 毎に色が割り当てられる仕組みとなっています。そしてレート 0~399 は灰色、レート 400~799 は茶色、レート 800~1199 は緑色、という風に色が分けられています。
詳細は AtCoder のホームページを確認してください。
参加前のスペック
- 修士 2 年生(情報系の大学院)。
- 研究はアルゴリズム関連。
- 基本的なデータ構造(配列、リスト、木構造など)やアルゴリズム(二分探索、しゃくとり法(two pointers technique)、幅優先探索など)については既に授業などで知っていた。
- 高校数学については特に得意でもなく、組み合わせなどの基本的なことは覚えていたが、細かいことは忘れていた。
- Paiza のスキルチェックでは Python で S ランクを取っていた。
灰色、茶色時代
この時は参加するだけでレートが上がっていたので、モチベーションも高くコンテストは毎週楽しかったです。 実力的には、ABC117 の D 問題がコンテスト中にギリギリ提出できる、という感じでした。 コンテスト終了後、ギリギリ解けなかった問題については解説を読んで提出(通称、解説 AC)していましたが、特に進んで新しいアルゴリズムの勉強などはしていませんでした。
また、アルゴリズムは関係ないのですが、私は AtCoder のコンテスト参加と同時に Rust を使い始めたので、Rust の文法について慣れながら参加していました。 Rust を使い始めたばかりの時、コンテスト中に文字列を標準入力で受け取る方法や空白で区切られた文字列の処理方法がわからず、途中で Python に切り替えたことを今でも覚えています。
緑色時代
コンテスト 5 回参加で緑色に到達しました。この時まで前述した通り「水色くらいなら半年で到達するだろう」と甘く考えていましたが、これは自分の実力を見誤っており、大きな勘違いでした。 実際はここからが大変で、緑色から水色に到達するまで約 2 年 4 ヶ月かかりました。SNS を見る限り、これはかなり時間がかかっている方でした。 数学やアルゴリズムが得意な参加者は、数ヶ月で水色まで到達しているようだったので、モチベーションを保つのが大変でした。
2019 年 4 月ごろ、レート停滞の気配を感じたので、コンテストに出てきたアルゴリズム(ダイクストラ法、Union Find など)を勉強し始めました。 ただし、この時期も普段から問題を解いたりはしていませんでした。
そしてレートは停滞しながらも毎週コンテストに参加し続けた 2020 年 5 月、レート最高値を更新して水色まであと一歩というところでした。しかしここでコンテストで失敗して、レートを 58 落とし、レート 1158 からレート 1100 まで下がりました。 この 58 というのは、私の経験したレート減少の中で最も大きい値です。
この時のことは悔しくて今でも覚えています。その時のコンテストは A 問題と B 問題までは順調でした。次の C 問題は「入力として与えられた条件を満たす値を出力してください。ただし、そのような値が存在しない場合は-1 を出力してください」という問題でした。C 問題も解法まで思いついて実装もそれなりに順調でした。
しかし 1 つのテストケースがずっと WA (Wrong Answer：誤答) となっており、結局最後まで原因がわからないままコンテストは終了しました。 コンテスト後に公開されたテストケースを見て気づきましたが、ずっと WA となっていたテストケースは、「入力サイズが極端に小さい」かつ「そのような値が存在しない場合」というケースでした。 このケースが WA となっている理由は、コンテスト中に気づけるべきでした。1 回目の提出が WA となったのを確認した後、「入力サイズが極端に小さい場合」と「そのような値が存在しない場合」それぞれを満たすケースは手元でテストしていました。
しかし、この 2 つの条件両方を満たすケースを全く考慮していませんでした。そもそも「この 2 つを満たすケースを試す必要があるな」という考えすら出てきませんでした。 実際に当時提出していたコードを読むと、入力サイズが極端に小さい(サイズが 0)時だけは if 文で処理を分けていました。ですので、「入力サイズが極端に小さい場合のケースは網羅したのか」ということは注意すべきでした。 この失敗は個人的にはショックで、良い教訓になりました。
その後のコンテストでもあまり良いパフォーマンスが出ず、ずるずるとレートは落ち続けて最終的にレートは 990 まで落ちました。 ループで使っている変数"i"と"1"を間違えて書いてしばらく気づけなかった、ということもありました。
この頃から、さすがに普段の勉強量が足りていないことを自覚し始めて、平日も意識して過去問を解いたり本で勉強したりしていました。 他の水色に到達した人のブログを読んでも、その人に比べて知っているアルゴリズムの数が明らかに少ないとは思いませんでした。 解いた問題数がすべてではないですが、実際に AtCoder Problems で確認すると、周囲よりも解いた問題数は少ないことがわかりました。 ですので、簡単な過去問から順番に解いていきました。 この時は新しいアルゴリズムを覚えるというよりも、実装力や「同じような問題を過去問で見たことあるな」という経験を自分の中で蓄積することが目的でした。
レートが落ちても過去問を解いたりコンテストに参加し続けた理由はいくつかあります。見通しが甘かったとはいえ AtCoder に参加する前「Paiza でも S ランク取れたし、研究はアルゴリズム関連だし、僕なら水色くらいは余裕でいけるでしょ」と考えていました。そして初志貫徹をしなければという謎の義務感がありました。 あとは、社長のブログでも以下のように水色の技術力として以下のような説明があるので、「カンストってかっこいいなぁ、僕もなりたいなぁ」みたいな気持ちで頑張れました。
水色はかなり優秀です。普通に企業とかで超優秀って言ってるプログラマが居た時に、半分くらいはこのランクになると思います。数学が得意なタイプだと、この一つの上の青色に行きますが。
半数以上のIT企業において、アルゴリズム能力についてはカンストと言えるでしょう。特にアルゴリズム的な能力を必要としない会社であれば、ここから上はレートを上げても実務に役立つ部分はほとんどありません。
そして 2020 年の 7 月からは少しずつレートは上がっていき、2021 年 6 月、水色に到達できました。 水色になるまでに、最終的に約 1150 問解きましたが、特別多く問題を解いたというわけではないようでした。
おわりに
AtCoder に参加していたおかげで、業務でとある処理を実装する前に時間計算量を見積もって、「愚直に書いたら要求される時間内に処理が終わらないな」と気づいたこともありました。 時間はかかってしまいましたが、諦めずに参加し続けたことに関しては我ながら良かったと思いました。
また、これまでの経験から今後は以下のことを意識してコンテストに参加しようと思いました。
- エッジケースについて考慮する。
- 今自分が実装しようとしているアルゴリズムの計算量が本当に TLE (Time Limit Exceeded：指定された実行時間以内にプログラムが終了しないこと) にならない計算量なのか確認する。
- 1、2 個のテストケースで WA になってもあせらず、ノートに図などを書いて整理する。
緑色で停滞していてレートが下がっている時は、あまりにも水色に到達できなかったので「水色に到達したらコンテストへの参加をやめよう」と考えていました。 しかし、ぱっと見てわからなかった問題の解法がわかった時や実装して提出結果が AC になった時の感覚が忘れられないので、今後も定期的に参加して、次は青色を目標に頑張りたいです。
エンジニア募集
弊社ではマルウェアの解析などセキュリティの研究開発を行っています。興味のある方は弊社までお問い合わせください。
