2778
2465

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@e869120(E869120)

レッドコヌダヌが教える、競プロ・AtCoder䞊達のガむドラむン【䞭玚線目指せ氎色コヌダヌ】

2778
Last updated at Posted at 2020-02-19

0. はじめに

からの続きです

䞭玚線から読む方ぞ

近幎、AtCoder を䞭心ずした競技プログラミング競プロの存圚感が日に日に高たっおきおいたす。近幎では、AtCoderJobs ずいう AtCoder での実力に応じお求人に応募できるサヌビスや、アルゎリズム実技怜定ずいう名の怜定サヌビスも珟れおきおいたす。

そんな䞭、**「競プロでどうやっお䞊達すれば良いのかわからない」**ず思い悩んでいる方は倚いず思いたす。その悩みも、実力垯ごずに異なり、

  • 最初に䜕をやれば良いのか悩んでいる競プロ未経隓者もいる
  • 競プロ成瞟䞊䜍に食い蟌むためには䜕をやれば良いのか悩んでいる人もいる
  • 郚掻や瀟内などで、どういう競プロの教え方をすれば良いのか悩んでいる人もいる

ず思いたす。そこで本蚘事では、競技プログラミングで䞊達するためにはどういうこずを孊べば良いのか、どういう緎習をすれば良いのかのガむドラむンをレベル別に瀺し、䞊達に圹立おおもらうこずを最倧の目暙ずしおおりたす。

目次

初玚線

ç«  タむトル 備考
0. はじめに
1-1. 競プロずは䜕か ここからサポヌトしおいきたす
1-2. 競プロの 6 ぀の面癜さ 「競プロっお、面癜い」を䌝えおいきたす
1-3. 早速競プロを始めおみよう
1-4. AtCoder のレヌティングずは
1-5. 「茶色コヌダヌ」で芁求される 4 ぀のこず
1-6. 「茶色コヌダヌ」になるためのガむドラむン 初玚線のメむンです
1-7. Tips AtCoder の過去問を解ける䟿利なサむト
1-8. おたけ競プロにおける C++ のすすめ

䞭玚線

ç«  タむトル 備考
2-1. 「氎色コヌダヌ」で芁求される 4 ぀のこず
2-2. 「氎色コヌダヌ」になるためのガむドラむン 䞭玚線のメむンです
2-3. 分野別　初䞭玚者が解くべき過去問粟遞 100 問 この 100 問解けば実力䞊がるず思いたす
2-4. 「氎色コヌダヌ」を目指す人のための Tips 5 個

䞊玚線

ç«  タむトル 備考
3-1. 「黄色コヌダヌ」で芁求される 6 ぀のこず
3-2. 「黄色コヌダヌ」になるためのガむドラむン 䞊玚線のメむンです
3-3. 分野別　䞊玚者が解くべき過去問粟遞 100 + 50 問 この 150 問で実力䞊がりたす
3-4. 「競プロ兞型 90 問」のすすめ 新たに誕生した教材です
3-5. 「黄色コヌダヌ」を目指す人のための Tips 4 個
4. 「橙色コヌダヌ」になるためには䜕をすれば良いか 橙色たでサポヌトしたす
5. 「橙色コヌダヌ」の先　ガチンコ競技ずしおの競プロのはじたり
6. おわりに

2-0. 䞭玚線で玹介するこず

䞭玚線では、AtCoder で氎色コヌダヌたで最速で䞊達する方法を蚘したす。぀たり、レヌティング 1200 に最速で到達する方法を蚘したす。

なお、AtCoder のレヌティングは以䞋の衚の通りです。氎色コヌダヌは、党䜓の䞊䜍 1 割くらいです。1

レヌティング 色 盞察的な䜍眮 絶察的な䜍眮
2800+ èµ€ 䞊䜍 0.2%
2400-2799 橙 䞊䜍 0.6%
2000-2399 黄 䞊䜍 2% アルゎリズムの研究職・研究開発で重宝されるレベル
1600-1999 青 䞊䜍 5% ほずんどのIT䌁業でアルゎリズム胜力がカンストする
1200-1599 æ°Ž 䞊䜍 10% 半数以䞊のIT䌁業でアルゎリズム胜力がカンストする
800-1199 緑 䞊䜍 20% ゚ンゞニアずしおかなり優秀
400-799 茶 䞊䜍 35% 孊生なら優秀
1-399 灰 䞊䜍 100%
(2020/08/03 盞察的な䜍眮を修正 (曎新) したした)
※ 絶察的な䜍眮に関しおは AtCoder 瀟長・chokudai さんのブログ が゜ヌスです。
38.PNG

2-1. 「氎色コヌダヌ」で芁求される 4 ぀のこず

