Zenn
🐙

【色変記事】AtCoderで入茶できたので振り返ってみる

2024/02/19に公開
競技プログラミング
AtCoder
idea

はじめに

昨年の10月頃から始めたAtCoder(アルゴリズム部門)で先日遂に入茶(レートが400に到達)できました。

当初目標にしていた初の色変を達成することができたので、その振り返りをしてみます。

対象読者

  • これからAtCoderやってみようかなという人
  • 灰色で停滞している人

筆者のスペック

  • 大学は理系学部だったが、情報系や数学系ではない
    • しかし、後述する様にこの時代から多少のプログラミング経験はあった
    • 学生時代は微積や行列演算には沢山触れたが、AtCoderで必要となる組み合わせ論やグラフ理論に触れる機会はあまり無かった(と記憶している)
  • ITエンジニア歴5年
    • 経験言語
      • C++(VC++): この仕事を始めてから、最初の3年間使用し、その後もちょこちょこと書いている。AtCoderで現在使用している言語でもある
      • Python: 業務では2年ほどの経験あり。卒論ではデータの解析に使用
      • C: 大学の講義で1年ほど
    • 今までの業務でAtCoderで求められるCS的なアルゴリズムの実装経験や知識はほぼなし
    • BRep(※3次元構造を位相幾何を用いてCGやCADソフトウェアで表現する手法の一種)や画像処理のドメイン知識を活用した実装経験があり、数学的な知識を実装する事への抵抗感はない(むしろ好き)

学習法

以下の3つの取組みを行ってきました。

  • コンテスト参加
  • 鉄則本(競技プログラミングの鉄則 ~アルゴリズム力と思考力を高める77の技術~)
  • AtCoder Daily Training
    それぞれについて振り返りたいと思います。

ABCコンテスト参加

これは言わずもがなではありますが、コンテストに参加しないとレートは絶対に上がりません(参加して下がることもありますが...)。なので、毎週コンテストが開催される土 or 日の21時はできるだけ予定を空けて、Ratedで参加していました。
コンテスト終了後はコンテスト中に解けた、着手した問題は正解不正解に関わらず振り返りを行っていました。
自分の場合は、大体ABC3完+D問題を本番で挑戦したが解けなかった or AB2完+C or D問題を本番で挑戦したが解けなかったのどちらかのケースだったので、これらの問題の解説を読んだり、公式生放送を翌日視聴したりしていました。解説だけで理解できた方が時短にはなるのですが、公式生放送の方が背景なども含めて丁寧に解説されている印象があるので、解説だけだとよく分からない場合は公式生放送を観たほうが理解が進みます。また、本番中に着手もできなかった問題については、あまり振り返るメリットを感じなかったので触っていません。

鉄則本

https://www.amazon.co.jp/gp/product/B0BDZGDM9J/ref=ppx_yo_dt_b_search_asin_title?ie=UTF8&psc=1
言わずとしれた知の高速道路です。あまりに色々な所でおすすめされているので、AtCoderを始めるのとほぼ同じタイミングで購入しました。
以下の様な取り組み方で埋めていきました。

  • 1章から順番に取り組む(7章ヒューリスティックはスキップ)
  • A問題とB問題を必ず自分の手で実装する
    • A問題
      • 章のタイトルを見て、自分が既に知ってそうな分野であれば、最低25分は考える。タイトル的に自分の知らない知識(e.g. Union-Find, ダイクストラ法...etc)が必要そうな場合は割とすぐに解説を読んでから、実装していました。この書籍は図を交えて分かりやすく説明してくれているので、そこで理解を深めつつ、それでも理解できない箇所や疑問点は別途検索したりChatGPTに聞いてました。
    • B問題
      • ほとんどの問題が、A問題で得た知識を応用すれば解けるはずの問題(=前提知識が不足している事は基本的にはないはず)なので、最低でも25分は自分の頭で考え、全く手が動かなかったら解説を読んでいました。また、手元のテストケースは全て通ったけど、提出してみるとWAになってしまうという事が結構あり、そういった場合は最高60分はデバッグしたり、考慮漏れがないかを確認する時間としていました。

