緑になるまでにやっていたこと[色変報告]

はじめに

2020/10/31日に開催された AtCoder Regular Contest 107で緑になれました！嬉しい！
他の方もやっているそうので僕もこれまでにやってきたことをまとめておこうと思います
(僕のプロフィールです)

始めてからこれまで

始めたて

僕は、プログラミングを始めて、ようやく最初の言語(C)の学習学習が終わったときに競技プログラミングを始めました。最初はC言語での参戦で、ABC-Aレベルは普通に解けてBに苦戦、Cは完全に「＼(^o^)／ｵﾜﾀ」って感じでした。まあ、当時は配列すら知らなかったですし、競プロでしっかりやり合えるような知識は皆無でした。ただ、コンテスト後に他の人の解法を見てたり、回数を重ねていくうちに少しずつ強くなっていた気がします。

C++/STLとの出会い

それでも、まだまだ弱い自分に1つ目の革命を起こしてくれたのがC++とその標準ライブラリ(STL)でした。まず、標準入力、出力に使うstd::cinとstd::cout。それまで僕が使っていた出入力はscanfとprintfでした。これがまあ面倒。関数形式でしたからね。でもcin、coutだとscanf、printfよりも体感的にかけるのでとても楽でした。
次に、vector。それまでは長さが固定の平配列しか使ってこなかった自分にとって、可変長配列はいままでの自分のコーディングをガラッと変えてくれました。

けんちょんさんの記事

STLを使って速度は格段に上がったものの、アルゴリズムの知識は皆無で、「幅優先？深さ優先？ﾅﾆｿﾚ」って感じでした。そしてそういったアルゴリズムの名前を調べていると、けんちょんさんの記事に出会いました。これがもう本当にわかりやすい。けんちょんさんのおかげでグラフが理解できたと言っても過言ではありません。

蟻本！

そして、ようやくアルゴリズムの知識がついてきたときに蟻本を買ってみました。すでに知っているアルゴリズムがほとんどでしたが、蟻本のおかげでそれらの知識がとても深まりました。ダイクストラ法も、名前は知っていてもそれがどういうものかわからなかったのですが、蟻本野おかげでようやく理解できました。
( なんか文章短くなってきてるな )

それから

それから、今日(2020/10/31)までAtCoder ProblemsのRecommendationsや茶埋めをしていくうちにレートは上がり、緑になれました

覚えたアルゴリズム

僕がいま覚えているアルゴリズムはこんな感じです
・線形探索(迫真)
・二分探索
・動的計画法
・幅優先探索
・深さ優先探索
・ダイクストラ法

この中で一番苦労したのが動的計画法です。高校数学の知識が必要と言われている競技プログラミングで、漸化式を知らなかった中学生の僕にとって、動的計画法は一番理解に苦しみました。でも、数を重ねていくうちに理解でき、普通の１次元DPなら普通にかけるようになりました。
色んな人の色変記事を見ていると、DPはやらなくても大丈夫！という感じですが、最近少し難し目の問題でも灰diffで、AtCoder全体の難易度やユーザーの強さが上がってきている気がします。

僕の思う、競プロで大事なこと

僕の思う競プロで大事なことはこの２つに限ります
・精進
・考察力・応用力
・学校での数学
順に説明していきます

1.精進

まず、精進。これは欠かせないです(一部の天才を除いて)。やっぱり、レートの高い人たちほど解いている問題数は多いです。コンテスト後、「この問題は過去に出たこの問題に似てる」というツイートをよく見かけます。つまり、多くの問題を解き、色んなパターンを知っているんだと思います。やっぱり精進は必要。

2.考察力・応用力

そしてもう一つ大事なのは考察力・応用力ですね。最近はAtCoderSTL(でいいんだっけ?)という、競プロで使えるアルゴリズムが入ったライブラリが整備されています。そのため、なれていないアルゴリズムも関数一つで解決できるようになったというわけです。便利な世の中になったもんだ
僕にとって、競プロは「実装力+考察力」ですが、そのうちの「実装力」はそれによって解決できてしまうので、残った「考察力」がこれから大事になってくるんだと思います。
例えば、僕はUnionFind(UF)というアルゴリズムは書けません。でも、UFを使った問題を解くことができます。それは、僕がUFの代替となるような手法(BFSによる連結成分の検出)を使っているからです。知識がほとんどなくても、いまある知識をどう「応用」すれば実装できそうか「考察」を行うことさえできれば十分強いと僕は思います。

学校での数学

やはり、プログラミングには数学は欠かせません。AtCoderでも、コンテスト２回に1回は必ず数学の知識を使った問題が出されています。2次関数の展開・因数分解や素因数分解はもちろん、Σを使う問題も出ます。そのため、学校での数学の授業は絶対におろそかにしてはいけないと思います。

これから必要になってきそうな技術

先ほどの3つに加えて、緑コーダーをやっていくときに必要になるんだろうな、という技術が、

与えられたデータを前処理できる技術

だと思っています。僕が緑になれたときのコンテスト、ARC107のC問題でそれを痛感しました。
ざっくりいうと、この問題の解法は「①どの行同士、列同士が入れ替えられるかを判定。それをグラフ構造にして、②そのグラフに存在する連結成分内の要素数の階乗をかけ合わせる」です。
つまり、この問題はグラフ問題と捉えることができます。
グラフ問題は多くの場合、グラフ構造がそのまま与えられますが、今回の場合はそれはありません。つまり、自分で作る必要があったのです。
このように、「与えられたデータからもう一つのデータを見つけ出す技術」は今後必要になってくると思います。

最後に

ここまで読んでいただき、ありがとうございました。灰、茶の方に少しでも参考になっていただければ幸いです。

余談
記事はほとんどないですが、機械学習にも興味があります。
twitter:@Luke02561