AtCoder で氎色コヌダヌ、぀たりレヌティング 1200 に到達するには、

  • AtCoder Beginner Contest で確率 8 割以䞊で 4 問正解できる
  • AtCoder Beginner Contest で確率 3-4 割で 5 問正解できる
  • AtCoder Beginner Contest の問題をある皋床早く解くこずができる
    • 目安は、A 問題 1 分、B 問題 4 分、C 問題 10 分、D 問題 25 分

こずが芁求されたす。そのためには、以䞋の 4 ぀のこずができれば良いず考えたす。もちろん、茶色コヌダヌで芁求される 4 ぀のこず は党おクリアしおいる必芁がありたす。

条件 1

暙準ラむブラリSTLを理解し、コンテストでもそれを䜿えるようになる。
ちなみに、C++ の堎合、䜿えおほしい STL は以䞋の 25 個。
abs sin/cos/tan string min/max swap
__gcd rand clock reverse sort
vector stack queue priority_queue map
lower_bound set pair tuple assert
count find next_permutation __builtin_popcount bitset

条件 2

以䞋に曞かれおいる、基本的なアルゎリズムずデヌタ構造を党お理解する。

アルゎリズム12 個

  • 党探玢bit 党探玢、順列党探玢を含む
  • 二分探玢
  • 深さ優先探玢DFS
  • 幅優先探玢BFS
  • 動的蚈画法bitDP などを含む
  • ダむクストラ法最短経路問題
  • ワヌシャルフロむド法最短経路問題
  • クラスカル法最小党域朚問題
  • 高速な玠数刀定法
  • べき乗を高速に蚈算するアルゎリズム
  • 逆元を蚈算するアルゎリズム
  • 环積和

デヌタ構造3 個

  • グラフグラフ理論
  • 朚
  • Union-Find

条件 3

条件 2 で玹介した基本的なアルゎリズムをコンテスト䞭に匕き出し、それらを䜿えるようになる。
぀たり、本蚘事で玹介する「基本アルゎリズム」が完党に身に぀く、ずいうこず。

条件 4

15 行皋床のプログラムであれば、ほがバグらせずに曞くこずができる。
35 行皋床のプログラムであれば、ある皋床速く曞くこずができる。バグらせおも、平均しお 5 分以内でバグを解決できる。

※ 実際に、35 行皋床のプログラムを、バグ取り含めお平均しお 15 分で曞けるようになれば、難しめの数孊的考察が必芁な問題が無い堎合、AtCoder Beginner Contest で 4 問正解を 50 分以内で達成できるこずが倚い。

補足

䞊の 4 ぀の条件を満たすようになれば、AtCoder Beginner Contest の D 問題たでは 7 - 8 割解けるようになるず思いたす。1 - 2 割は難しめの数孊的考察が必芁な問題が出題されたすが、それを解かなくおもコヌディングの速床ず正確性を鍛えるこずによっお、氎色コヌダヌになるこずは十分可胜です。

ちなみに、E 問題ずなれば数孊的考察を必芁ずする問題も少し増えおきたすが、兞型アルゎリズムの掻甚で解ける問題が倚いので、過去問を解いお挔習量を増やせば、3 - 5 割くらいの確率で解けるようになっおいくず思いたす。

さお、それらができるようになるためには、どのような緎習をすれば良いのでしょうか。

2-2. 「氎色コヌダヌ」になるためのガむドラむン

氎色コヌダヌに到達するためにやるべきこずは、以䞋の 5 ぀だず考えおいたす。

それぞれ、順番に説明しおいきたいず思いたす。

2-2-1. 暙準ラむブラリを䜿えるようになる

競技プログラミングにおいお、暙準ラむブラリSTLはずおも䟿利です。䟋えば C++ で問題を解く堎合、AtCoder Beginner Contest の E 問題レベルでは 50% 皋床の問題で、どこかしらの堎面で暙準ラむブラリの機胜が圹立ちたす。

ただし、党おの暙準ラむブラリを理解する必芁がある蚳ではありたせん。䟋えば C++ の堎合、競プロで知っおおきたい暙準ラむブラリは以䞋の 25 個に絞られたす。
abs sin/cos/tan string min/max swap
__gcd rand clock reverse sort
vector stack queue priority_queue map
lower_bound set pair tuple assert
count find next_permutation __builtin_popcount bitset

そこで、暙準ラむブラリを䜿えるようになるために、読むべき蚘事が 2 ぀ありたす。私が執筆した蚘事です
蚘事を読んで、これらの蚘事に茉っおいる問題䟋を解くず、暙準ラむブラリSTL 機胜がマスタヌできるず思いたす。

25 個の暙準ラむブラリの機胜を理解する

暙準ラむブラリが競プロのどんな堎面で䜿われるか理解する

2-2-2. 12 個の基本アルゎリズムをマスタヌする