この書籍のおかげで、ABCコンテストで求められる典型的なアルゴリズムの知識面はそこそこカバーできたのかなと考えています。また、6章の考察テクニックついての章は、競技プログラミングに特化した本書ならではの、競技プログラミングにおける考察の重要なポイントが記載されており、非常に勉強になりました。

AtCoder Daily Training

https://atcoder.jp/contests/adt_top/
自分がAtCoderを開始したのとほぼ同時期(2023年の10月頃)に開始した、AtCoder社主催のバーチャルコンテストです。難易度がEASY、MEDIUM、HARD、ALL(左記の3種類全ての難易度を含む)の4種類が用意されており、過去に開催されたABCコンテストの過去問から出題されています。以下の様な難易度構成になっており、自分はEASYに取り組んでいました。

  • EASY
    • おすすめ対象者:　初めて参加される方・灰色
    • 問題難易度:　AABBC
  • MEDIUM
    • おすすめ対象者:　茶色・緑色
    • 問題難易度:　BBCCD
  • HARD
    • おすすめ対象者:　初めて参加される方・水色・青色
    • 問題難易度:　CCDEF
  • ALL
    • おすすめ対象者:　初めて参加される方・水色・青色
    • 問題難易度:　AABBCCDEF

今年の1月までは、上記のコンテスト参加と鉄則本を優先していたので、こちらはスルーしていたのですが、今年に入ってから何となく参加してみた所、感触が良かったので大体毎週木曜日の20:30の回はリアルタイムで参加、後は気が向いた時にバーチャル参加しています。
自分はほとんどの場合、本番コンテスト中(100分)にA〜D問題に取り組んでいますが、こちらは60分でA問題×2、B問題×2、C問題×1に取り組む事になるので、A〜C問題を解くスピードを上げる事に役立つと考えています。また、レートに関係しないとしても、本番同様に他の方との競争になるので、本番の立ち振舞(e.g. 自分が解けそうな問題の見極め、状況に応じて解く順番のスイッチ)や、メンタルを安定させる練習にもなっています。

反省点

ここまでの取り組みを振り返り、自分の反省点を挙げていきたいと思います。

鉄則本に時間をかけすぎた

はい、実は購入・着手から既に半年ほど経っていますが、未だに一周目も終わっていません。
現在、「9.8 最大フロー問題」まで進んでいるのですが(後半ではある)、1月の途中からAtCoder Daily Trainingを優先したり、単純にAtCoderのための時間を取っていないせいで、未だに完了していません。
大体平日の朝に1問、退勤後の夜に1問解くようなペースでやっているのですが、休日に関しては土曜日の昼間は遊ぶ→夜はコンテストに参加する→コンテスト後に酒を飲んで寝る→翌日日曜日は前日のコンテストの復習に充てる→遊ぶ...という過ごし方をしており、土日の進捗が0の事が結構あります。
また、この書籍では、基本的なデータ構造の話から、bit DPや区間DP、ニムやGrundy、Rolling Hashなどの高度な内容まで網羅しています。しかし、あくまで私の実際にABCコンテストに参加してみての印象ですが、茶色を目標とするのであればこのレベルの知識は不要だと思います。
おそらくこれらの知識はこれからも競技プログラミングを続け、更に高いレベルを目指すのであれば、どこかのタイミングで必要になると思いますが、まず茶色に到達する事を目標とするのであれば、用語だけ頭の片隅に置いておき、現時点ではスキップするのでも問題ないのかなと思います。
私の感覚的には、本書の★4までの問題を網羅しておけば、知識面に関しては茶色到達には十分かな？と考えています。
※少なくとも私の参加した2023/10〜2024/2までのABCコンテストの傾向を見る限り

実践形式の演習量が少なかった

以下が自分の現在の解いた問題数になります。


