初心者向けフローチャート(暫定)
この記事は何?
競プロで強くなりたい!けど何をすればいいのかわからない!という人のための記事。(コンテストの出方とかは知ってるぐらいの人が対象です。わからない人は調べてね)
各章につけられた数字はレベルを表しています。数字が同じやつは順不同という感じ。
その章の内容が大体理解出来たら次に進んでいいと思います。不安になったらまた戻って来よう。
今ならAtCoder Novistepsを使うのも良いかもしれません。解く問題に迷ったら使ってみましょう!
とにかく量をこなしたい人はAtCoder Problemsで問題をたくさん解こう!(僕はこれです)
(0)C++に慣れよう!
新しく競プロを始めるという人はC++を学ぶのがおススメです。理由はいろいろありますが、大きな理由としては最もメジャーだからです。競プロの特性に合った言語仕様です。最初は少し構文が難しく感じるかもしれませんが、APG4bをしっかり読めば身に付くはずです。
APG4bを第一章まで、できれば二章までこなそう!C++の基本的な文法が学べます。(ただし、配列のアクセスにはat()ではなく[]を使うようにしましょう。)
AtCoder Beginners Selectionを解こう!競プロの問題に慣れよう!
(0)Pythonに慣れよう!
Pythonの文法をある程度知っている場合はこっちの方が最初はお勧めかもしれません。後々苦労することになると思うけど...
(C++を選択した方はこっちはやらなくて良いと思います。)
APG4b for Pythonを一通りこなそう。Pythonの基本的な文法が学べます。
AtCoder Beginners Selectionを解こう!競プロの問題に慣れよう!
(1)全探索
すべての基本、全探索。ABCのA問題やB問題は基本的な全探索で解くことが出来る問題が多いです。
$ 10^6(1000000)程度ならば全探索できる、を意識しておくと後々役に立つかもしれない。
どんな問題でも「とりあえず全部試すコードを書いてみる!」ができるようになると良い。
なお、bit全探索や順列全探索は少し難しいので、for文だけで書けるような全探索をまずはマスターしましょう!
配列(vector)の基本的な操作もできるようになると思います。
前述のAtCoder Beginners Selectionには基本的な全探索の問題が載っているので解くといい。
たのしい探索アルゴリズムの世界 前編の全探索の部分を読み、載っている類題を解こう!
(2)簡単な問題をたくさん解いてみよう
ここまでで基本的な文法は身に付いていると思います。具体的には、ABCのA問題とB問題はほとんどが解けるようになっているはずです。しかし、まだ問題演習をほとんどしていないので不安だと思います。
AtCoder ProblemsからABCのA問題とB問題を解いてみましょう!新しいもの(上の方にあるもの)から解くと良いです。
必ずしもすべて埋める必要はないです。基本的な文法が身に付いているなと思ったら次に進みましょう。
解けない問題があっても焦ることはないです。それは伸びしろです。解説を読んだり、前の章に戻ったりして身に付けましょう。
最初にも紹介しましたが、AtCoder NoviStepsというサイトに、上達に役に立つ問題が細かい難易度順に並んでいます。これを上から解いていくのも良いと思います!ここまでの内容で、11Q~7Qぐらいまでは解けると思います。
(2)setとmap
(Pythonではmapではなくdictという名前です。Pythonで進めている人はdictの使い方を調べてみてください)
setとmapは簡単に使えて応用が利くデータ構造!使えるようにしておいて損はないです。
APG4b にsetとmapの使い方のページがあります。まずはこれを見て使い方を知ろう!
この問題をsetを使って解いてみよう!
さっきの問題を、今度はmapを使って解いてみよう!
もっと問題が解きたかったら、けんちょんさんの【問題集】set・mapから点数が低めの問題を探して解いてみよう!
使い方がよく分からなかったら、解説のコード等をよく見てみるといいと思います。
それでもわからなかったら身近な人に聞いてみたり、SNS等で質問してみましょう!
(2)少し難しい問題に挑戦してみよう
基本的な文法のみを使って問題文の通りに実装をする問題は解けるようになってきたと思います。
ですが、ABCの最初の方の問題でも、競プロ特有の難しさがある問題が出題されることがあります。この章ではそういった問題に慣れることを目標にします!
AtCoder NoviStepsの6Q~4Qの問題を解いてみましょう!5~10分ほど考えて、わからなかったら解説を見る、というのを繰り返しましょう。問題はたくさんあるので、どんどん解説を開いちゃって大丈夫です!全ての問題を解かなくても大丈夫です。満足したら次の章に進みましょう。不安になったら残りを解きに戻ってきましょう。
ここから先は具体的なアルゴリズムがたくさん出てきます。興味があるものや、コンテスト中に解けなくて悔しかったものから習得していっても良いと思います!
(3)DP - 動的計画法  のきほんのき
いよいよ本格的なアルゴリズムの登場です!まずはDP(動的計画法)から。
DPでは「前に計算した値を使って、次の値を求める」という考え方がベースとなっています。この考え方は競プロでずっと役に立つ超重要なものです!
EDPC-A問題を見て、DPでどんな問題が解けるかを知ろう
動的計画法超入門! Educational DP Contest の A ~ E 問題の解説と類題集を読んで、DPを知ろう
EDPC-A問題とEDPC-B問題を解こう
以降の問題を解いても良いが、とりあえずAとBの2問が解ければ基本は出来ると思います
(3)BFS - 幅優先探索
BFSは最短経路を求めるアルゴリズムです!
初めてグラフという概念に出会うかもしれませんが、仕様はそこまで複雑なものではありません。街とその間を結ぶ道をイメージすると理解しやすいかもしれません!
鉄則本A63を見て、BFSでどんな問題が解けるかを知ろう
BFS (幅優先探索) 超入門! 〜 キューを鮮やかに使いこなす 〜を読んで、BFSを知ろう
記事内のBFSの実装テンプレを参考に、鉄則本A63を解いてみよう
けんちょんさんのBFSカテゴリから点数が低めの問題を探して解いてみよう!
鉄則本A62をBFSを使って解くのも良いかもしれない...?
(3)DFS - 深さ優先探索
DFSはBFSと対になる探索アルゴリズムです!それぞれに得意不得意があります。
再帰関数を習得していない場合、APG4b 2.05を読んで再帰関数を知ろう
DFS (深さ優先探索) 超入門! 〜 グラフ・アルゴリズムの世界への入口 〜【前編】を読んで、DFSを知ろう
鉄則本A62を解いてみよう
けんちょんさんのDFSカテゴリから点数が低めの問題を探して解いてみよう!
(3)Union-Find
Union-Findは連結成分を高速に管理するデータ構造です!
#Union-Find
ACL-Aを見て、UnionFindでどんな問題が解けるかを知ろう
(3)累積和
累積和も頻出のアルゴリズムです!
鉄則本A06を見て、累積和でどんな問題が解けるかを知ろう
準備中...
(3)二分探索 (lower_boundとupper_bound)
(Pythonではbisect_left、bisect_rightという名前です)
二分探索も競プロでずっと役に立つ超重要なものです!
準備中...
(3)bit全探索/順列全探索
ABCだとC問題やD問題で頻出です!
準備中...
(4)ダイクストラ法
ダイクストラ法はBFSを少し発展させたものです!
鉄則本A64を見て、ダイクストラ法でどんな問題が解けるかを知ろう
ダイクストラ法による単一始点最短経路を求めるアルゴリズムを読んで、ダイクストラ法を知ろう
先ほどの記事を参考にしつつ、鉄則本A64を解いてみよう
structとかがよくわからなかったら僕の提出を見てください
最短経路問題総特集!!!~BFSから拡張ダイクストラまで~に載っている類題を解いてみよう
(4)DP - 動的計画法  のきほんのほ
いよいよ二次元DPが出てきます!
EDPCのC問題からE問題までを解いてみよう!(解けないと思うので、解説を読んで理解しよう!)
動的計画法超入門! Educational DP Contest の A ~ E 問題の解説と類題集から類題を解いてみよう
僕のオススメはABC303D - Shift vs. CapsLockです。
(4)二分探索(決め打ち二分探索、答えで二分探索)
二分探索はこんな使い方もできます!!
準備中...
(4) 約数列挙/素数判定・列挙/素因数分解
3つをまとめたらすごいごつい感じになってしまった...
整数判定系のアルゴリズムです!
準備中...
(4)ダブリング
準備中...