初玚線でも述べた通り、競プロの本質は「実行時間制限に間に合う効率的なプログラムを考え、実装するこず」です。その効率的なプログラムを実装するこずにおいお、兞型的なアルゎリズムを知っおいるず非垞にお埗です。

しかし、氎色コヌダヌ、すなわちレヌティング 1200 に到達するために理解する必芁があるアルゎリズムは、僅か 12 個です。
党探玢 二分探玢 深さ優先探玢 (DFS) 幅優先探玢 (BFS)
動的蚈画法 (DP) ダむクストラ法 ワヌシャルフロむド法 クラスカル法
高速な玠数刀定法 べき乗を高速に蚈算する手法 逆元を蚈算する手法 环積和
※ ダむクストラ法・ワヌシャルフロむド法は最短経路問題を解くアルゎリズムです。
※ クラスカル法は最小党域朚問題を解くアルゎリズムです。

それらのアルゎリズムが孊習できる蚘事たちなどを玹介したす。

党探玢

党探玢には、「党列挙」「ビット党探玢」「順列党探玢」「再垰関数を甚いた党探玢」など倚くの皮類に分かれたす。しかし、基本的に以䞋の蚘事を読めば党郚理解できたす。

二分探玢

アルゎリズムの代衚䟋ずもいわれる二分探玢は、以䞋の 2 蚘事で解説されおいたす。

【補足】二分探玢に類䌌したアルゎリズムずしお「二分法」がありたす。それに぀いお詳しく知りたい方は以䞋の蚘事をお読みください。

深さ優先探玢 (DFS)

競プロに䜿えるテクニックの䞀぀です。以䞋の蚘事で解説されおいたす。

幅優先探玢 (BFS)

競プロで䜿えるテクニックの䞀぀です。以䞋の蚘事で解説されおいたす。

動的蚈画法 (DP)

以䞋の 3 ぀の皮類の動的蚈画法DPが理解できれば、氎色コヌダヌになるために求められる動的蚈画法の問題は倧䜓解けたす。

  • ナップザック DP郚分和問題・最小共通郚分列などは党おこれに含たれたす
  • 区間 DP
  • bit DP

それぞれの皮類に぀いお、アルゎリズムは以䞋の蚘事で解説されおいたす。

ちなみに、茶色コヌダヌ・緑コヌダヌには少し難しめですが、DP の教育的な問題がたずたったコンテストがあるので、過去問ずしおこれを最初の数問だけでも解くず良いず思いたす。党郚で 26 問ありたす

ダむクストラ法

$N$ 頂点 $M$ 蟺のグラフにおける頂点 $1$ から各頂点ぞの最短経路長を、$O(M \log{N})$ で蚈算するアルゎリズムです。詳しくは、以䞋の蚘事で解説されおいたす。

ワヌシャルフロむド法

$N$ 頂点 $M$ 蟺のグラフにおける党頂点察間の最短経路長を、$O(N^3)$ で蚈算するアルゎリズムです。詳しくは、以䞋の蚘事で解説されおいたす。

クラスカル法

以䞋の 2 蚘事で解説されおいたす。

高速な玠数刀定法

$N$ が玠数であるか $O(\sqrt{N})$ で蚈算する手法です。
単玔に、$N$ を $2, 3, 4, 5, ..., \sqrt{N}$ で割っお、どれでも割れなければ玠数です、ずいうアルゎリズムです。䟋えば、$37$ は $2, 3, 4, 5, 6$ のいずれでも割れないので玠数です。

※ 正圓性は、もし $N$ が玠数でなくお $N = pq$ $(p \geq 2, q \geq 2)$ で衚せるずするず、$p, q$ の少なくずも片方が $\sqrt{N}$ 以䞋だからです。䞡方 $\sqrt{N}$ を超えおしたうず、$pq > \sqrt{N} * \sqrt{N} = N$、よっお $pq > N$ ずなっおしたい、矛盟が生じたす。

べき乗を高速に蚈算するアルゎリズム

$a^b$ を $m$ で割った䜙りが $O(\log{b})$ で蚈算するアルゎリズムです。以䞋の蚘事で解説されおいたす。

逆元を高速に蚈算するアルゎリズム

$ax \equiv b \pmod{p}$ [$p$ は玠数] ずなるような $x$ を $O(\log{p})$ で蚈算するアルゎリズムです。以䞋の蚘事で解説されおいたす。

环積和

競プロで䜿えるテクニックの䞀぀です。以䞋の蚘事で解説されおいたす。

たた、环積和の亜皮ずしお、「いもす法」ずいうアルゎリズムもありたす。これも勉匷しおおくず良いです。

2-2-3. 3 個の基本デヌタ構造をマスタヌする

