みなさん初めまして
初登校です🎒
少し前になりますが、2021/10/2に行われたABC221で入緑しました！🤗
今回は私が入緑するのに必要だったアルゴリズムとデータ構造についてまとめていこうと思います.
よろしくお願いします.
はじめに
AtCoder緑の現状について
例のchokudaiさんの記事だけではなく,
実はAtCoder内に未完成情報ですが こんな記事 があったりします.
共通して
競技プログラミングを熱心に取り組んでいるユーザと考えて問題なく、他社のアルゴリズム能力判定サイトでは、最高ランクに到達出来る水準です。 と記載があり, 簡単なものではないことに変わりありません.
なぜ2021年10月版を作るのか?
最近のAtCoder界隈は平均レベルがあがっている1部分があり,緑になるのにも要求されるレベルがあがっていると感じている人が一定数いるようです.2
またABCが8問体制になり問題の難易度の崖が緩やかになるなど,環境が変わってきているので現在の情報をまとめたかったため作成しました.
自己紹介
普段は業プロer(web)として自社サービスのバックエンド/フロントエンドを中心に開発しています. (Rails/React)
AtCoderをやる上で周りをみると強い人が大量にいますね. 一言で入緑といっても強い人は一瞬で到達していくので,そうではない私の場合を簡単に記載します.
- AtCoderを始めたのがアラサーになってからで,始めてから入茶するまでに10ヶ月ほどかかっている.
- 入茶してから入緑するまでに6ヶ月ほどかかっている. (入緑までに合わせて1年4ヶ月かかっている)
- 学歴は中堅理工系学部卒(非情報系, ちなみに理数系科目苦手だった)
- 持ってるIT系資格はFEとAP
統計情報をもとにしてはいませんが, 界隈の中では強い方ではありません.ご安心ください.
入緑した際のStatsは, はてぶの方に書いたので気になる方はそちらをどうぞ
使用言語, 開発環境
言語
Python3(Pypy)で取り組んでいます.
始めたときには業プロでPython使っていたのでその流れで選びました.
言語が異なると言語仕様によって利用できるライブラリ等で難易度に違いがでるので, Pythonだとそうなんだな~程度にお考え下さい.
lower_boundはデフォで持っててほしいよPythonさん...
開発環境
正直パフォーマンスには関係ないのですが記載しておくと,
Windows10+WSL2(Ubuntu)+Docker+VSCode(RemoteDevelopment) で取り組んでいます.
CLIで済むと楽だと気づいたので,
online-judge-toolsとatcoder-cliを使ってコンテストの生成からテストと提出までをCLIで行っています.
学習/使用したアルゴリズム
| アルゴリズム | 理解度 | 使用 | 使用した問題 |
|---|---|---|---|
| 線形全探索 | ○ | ○ | ABC214-B など |
| bit全探索 | ○ | × | |
| 二分探索 | ○ | ○ | ABC212-C |
| 順列/組み合わせ/包除原理 | ○ | ○ | ABC215-C |
| 累積和 | ○ | ○ | ABC220-C |
| imos法 | ○ | ○ | ABC221-D |
| 基礎DP | ○ | ○ | ABC220-D |
| 耳DP | ○ | ○ | ABC211-C |
| DFS | △ | ○ | ABC213-D |
| BFS | △ | ○ | ABC211-D |
| トポロジカルソート | △ | × | |
| 約数列挙 | ○ | × | |
| GCD/LCM | ○ | ○ | ABC215-D |
| エラトステネスの篩 | ○ | × | |
| 座標圧縮 | ○ | ○ | ABC213-C |
| 転倒数 | △ | × | |
| 幾何要素 | ○ | ○ | ABC197-D |
グラフ理論に関するアルゴリズムは基礎BFS,DFSができれば足りると思います. (経路復元はできなくてもなんとかなる)
経路復元できないって経路探索アルゴリズムちゃんと理解してないよね? はい精進します...
あとDijkstra法,ワーシャルフロイド法と言った最短経路を求めるアルゴリズムは使えなくても大丈夫でした. 3
学習/使用したデータ構造
| データ構造 | 理解度 | 使用したか | 使用した問題 |
|---|---|---|---|
| queue | ○ | ○ | ABC211-D |
| priority-queue | ○ | ○ | ABC212-D |
| HashTable | ○ | ○ | ABC218-D |
| Union-Find Tree | △ | × |
一番重要なのはqueueです.
次に重要なのはHashTableです.
それぞれTLEを防ぐ上で重要なデータの持ち方になります.
Union-Find Treeは何度かコンテスト中に問題に出会ったのですが,結局1度も解けませんでした...
学習方法
問題を解きながら, 分からない問題は解説ACをしてアルゴリズムを身に着けて行きました.
主に
AtCoderProblems の
そして
競プロ典型90問 (☆3まで)
を解きました.
そして,非常に重要なのはコンテスト後に挑んで解けなかった1問を解くことです.
緑diff以下の解けなかった問題を解説ACするようにしていました.
余談ですがアルゴリズムのメモやAtCoderの自分の取り組んだ問題管理にはNotionを使っています. オススメです.
やらなかったこと(必要なかったこと)
-
自作ライブラリ/スニペットの作成
緑になった現在はUnion-Find Treeのライブラリを作りましたが, 入緑に限っては特にライブラリを作る必要はなかったです.
同じく早解きの観点からスニペットを用意して参戦する方も多いと思いますが, 現時点ではなくても何とかなっています.(いずれ作る予定です) -
競プロ関連書籍による勉強
蟻本/螺旋本/けんちょん本と買ってあるのですが積読状態になってしまっています.
書籍による知識のベースを埋め込まなくても, 精進の中で解説を見てアルゴリズムが理解できてoutputできているうちは優先しなくてもよさそうに思います.
典型90で行き詰ったら手を付けていく予定です. -
グラフ理論に関する書籍での勉強
例題で学ぶグラフ理論/グラフ理論入門の2冊を買ってあるのですが積読状態になっています.
グラフ理論に関して全く得意意識がないので入水に向けて重点的に取り組む必要があると思っていますが, 緑までだったらなくても大丈夫でした. -
AtCoder以外の競プロ
AOJもCodeForcesもyukicoderもやりたいなと思ってますができてません.
さいごに
入緑したい~! と思っている方の少しでも参考になれば幸いです.
私は入水を目指してこの後も精進を続けます.
初投稿なので非礼や誤りがありましたら申し訳ありません.ぜひご指摘ください.
また疑問質問もありましたらコメントお待ちしています.
ありがとうございました!