はじめに
2024年1月7日のAtCoder Beginner Contest 335にて入茶しましたので、色変記事を書いてみることにしました。拙文ではございますが、最後までお付き合いいただければ幸いです。
また、後述しますが筆者はプログラミング経験1年未満の駆け出しCoderですので、プログラミングの技術等の内容に関してはまだまだ素人同然です。後に幾つかのアルゴリズムとそれに対する私の認識を添えておりますが、素人感として軽く参考にする程度に留めていただければと思います。
最後に、私がプログラミングやAtCoderに興味を持つきっかけを与えてくれた友人J氏に特別の感謝を送ります。彼はプログラミングや競プロを含むパソコン関連全般に明るく、私の質問に対していつも的確な助言を与えてくださりました。彼の助けが無ければ、私がこの素晴らしい趣味と出会うことは無かったでしょう。
（余談ですが、この記事を書いたMarkdownに触れるきっかけを与えてくれたのもJ氏です）
筆者について
- 某大学の物理学科 2年生
- 小受・中受経験無し、真ん中程度の高校出身、軽音楽部所属
- 各種オリンピック経験無し
- 算数は苦手、数学はぼちぼち
- プログラミング経験1年未満のぺーぺー
- 主にPythonを使用、それ以外はあまり経験無し
- Twitter: Ahoh, AtCoder: AtatakaiInTheSky（暫定）
AtCoderの軌跡
AtCoderとの出会い
AtCoderとは2023年の6月中頃に出会いました。出会いのきっかけはJ氏にAtCoderのことを教えてもらったことで、AtCoderを始めてすぐは常設コンテストのアルゴリズムと数学 演習問題集や競技プログラミングの鉄則 演習問題集に手を伸ばしました。
ですが、図1を見ると分かるように、AtCoderを始めて最初の方はすぐに熱が冷めてしまい、そこからしばらくAtCoderにはあまり触れない時期が続きました。
AtCoder Beginner Contest への参加
AtCoder熱が再燃(?)したのは大学の夏休み末頃で、この時期から毎週のAtcoder Beginner Contest（以下ABCと記す）に参加し始めました。丁度Pythonの基本文法や基本的なライブラリについての知識が身に付き始めた頃で、後期からのPythonの演習場所としてAtCoderに再び意識が向いたのがきっかけです。
最初期に参加したコンテストではA問題、B問題に苦戦しながらなんとか2完するくらいの練度でしたが、そこから十数回のコンテストを経て、直近数回のコンテストでは茶色相当のパフォーマンスを安定して出せるようになりました。
こうしてAtCoderとの出会いから約半年、ABC335にてレート400の壁を越えることができました。
入茶するまでに学習した内容
問題演習について
問題演習に関してはABCの問題をABCの期間中に解くことが主でした。A問題、B問題に関しては過去問演習も進め、実装力を付ける練習としました。
解いた問題の難易度は主に灰色で、茶色相当の問題は今後の課題としています。
学習で用いた教材とその利用法について
ABCに参加してしばらくの間は教材を用いず、毎回のコンテストの問題に悪戦苦闘しながらアルゴリズムの基本や実装に慣れて行きました。そのやり方で伸び悩み始めた頃、J氏から
プログラミングコンテストチャレンジブック [第2版]（以下蟻本と記す）を貸してもらい、以降はそれを用いてアルゴリズムの基本となる考え方を学びました。
蟻本では各アルゴリズムの「お気持ち」を汲み取ることを重視し、実際にABCで出た時に自然な発想として思い浮かぶことを目標として学習を進めました。この学習法が自分の中でしっくり来たのか、蟻本を始めてから徐々に問題の見通しが速く立つようになり、毎週の参加によるコーディングの慣れも相まって、成績が徐々に向上して行きました。
学んだアルゴリズムについて
ここでは、私が今までに学んだアルゴリズムを紹介します。
私の問題演習不足により、学んだアルゴリズムはかなり限られてきます。また、苦手なアルゴリズムも多いため、アルゴリズムごとの記載内容の差が激しくなっています。
深さ優先探索（DFS）, 幅優先探索（BFS）
少し複雑な全探索を実装するアルゴリズムです。私が解いた問題でも何度か出番がありました。
個人的に苦手なアルゴリズムの1つで、やりたいことは理解できるのですが、再帰による処理の実装にまだ慣れていないため、問題演習を通して苦手を克服する必要がありますね。
茶diffの問題で過去に出題例があるため、基本的な実装は茶色到達までにできるようになっておくと良いのかな、といった感じがします。
二分探索（binary search）
ソートした配列から指定した値を効率的に探すアルゴリズムです。
個人的にかなり使うアルゴリズムで、基本的な使い方は理解できているつもりです。茶色到達までにできるようになっておくとかなり嬉しいアルゴリズムだと思います。
これを使って配列から値を探す計算量を $\mathcal{O}(n)$ から $\mathcal{O}(\log{n})$ にする技術はよく使います。また lower bound や upper bound を用いることで、指定した数以下の要素の数や指定した要素の数を計算する場合にも用いることができます。
Python では bisect の bisect_left と bisect_right を用いて lower bound と upper bound を実装できるため、数度自分で実装した後は bisect を用いると良いかと思います。
累積和
規則的に取っていった配列の要素の和を、別の配列に先に計算して順番に記録しておくアルゴリズムです。計算量を落とす技術としてよく用いるアルゴリズムで、基本的な使い方は理解できているつもりです。
計算量のかかる和の計算を配列の要素数だけの時間で済ませた後に定数時間でアクセスできるため、二分探索同様、茶色到達までにできるようになっておくとかなり嬉しいアルゴリズムだと思います。
貪欲法
操作の最善手を実装するアルゴリズムです。要は我々の頭で問題を処理して、最善手を解いちゃおうってことです。簡単な貪欲法は茶色になるまでにできるようになっておくと嬉しいのではないでしょうか。
解けると何故か何かに勝った気がするアルゴリズムです。
動的計画法（DP）
上手いこと条件式を整理することで、重複した計算を除いて処理するアルゴリズムです（DPはDynamic Programming の略ですが、 Doutekikeikaku Phou の略だという説もあります）。
メモ化再帰としてたまに実装する印象があります。メモ化再帰は比較的簡単に重複を落とすことができる技術なので、茶色到達までにメモ化再帰はできるようになると嬉しいのかなと思います。漸化式をあれこれするDPは茶色以降で必要になるのかなといった印象です（つまりこれからはこいつと戦わなければならないということです）。
個人的にかなり苦手なアルゴリズムの1つで、漸化式を立てるとなると、解けるかどうかは五分五分といったところです。
スタック（stack）, キュー（queue）と Python の配列
配列を実装するデータ構造です。スタックは先入れ先出し、キューは先入れ後出しを実装します。
使う上で違いを知っておくのは大切ですが、Python をつかっていると、これらの個々の内容を必ず意識しなければならないといった場面にはまだ遭遇したことがありません。
Python では list と deque の違いを意識することが重要です。例えば list では要素の追加や削除に要素の数に応じた計算量がかかりますが、deque では先頭の要素の追加や削除は即座に完了します。また、list では配列の各要素に即座にアクセスできますが、deque では要素の数に応じた時間がかかります。これを意識しないと TLE してしまうことがあります。
Union-Find
要素が同じグループに属しているかどうかを確認することに長けたデータ構造です。応用次第で様々なことができるそうですが、私はまだあまり習熟していません。茶色までに使える問題もいくつかありますので、基本的な実装は押さえておくと嬉しいかと思います。
おわりに
今回初めての色変記事を、というか初めての記事を書きましたが、如何せんまだまだ素人のため、薄っぺらい内容に仕上がっています。
今年中に入緑することを目標にしておりますので、入緑記事を書く頃には、もう少しマシな内容を書けるように精進します。