前節で述べた通り、競技プログラミングにはアルゎリズムを孊ぶこずが倧切です。䞀方、デヌタ構造を孊ぶこずも倧事です。ちなみに、アルゎリズムずデヌタ構造を混同しお芚える人が倚いのですが、違いは以䞋のようになりたす。

  • アルゎリズム問題を解くための方法のこず。
  • デヌタ構造デヌタの集たりを䞀定の圢匏で系統立おお栌玍するずきの圢匏。

さお、氎色コヌダヌになるために必芁なデヌタ構造は䞻に以䞋の 3 ぀です。

  • グラフ
  • 朚
  • Union-Find

それらのデヌタ構造が孊習できる蚘事たちなどを玹介したす。

グラフ

グラフずは、「頂点」ず「蟺」で構成されるデヌタ構造です。基瀎知識は、以䞋の蚘事で解説されおいたす。

朚

朚ずは、$N$ 頂点 $N-1$ 蟺の連結なグラフです。その特殊な性質ゆえに、競プロではよく問題にされたす。深さ優先探玢などずセットで出されるこずが倚いです詳しくは、以䞋の蚘事をご芧ください。

Union-Find

競プロで頻出のデヌタ構造です。以䞋の蚘事で解説されおいたす。

2-2-4. 過去問を解きたくる

皆さん、アルゎリズムずデヌタ構造を理解した埌に、重芁ずなっおくるこずは過去問を解くこずです。氎色コヌダヌになる蟺りたでは、

　競プロの実力 = アルゎリズムの理解床 × 競プロの挔習量

だず考えるこずもできたす。したがっお、過去問を解くこずはずおも重芁です。実際に、mencotton さんのツむヌト によるず、800 問解けば 60% 、1100 問解けば 90% の人が氎色コヌダヌになれたす。2020/01/17 時点の統蚈です
22.PNG

䞀方で、**「解いた過去問の問題数 = 競プロの挔習量」ずは限りたせん。**私の考えずしお、特に初䞭玚者のうちは、「教育的な質の高い問題」ず「それほど高くない問題」に分かれおいるず思っおいたす。

そこで、少ない問題数でも「氎色コヌダヌ」を達成しやすいように、茶色コヌダヌ・緑コヌダヌにずっお教育的良問だず思った問題を合蚈 100 問遞びたした。

にたずめられおいたすので、基本的なアルゎリズムを孊習した埌は、この粟遞 100 問を解き、䜙力があれば AtCoder Problems などのサヌビスを利甚しおさらに過去問を解いおいくこずをお勧めしたす。

2-2-5. 早解きを鍛える　バヌチャルコンテストのすすめ

競プロで戊う䞊で、難しい問題を解くこずも重芁ですが、簡単な問題を安定しお早解きするこずも重芁です。実際に、AtCoder Beginner Contest 155 においお、

  • 3 完最䞊䜍のパフォヌマンス1430
  • 3 完最䞋䜍のパフォヌマンス307

ず、ずおも倧きな差がありたす。さお、早解きを鍛えるには䜕をすれば良いのでしょうか。ここでお勧めなのが「バヌチャルコンテスト」です。

䟿利なサむト「AtCoder Problems」によるバヌチャルコンテスト

(2020/08/03 AtCoder Virtual Contest のサヌビス終了に䌎い、修正したした)

を䜿うず、仮想的に自分でコンテストを奜きな時間にやるこずができたす。より具䜓的に曞くず、AtCoder の過去問から䜕問か遞んで、開始時間ず終了時間を決めお、コンテスト圢匏で過去問を解けるずいう感じのサヌビスです。ちなみに、2 人以䞊の参加者ず同時に戊うこずができるのが面癜い点の䞀぀です。以䞋のように、コンテストず同様順䜍衚がリアルタむムで動きたす
23.PNG

サヌビスの利甚方法

基本的に、GitHub のアカりントからログむンする必芁がありたす。AtCoder Problems のサむトを開くず、右䞊に「Login」ず曞かれおいるリンクが衚瀺されるず思いたす。これをクリックしお、GitHub アカりントず連携するこずでログむンしおください。

バヌチャルコンテストに参加するためには、AtCoder Problems の右䞊の「Virtual Contest」ずいうリンクをクリックしお、バヌチャルコンテストのペヌゞに移動しおください。そうするず、䞋図のような画面が衚瀺されるず思いたす。
34.PNG

あずは、奜きなバヌチャルコンテストを遞んで、それに参加しおください。自分でバヌチャルコンテストを䜜りたい堎合は、「Create New Contest」 ずいう緑色のボタンを抌しお、コンテスト蚭定フォヌムに進んでください。あずはフォヌムの通りに、コンテストタむトルや䜿う問題などを入力するず良いです。

バヌチャルコンテストには、「Join」ずいうボタンを抌すこずで参加できたす。コンテスト時間䞭に AtCoder で該圓する問題の提出をするこずでバヌチャルコンテストに参加でき、順䜍衚も曎新されたす。
35.PNG

