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