(自分の認識が間違っていなければ)上の画像の物がABCコンテストで解いた問題数(本番中+後日解いた物+AtCoder Daily Trainingで後日手動で過去コンテストに提出した物)、下の画像の「Other Contests」が鉄則本の演習で解いた物になると思います。これら以外に特に演習は行っていないので、この合算値(ABC:77+鉄則本:145=222)が現在の私の演習量とほぼ等しいはずです。
こうしてみると、およそ65%が鉄則本の演習量になります。しかし、上記の通り、この中にはおそらく茶色到達(ABC3完ぐらい)では求められないレベルの問題も含まれているので、茶色到達を一旦のゴールとした場合に最適だったかと言われると、少し疑問が残ります。
もちろん、茶色以上の高度な内容も学ぶ事で、D問題以降も本番中に解くことができれば、一気にレートを上げる事が可能ですが、それよりもまずは安定してABCをミスなく素早く3完する事を目指した方が簡単ですし、優先度が高いかなと個人的には考えています。
自分の場合は一応スキップせずに問題を解いてきたため、例えばE問題を読んだ時に、「これはセグメント木を使うと解けそう」という所までは考察できる事がありますが、それを実際の本番中に問題の条件に合う様に実装して提出するのは困難です。少なくとも私の場合、「そのアルゴリズムの基礎知識を持っており、関連した問題を数問解いた事がある」と「本番中に与えられた問題を考察し、適切なアルゴリズムを選択し、限られた時間内で実装する」というレベルには大きなギャップがありそうです。また、せっかく茶色以上の知識を持っているのに、それが本番で活かせず、レートに寄与しないというのは結構悲しいです。
なので、次の緑色を目指す時には、既に鉄則本のおかげで知識面はある程度網羅できていると思うので、知識面は一旦置いておいて、演習に力を入れていきたいと考えています。

人と比べて焦らない

AtCoderは他の参加者との競争です。他の人と自分を比較する事は、良くも悪くもモチベーションに影響を与えます。しかし、いつもそれが良い方向であれば問題ないと思いますが、例えば自分のレートが停滞している時に、自分よりもAtCoder歴が短いのに、自分より遥かに上のレートの人を見ると、思わず「うっ」となります。
しかし、世の中上を見ればキリがないので、「今まで本番ではB問題までしか解けなかったけど初めてC問題も解けた」とか、「初めて本番中にグリッド問題を通せた」など他者に依存し過ぎない評価軸を持つことも大切だと思います。

これから

ひとまず茶色に到達する事ができて一安心ですが、次は以下に取り組んでいきたいと考えています。

鉄則本を終わらせる

上記の通り、未だに完了していないため、まずはこちらを完了させたいです。

Rustを学習&試してみる

AtCoderではメモリ関連にそこまで気を配らなくて良いため(最悪メモリリークしてようがACできればOK)、特にC++に強い不満を感じている訳ではありませんが、どうしても記述量がPythonなどと比較すると多くなりがちなのと、コンパイル時にデバッグオプションをつけたとしても、エラーメッセージが結構分かりにくい事がある(特にテンプレートが絡む様なエラー)のが気になっています。
ここで既に経験のあるPythonへの移行を検討してみても良いのですが、それよりもRustという言語を学んでみたいという気持ちが強いです。元々AtCoderを始める前から興味がある言語だったのですが、今まで手をつけられていなかったので、これを機に挑戦してみようと考えています。
また、個人的には新しいプログラミング言語に慣れるのに、競技プログラミングは割とうってつけの教材なのかなと思っています。AtCoder開始前からそれなりに触っていたC++すらも、AtCoderを通して様々な学びや発見がありました。

C、D問題を埋めていく

私の感触では、緑色に到達するためには、本番中にABCD問題をある程度安定して解く必要がありそうです。
しかし、AtCoderを開始して半年ほど経過した現在でも、まだ本番中にD問題を解けた事がないため、緑色到達のためにはD問題に対する演習が必須だと考えています。また、C問題も偶に解けない事があったり、解けたとしてもかなり時間を使ってしまい、D問題にかけられる時間が全然ない事もあります。なので、C問題の安定性・スピードアップとD問題を解ける様になる事を目標に、AtCoder Daily TrainingのMediumに挑戦 & C、D問題を茶diff程度の物から埋めていこうと考えています。

最後に

AtCoderの実力=ソフトウェアエンジニアとしての実力、ではないと思いますが、得られる物も多いですし、他の方が読んだり長期的にメンテナンスする事を気にせずにコードを書けるのは楽しいので、しばらくは続けてみようと思います。
ありがとうございました。

Discussion