バヌチャルコンテストの掻甚の仕方

このサヌビスを掻甚しお、䟋えば以䞋のようなバヌチャルコンテストを定期的に䟋えば 1 週間に 2 回ずかやるず、プログラムの実装を速くできる力が身に぀くず思いたす。

  • AtCoder Beginner Contest から、A 問題 1 問・B 問題 2 問・C 問題 3 問の合蚈 6 問を集める。
  • これを合蚈 30 分でできるだけ解く。

氎色コヌダヌを目指す参加者にずっおは、AtCoder Beginner Contest の A, B 問題なんかあたりにも簡単かもしれたせんが、早解き力はそういう基本的なずころで差が付きたす。そのため、高難易床の緎習だけでなく、䜎難易床を早解きする緎習もした方が実力が䌞びるず考えられたす。


2-3. 分野別　初䞭玚者が解くべき過去問粟遞 100 問

AtCoder で氎色コヌダヌ、぀たりレヌティング 1200 を少ない問題数で達成するために、茶色コヌダヌ・緑コヌダヌにずっお適切な教育的良問を 100 問集めたした。

分野ごずに問題が分けられおいたす。たた、アルゎリズムの確認問題から応甚問題たで幅広い局の問題がありたすので、是非解いおみるこずをおすすめしたす。難しい問題もあるので、氎色コヌダヌを目指す人は 100 問䞭 70 問正解を目安に頑匵っおください。

100 問党郚解けたら、氎色コヌダヌどころか青色コヌダヌくらいの実力が付くず思いたす。そのため、既に氎色コヌダヌ以䞊であっおも、100 問党郚を解いおいない堎合は、解く䟡倀が倧きいず思いたす。

党探玢党列挙

1　ITP1_7_B - How Many Ways?　基本問題です。
2　AtCoder Beginner Contest 106 B - 105
3　AtCoder Beginner Contest 122 B - ATCoder
4　パ研杯2019 C - カラオケ　これが解ければ党探玢に慣れたず思っお良いです。

党探玢工倫しお通り数を枛らす党列挙

5　AtCoder Beginner Contest 095 C - Half and Half
6　䞉井䜏友信蚗銀行プログラミングコンテスト 2019 D - Lucky PIN
7　JOI 2007 本遞 3 - 最叀の遺跡　面癜いです。Python3 だず想定解法が TLE する可胜性がありたす。
8　Square869120Contest #6 B - AtCoder Markets　党探玢するず無数に通り数があるように芋えたすが、ひず぀工倫するず珟実的な通り数で党列挙できる問題です。
9　JOI 2008 予遞 4 - 星座探し

党探玢ビット党探玢

10　ALDS_5_A - 総圓たり　基本問題です。
11　AtCoder Beginner Contest 128 C - Switches
12　AtCoder Beginner Contest 002 D - 掟閥
13　JOI 2008 予遞 5 - おせんべい　茶色コヌダヌにはやや難問ですが解くこずをおすすめしたす。
14　Square869120Contest #4 B - Buildings are Colorful!　工倫も必芁で、䞀筋瞄では解けない難問ですが、解けば確実に力が぀きたす。

党探玢順列党探玢

15　AtCoder Beginner Contest 145 C - Average Length
16　AtCoder Beginner Contest 150 C - Count Order
17　ALDS_13_A - 8 クむヌン問題　面癜いです。

二分探玢

18　ALDS_4_B - 二分探玢　基本問題です。map でも解けたすが二分探玢で解いおみおください。
19　JOI 2009 本遞 2 - ピザ
20　AtCoder Beginner Contest 077 C - Snuke Festival　面癜いです。
21　AtCoder Beginner Contest 023 D - 射撃王　教育的に良いです。
22　AtCoder Regular Contest 054 B - ムヌアの法則　埮分しお二分法をするず解けたす。䞉分探玢ず話が繋がっおくるので、それも調べおみるず良いず思いたす。
23　JOI 2008 本遞 3 - ダヌツ　工倫しお二分探玢する、チャレンゞ問題です。

深さ優先探玢

24　ALDS_11_B - 深さ優先探玢　基本問題です。
25　AOJ 1160 - 島はいく぀ある　グラフの連結成分数は、深さ優先探玢で蚈算できたす。
26　AtCoder Beginner Contest 138 D - Ki　朚構造の問題の倚くは、深さ優先探玢を䜿いたす。
27　JOI 2009 予遞 4 - 薄氷枡り　深さ優先探玢は、朚構造だけではありたせん、ずいうこずを教えおくれる問題です。再垰関数を䜿っお解けたす。

幅優先探玢

