はじめに
こんにちは、たごころです。
Atcoderのコンテストに初めて参加してから約３ヶ月で入茶することができました！
今回は自分が入茶するまでにしたことをメモがてら書いていこうと思います。稚拙な文章ですが温かい目で読んでいただけると幸いです。
1.Atcoderを始める前の著者のスペック
所属 偏差値60程度の高専1年生
プログラミング経験 習い事でichigojam basic、独学でスクラッチやarduinoIDEをやっていた。言語はpythonの基本文法を少しやったことがある程度(if文とかwhile文書けるくらい)
数学力 県模試の偏差値で65-67が取れる程度。典型的な問題が解けるだけで、発想力がなく多分この界隈においては数弱
2.競プロとの出会い
3月頃高専受験が終わって高専での授業に備えてpythonの勉強をしようと思い、入門書籍で勉強を始めました。しかし、本を読んで理解するのが苦手で全く理解できずに速攻で挫折しました。
そんなときにたまたまyoutubeでテレ東bizさんの競プロに関する動画を見ました。動画を見る以前から競プロの存在は知っていましたが、頭がいい人やすごいエンジニアがやるだけのものだと思い敬遠していました。しかしこの動画を見て面白そうだと思うのと同時に、初心者でも参加でき、プログラミング入門にも向いていることを知り競プロを始めることにしました。
3.茶色になるまでにやったこと
入茶を目指す上で
Atcoderで茶色になるのは結構難しいです！！
Xなどで見る界隈の人は緑や水色、それ以上が多く、灰色の次の色が茶色なので簡単だと思われがちです。しかし、実際のレベル感は全く違います。実際レートの分布を見てみると、半分以上の人は灰色です。
この分布を見てみるとそう簡単でないことがわかると思います。茶色くらいいけると思ってAtcoderに参加すると必ずやけどするので、いつかなれたらいいなくらいの心持ちの方がいいと思います。
4月 鹿本を読む
最初は競プロをpythonでやろうと思っていたので、pythonの解説も豊富なけんちょんさんの鹿本を初級編までやりました。解説が特別わかりやすいとは思いませんでしたが、良問が集められていて各セクションごとに実際のatcoderの問題を練習問題として載せていたので簡単な練習問題も含めて初級編までやりました。ただ練習問題には普通にdiff200~400くらいの問題もあり、なんなら緑diffもありました。練習問題ではけんちょんさんの解説はなく、Atcoder側の解説は基本C++しか載っていなくて挫折しそうだと思ったので途中からC++移行することに決めました。
自分のように本を読んで理解するのが無理でもatcoderでは問題を解くという目的があって、読んで終わりにならないので大丈夫だと思います。
この時は1日1時間から2時間くらいしか競プロに触れてなかったと思います。
4月~5月前半 APG4b
鹿本と並行しながらやりました。C++で競プロをやるなら最初はこれさえやればいいと思います。AAのSTLコンテナまで読みました。練習問題は一部の問題を除いて大体解きました。再帰関数の練習問題のようにむずいやつは一切手をつけないで次に行きました。正直ここで完璧に理解しようとするよりは、こんなものがあるのか程度の理解で早めに終わらせることが大切だと思います。今できなくてもどうせすぐ触れる知識ばかりなのでどうしても分からなかったら無理して理解しようとせず飛ばしてしまっても大丈夫だと思います。
5月前半〜6月 A埋め
ひたすらA問題を埋めました。A問題は
・変数の型
・条件分岐
・繰り返し
・文字列の扱い
・配列の扱い
などといった基本的な文法さえ理解していれば解けるので、解けない問題はあんまりなかったと思います。ただ簡単な問題を解いてACしているだけだったのでそんなに必要性はないです。
またこの頃からコンテストに参加していました。多分まだ「B問題なんか絶対解けない！！」と思っていました。
5月後半〜6月前半 B埋め
ABC353でA問題とB問題を早どきしてパフォーマンス600台を取れました。
めちゃくちゃ嬉しくて、B通した瞬間発狂しながら家中を走ってました。B問題でも解ける問題が出てきたのでA埋めと並行してB埋めを始めました。最新のコンテストからABC212までの問題を大体やりました。B問題では多重ループや二次元配列、連想配列、setなど本格的に競プロを始めるにあたって必要な知識がたくさん手に入るので茶色を目指すならB埋めは絶対にやるべきです。
ただB問題くらいになると骨のある問題も多くなってきます。例えばこの問題。ただループをたくさん回して全探索すればいいんですけど、実装がめちゃくちゃ重いし、添字ミスるし...でいまだにACしていません。（これ書き終わったらやろ...）これは私が苦手だっただけでもっと難しい問題もあると思います。なので少し考えてわからなかったら、snukeさんの解説放送を見ましょう。
ちなみにB埋めを始めたあたりからは自由な時間の半分以上は競プロに使っています。
6月後半~8月 C埋め
茶色になる上で最重要です。ABの早どきでも茶色パフォーマンスを出すことは可能ですが、C問題の難易度によっては茶色パフォーマンスを取れないこともあるので、安定しません
↑C問題のdiff795
↑C問題のdiff441
しかしB→C問題はA→Bの難易度に比べてとても高く、ABと比べて多くのアルゴリズムの知識や、高い考察力が要求されます。
またC問題からは計算量という概念を意識する必要があります。
https://atcoder.jp/contests/abc085/tasks/abc085_c
問題を要約すると
10000円札と5000円札と1000円札を合計N枚あって、合計Y円出会った時、各金額の札の枚数の組みを一つ求めてください。そのような組が存在しない場合は-1-1-1を出力してください
となります。この問題を愚直に解こうとしたら次のようになります
#include<iostream>
using namespace std;
int main()
{
int n,y;
cin >> n >> y;
for(int a = 0;a <= n;a++){
for(int b = 0;b <= n;b++){
for(int c = 0;c <= n;c++){
if(a*10000+b*5000+c*1000 == y && a+b+c == n){
cout << a << " " << b << " " << c << endl;
return 0;
}
}
}
}
cout << -1 << " " << -1 << " " << -1 << endl;
return 0;
}
しかしこのプログラムを提出するとTLEという結果が返ってくると思います。
初めてTLEという結果を見た時は「合っているのになんでACにならないんだ？？」と疑問に思うと思います。
TLEはTime Limit Exceededの略で実行時間が長すぎるという意味です。このプログラムの計算回数は3重のN回のforループが回っているので1000^3回計算することになるのですが、atcoderでは10^8以上の計算回数がかかるプログラムはTLEとなり不正解になります。なのでこのプログラムをもっと実行時間を短くする必要があります。
実はこの問題ではcを全探索をしなくてもaとbの値から求めることができます
for(a = 0;a <= n;a++){
for(int b = 0;b <= n;b++){
int c = n-a-b;
//以下略
}
}
このプログラムだと計算量は1000^2回でこれは10^6なので間に合います
丁寧な解説はけんちょんさんのこの記事を見てください
https://qiita.com/drken/items/fd4e5e3630d0f5859067#%E7%AC%AC-8-%E5%95%8F--abc-085-c---otoshidama-300-%E7%82%B9
C問題ではとにかくTLEを避けるためにアルゴリズムを工夫する必要があります。これは慣れないと結構難しいです。
というわけでC問題も最新のコンテストからABC212まで埋めました。C問題は難しいのでほとんどの問題が解説ACでした。中には解説を聞いても全くわからない問題もあり結構体力を使いました。その分C埋めをすることで手に入る知識は多く
・基本的なデータ構造の扱い方
・二分探索、尺取り法、bit全探索などたくさんのアルゴリズム
・動的計画法の基礎
・グラフ、unionfind,BFS,DFSの知識
・典型的な考察パターン
他にもたくさんのことが学べます。全く解けないからといって落ち込むことはなく、解説を見てこれらの知識を頭に叩き込みましょう。そして自分はC問題を116問解いた時に入茶することができました！！
他にやったこと
先に書いたことのように継続してやってはいないが、やったことを紹介します
1.鉄則
累積和と二分探索、動的計画法のあたりを解きました。
2.アルゴ式
動的計画法、グラフ、整数論的アルゴリズムをやりました。わかりやすいです。
3.EDPC
E問題までやりました。
4.入茶する上で必要なアルゴリズムの知識
入茶する上で有名なアルゴリズムの個人的に思う重要度を紹介します。
ただしここでは3完を目指す上での重要度です
二分探索 重要度:高
二分探索では答えで二分探索と配列の二部探索の2種類がありますが、特に配列の二分探索は実装する機会がありました。配列の二分探索はlower_boundを使うことで、ソート済みのある値以上の最小のイテレーターを高速に求めることができます。なので単調性がある問題文では、問題文を言い換えたり、データの持ち方を工夫して無理やり二分探索を使える形にすることで、計算量を落としてAC。という流れで解いた問題は結構あったと思います。答えで二分探索の方は自前で二分探索のプログラムを書く必要があるのですが、普通に書くとめちゃくちゃバグります。なのでめぐる式二分探索で書き方を統一した方がいいと思います。直近のABC365-Cで答えで二分探索する問題が出たのですが、想像以上にdiffが低くて驚きました。
bit全探索 重要度:高
bit全探索はbit演算を使って、2^N通りの全探索をするアルゴリズムです。例えば複数の商品（最大20程度）の買う買わないの選択肢を全探索したりする時に使います。bit全探索を使う時は大体制約が小さく(20以上になったらTLEして全探索できない)、2択の通りを全探索する場合には大抵使えるので、押さえておくべきです。bit演算を使うので実装は難しめです。私はこの記事で勉強しました。
私が始めてから2回くらい本番で実装したので少なくとも最近では頻出のアルゴリズムです。当時実装方法を理解していなかったので先の記事のコピペでABC358-Cを通した記憶があります。
累積和 重要度:高
累積和とは適切な前処理をおこない、配列上の区間の総和を高速で処理できるようにする手法です。たまに使いました。C問題レベルなら一次元の累積和さえ押さえておけば大丈夫です。私は鉄則本で勉強しました。
順列全探索 重要度:中
順列の通りを全探索します。計算量は(N!)なので最大でもN = 10くらいまでしか無理です。Cで順列を全探索したくて制約が小さい問題ならほぼ確実に順列全探索を使うと思っていいでしょう。C++ではnext_permutationを使うことで簡単に実装することができます。そこまで頻出ではありませんが、押さえておきたいアルゴリズムです。自分は詳しくないのですがpythonだと実行時間が間に合わないこともあるらしいので調べた方がいいかもです。ABC363-CではpythonだとTLEする人が多くdiffが高かったです。
DFS（深さ優先探索） 重要度:中
DFSはグラフや木の探索アルゴリズムで、ある頂点から開始して、その頂点から可能な限り深く探索していく方法です。一見グラフに見えない問題でもDFSで全探索をする問題はよくあります。DFSは基本的に再帰を用いて実装するのですが、私は再帰が苦手なので感覚を掴むのにかなり時間がかかったし、今でも苦手です。私はアルゴ式で勉強しましたhttps://algo-method.com/courses/496290c8624df207
BFS（幅優先探索） 重要度:中
BFSもグラフや木の探索アルゴリズムです。最短距離を求める時にも使います。個人的にはDFSよりもわかりやすいし実装しやすくて好きです。私は鹿本とけんちょんさんの記事を使って勉強しました。https://qiita.com/drken/items/996d80bcae64649a6580
素数判定、GCD,LCMなどの整数論的アルゴリズム 重要度:低
C問題で整数論的アルゴリズムを使用する問題には今の所であっていません。なので茶色になるための重要度は高くないです。ただ現在D埋めを始めていますが、D問題だと使う問題も多々みるのでこれもやっておいて損はないです。私はアルゴ式で勉強しました。
動的計画法 重要度:低
C問題でも出題されることはありますが、難しいのであんまり勉強しなくていいと思います。超基礎的な部分だけを勉強してコンテスト本番で出ないことを祈りましょう。私は鉄則とアルゴ式で勉強しました。C問題の動的計画法の難易度を掴みたい人はこのリンクに載ってる問題を数問解けばわかると思います。
https://zenn.dev/koyanagihitoshi/books/atcoder-classification-4/viewer/10-6
今後の目標
ひとまずは入緑とJOI本選進出を目指します。そのためにまずは鉄則埋めとD埋めを終わらせて、その後JOIの過去問も解こうかなぁーと思ってます。
あと今まで自分でできないデバックや実装はAIに投げることもあったのですが、JOIは生成AI禁止なのでデバック力、実装力をもっとつける必要があるなぁと思いました。なのでできるだけAIに頼らない。あとは自分の実装ミスをまとめてミスの傾向を掴んだりしようと思います。
あとはWeb開発とかもやってみたいですね（競プロ全然関係ないですがw）
競プロだけをやっていると身につく知識に偏りがありますし、高専の授業や将来働いた時に必要な実用的な知識も能動的に身につけていきたいです。