28　ALDS_11_C - 幅優先探玢　基本問題です。
29　AtCoder Beginner Contest 007 C - 幅優先探玢　重み無しグラフの最短経路問題は、幅優先探玢で解けたす。
30　JOI 2011 予遞 5 - チヌズ
31　JOI 2012 予遞 5 - むルミネヌション　少し実装が重いですが、頑匵れば解けたす。
32　AOJ 1166 - 迷図ず呜ず　実装が少し重いです。
33　AtCoder Beginner Contest 088 D - Grid Repainting　これが解ければ、幅優先探玢に慣れたず思っお良いです。

動的蚈画法ナップザック DP

34　ALDS_10_A - フィボナッチ数　超基本。「DP ずは䜕か」を感じるこずができたす。
35　DPL_1_B - 0,1ナップザック問題　基本問題です。
36　DPL_1_C - ナップザック問題　基本問題です。
37　DPL_1_A - コむン問題　基本問題です。
38　ALDS_10_C - 最長共通郚分列　基本問題です。

(ここから先は、どのような DP で解けるのかは曞きたせんが、党郚ナップザック DP たたはその亜皮で解くこずができたす。)

39　JOI 2011 予遞 4 - 1 幎生
40　JOI 2012 予遞 4 - パスタ
41　JOI 2013 予遞 4 - 暑い日々
42　JOI 2015 予遞 4 - シルクロヌド
43　パ研杯2019 D - パ研軍旗
44　AOJ 1167 - ポロック予想
45　AOJ 2199 - 差分パルス笊号倉調

動的蚈画法区間 DP

46　ALDS_10_B - 連鎖行列積　基本問題です。
47　JOI 2015 本遞 2 - ケヌキの切り分け 2　$O(N^2)$ の区間 DP です。
48　AOJ 1611 ダルマ萜ずし　$O(N^3)$ の区間 DP です。

動的蚈画法bit DP

49　DPL_2_A - 巡回セヌルスマン問題　基本問題です。
50　Square869120Contest #1 G - Revenge of Traveling Salesman Problem　巡回セヌルスマン問題を少し倉えた問題です。
51　JOI 2014 予遞 4 - 郚掻のスケゞュヌル衚　bitDP に含たれるか埮劙ですが、䞀応入れおおきたす。
52　JOI 2017 予遞 4 - ぬいぐるみの敎理　少し難しいですが、是非挑戊しおみおください。

動的蚈画法その他

その他の DP ずしお代衚的なものは、最長増加郚分列問題 (LIS) です。
53　DPL_1_D - 最長増加郚分列
54　AtCoder Beginner Contest 006 D - トランプ挿入゜ヌト
55　AtCoder Beginner Contest 134 E - Sequence Decomposing　チャレンゞ問題です。

最短経路問題ダむクストラ法

56　GRL_1_A - 単䞀始点最短経路　基本問題です。
57　JOI 2008 予遞 6 - 船旅　埌述のワヌシャルフロむド法でも解けたす。
58　JOI 2016 予遞 5 - ゟンビ島　前述の幅優先探玢も䜿いたす。実装がやや重めです。
59　JOI 2014 予遞 5 - タクシヌ

最短経路問題ワヌシャルフロむド法

60　GRL_1_C - 党点察間最短経路　基本問題です。
61　AtCoder Beginner Contest 012 D - バスず避けられない運呜
62　AtCoder Beginner Contest 079 D - Wall
63　AtCoder Beginner Contest 074 D - Restoring Road Network　ちょっず数孊的考察が必芁で難しいですが、是非解いおみたしょう。

最小党域朚問題

64　GRL_2_A - 最小党域朚　基本問題です。
65　JOI 2010 春合宿 - Finals　(問題pdf) JOI 春合宿の問題ですが、比范的簡単です。
66　AOJ 1127 - Building a Space Station
67　AtCoder Beginner Contest 065 D - Built?　やや難しいです。単玔に最小党域朚を求めるず、$N$ 頂点 $N^2$ 蟺になりたすが、なんずそれを枛らすこずができたす。

高速な玠数刀定法

68　NTL_1_A - 玠因数分解　基本問題です。
69　AtCoder Beginner Contest 084 D - 2017-like Number

高速なべき乗蚈算

70　NTL_1_B - べき乗
71　Square869120Contest #1 E - 散歩
※ べき乗だけを䜿う問題は少ないですが、$nCr$ などを求める際に、逆元ずセットで出おくるこずが倚いです。䟋えば、$ax≡1 \ (mod \ p)$ の解は $a^{p-2} \ mod \ p$ ずなりたす。$p$ が玠数の堎合

逆元を䜿う問題

72　AtCoder Beginner Contest 034 C - 経路　nCr を求めるだけの基本問題です。
73　AtCoder Beginner Contest 145 D - Knight
74　AtCoder Beginner Contest 021 D - 倚重ルヌプ
75　AtCoder Beginner Contest 149 F - Surrounded Nodes　チャレンゞ問題です。解けなくおも、「そういう特殊な出力圢匏の問題っおあるんだな」ず感じおほしいです。

环積和

76　党囜統䞀プログラミング王決定戊本戊 A - Abundant Resources　基本です。环積和を䜿わなくおも解けたすが、是非䜿っお解いおみおください。
77　JOI 2010 本遞 1 - 旅人
78　JOI 2011 本遞 1 - 惑星探査　二次元环積和です。
79　AtCoder Beginner Contest 106 D - AtCoder Express 2
80　GigaCode 2019 D - 家の建蚭

(ここから先は、「いもす法」ずいうアルゎリズムを䜿う堎合がありたす。)

81　AtCoder Beginner Contest 014 C - AtColor　基本問題です。
82　AOJ 2013 - 倧厎
83　JOI 2015 本遞 1 - 鉄道運賃
84　JOI 2012 本遞 4 - 釘　チャレンゞ問題です。

Union-Find

85　DSL_1_A - 互いに玠な集合　基本問題です。
86　AtCoder Beginner Contest 075 C - Bridge　深さ優先探玢による連結成分の個数の数え䞊げでも解けたすが、Union-Find でも解いおみたしょう。
87　AtCoder Beginner Contest 120 D - Decayed Bridge　䞀個の考察ステップがあり、少し難しいですが、解くこずで埗られる力は倧きいず思いたす。

その他のテクニック

「圧瞮」によっお解ける問題たちです。

88　JOI 2008 本遞 1 - 碁石ならべ
89　JOI 2013 本遞 1 - 電食

「単玔な幟䜕蚈算」によっお解ける問題たちです。暙準ラむブラリに存圚する、2 乗根・䞉角関数などを䜿うず解けたす。

90　Square869120Contest #5 B - Emblem
91　AtCoder Beginner Contest 144 D - Water Bottle　本蚘事では觊れおいたせんが、䞉角関数の逆関数を䜿っお解くこずができたす。

実装問題

考察に比べお実装がずおも重い問題です。緎習になるず思いたす。

92　AOJ 1193 - 連鎖消滅パズル
93　Square869120Contest #3 B - 石萜ずしゲヌム
94　AOJ 1149 - ケヌキカット

数孊的な問題

AtCoder の問題の䞀郚では、解くために数孊的な考察を必芁ずしたす。䞊玚線にも繋げおいくために、氎色コヌダヌを目指しおいる人は「数孊的考察っお䜕なのか」「数孊的考察っおどんな感じで䜿うのか」くらいは知っおおくず良いず思うので、これを感じられる問題の代衚䟋を玹介しおおきたす。

95　AtCoder Beginner Contest 149 B - Greedy Takahashi　200-300 点問題で出る数孊的問題は倧䜓そんな感じです。貪欲法アルゎリズムに繋がっおきたす。
96　AtCoder Beginner Contest 139 D - ModSum　考察䞀個です。
97　AtCoder Beginner Contest 150 D - Semi Common Multiple
98　䞉井䜏友信蚗銀行プログラミングコンテスト2019 予遞 E - Colorful Hats 2
99　DDCC2020 予遞 D - Digit Sum Replace　これも考察䞀個です。
100　Tenka1 Programmer Beginner Contest D - Crossing　やや難しいですが、頑匵っお解いおください。

これが党郚解けたら、自信をもっお「氎色コヌダヌ盞圓の実力」があるずいっおよいです。

2-4. 「氎色コヌダヌ」を目指す人のための Tips 5 個

䞭玚線の最埌に、氎色コヌダヌを目指す皆さんにずっお䟿利な情報をいく぀か玹介したいず思いたす。

2-4-1. 「蟻本」のすすめ

ずころで、プログラミングコンテストチャレンゞブック通称蟻本ずいう本がありたす。

この本では、競技プログラミングで䜿われるアルゎリズムの解説がされおあるだけでなく、各皮アルゎリズムを䜿う競プロの問題の解き方も䞁寧に説明されおいたす。

競プロ関連の本の䞭で最も売れおいるものだずいっお良いです。「蟻本を読んで匷くなった」ずいう人はたくさんいるので、是非持っおおきたしょう。サンプルコヌドなども茉っおいるので、「兞型アルゎリズムのコヌドの曞き方を忘れおしたった」なんおずきにも䟿利です。
24.PNG

2-4-2. AOJ の「ALDS」コヌスのすすめ

初玚線でも述べたように、AOJ はプログラミングの基瀎やアルゎリズムの基瀎が孊べるコヌスがたくさんあるのが特城です。2　その䞭で、兞型アルゎリズムが孊べるコヌスがあっお、

ずいうものです。党郚で 60 問近くありたすが、本蚘事の䞭玚線に茉っおいる倧䜓のアルゎリズムが確認できるので、各皮アルゎリズムを孊習した埌に、是非該圓する分野の問題を解いおみおください。兞型アルゎリズムを既に知っおいたずいう方も、アルゎリズムを䜿う緎習にもなるので解くこずをお勧めしたす

※ ちなみに、䞭玚線どころか䞊玚線ですら述べないようなアルゎリズムを䜿う問題も ALDS には茉っおいたすので、党おの問題を解く必芁はありたせん。

2-4-3. 過去問は䜕分で解説を芋ればよいか

さお、過去問を解いおいお、そもそも解法が党然分からないずき、い぀になったら解説を読めば適切なのかわからない人が倚いず思いたす。そこで、経隓則からの倧䜓の目安を提瀺しおおきたす。

難易床 100 点問題 200 点問題 300 点問題 400 点問題 500 点問題 600 点問題
茶色コヌダヌ 5 分 7 分 30 分 45 分 - -
緑色コヌダヌ 5 分 5 分 20 分 35 分 50 分 2 時間
比范的簡単な問題にも関わらず解法がわからない堎合、「兞型知識や兞型テクニックを知らないから解けなかった」ずいう可胜性がずおも高いです。そのため、早めに解説を芋るこずをおすすめしたす。(2/20 00:47 PM. 远蚘)

※ 䜕分経っおも解法が分からなかったら、ずいうこずです。぀たり、䟋えば緑コヌダヌが 400 点問題を解くずき、解き始めおから 15 分で解法がわかっお実装も 10 分でできたのに、10 分間バグの原因がわからなくお合蚈 35 分超えおしたったので解説を芋るべき、ずいうこずではないです。

2-4-4. Twitter 掻甚のすすめ

競技プログラミングをやっおいくうちに、䜕かわからないこずを質問したくなるこずがあるず思いたす。䟋えば、

「このコヌドのバグが分からない。誰か原因教えお。」
「動的蚈画法が理解できないので教えおください。」

ずか、色々あるず思いたす。そんな時に䟿利なのは Twitter です。基本的に競技プログラミングをやっおいる人は優しいずいうかコミュニティがあたたかいので、Twitter に質問を投皿したり、ダむレクトメッセヌゞで匷い人に聞いたりするず、答えおくれる堎合が倚いです。

たた、Twitter をやっおいる堎合、コンテストで成功しお䞀色䞊にあがったずきに、䟋えば「氎色になりたした」ずかいうツむヌトをするず、ずおも倚くの人から「おめでずう」ずリプラむされるこずがありたす。これは競プロ界隈の文化の䞀぀なのですが、色が䞊がったずきにずお぀もない達成感を埗るこずができたす。

2-4-5. 競プロ関連むベント参加のすすめ

競技プログラマヌが䞀箇所の䌚堎に集たっおコンテストをやるようなむベントが定期的に開かれたす。䟋えば、

などがありたす。

このような競技プログラミング関連のむベントに参加する初䞭玚者は珟状それほど倚くないのですが、䞀床参加しおみるこずをお勧めしたす。

  • 競プロ参加者ずの亀流ができお楜しい
  • 普段はオンラむン䞊での掻動がほずんどである「競技プログラミング」に察するモチベヌションの維持、あるいはモチベヌションの向䞊に繋がる

などが、利点ずしお挙げられたす。


2-5. 本蚘事を終えた次は

本蚘事の内容をマスタヌできれば、氎色コヌダヌになれるず思いたす。氎色コヌダヌずいったら、AtCoder の䞊䜍 1 割ですので、十分䞭玚者を名乗っお良いず思いたす。ちなみに氎色コヌダヌになるず、半数以䞊の䌁業においおアルゎリズム構築胜力がカンストしたす。

しかし、さらに䞊を目指したい。青色コヌダヌや黄色コヌダヌ、そしお橙色コヌダヌずいった競プロ成瞟䞊䜍ランカヌを狙っおいきたいずいう方。䞭玚線よりもさらに高いレベルたでフォロヌしおいたすので、是非䞊玚線もお読みください。

初䞭玚者の方でも、䞊玚者にどういうアルゎリズム・知識・緎習方法が求められるかを知る機䌚になるず思うので、興味があれば是非お読みください。

䞊玚線

-1. ぀づく

次は、䞊玚線に続きたす。

  1. 2020 幎 8 月 3 日時点です。 ↩

  2. 初玚線で説明した Introduction To Programming I (ITP1)、䞭玚線で説明した Introduction To Algorithms and Data Sets (ALDS) だけではなく、動的蚈画法が孊べる DPL、グラフ理論が孊べる GRL、敎数論が孊べる NTL など、AOJ には様々なコヌスが甚意されおいたす。 ↩

2778
2465
15

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2778
2465

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?