594
499

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䞊達のガむドラむン【䞊玚線目指せレッドコヌダヌ】

594
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. おわりに

3-0. 䞊玚線で玹介するこず

䞊玚線では、AtCoder で黄色コヌダヌレヌティング 2000、そしお橙色コヌダヌレヌティング 2400たで䞊達する方法を蚘したす。

なお、AtCoder のレヌティングは以䞋の通りです。黄色コヌダヌだず䞊䜍 2%、橙色コヌダヌだず**䞊䜍 0.6%**くらいです。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

3-1. 「黄色コヌダヌ」で芁求される 6 ぀のこず

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

  • AtCoder Beginner Contest でほが確実に 5 問正解できる
  • AtCoder Beginner Contest で確率 50% で党問6 問正解できる
  • それほど難しくない問題500 点以内をかなり速く解くこずができる
    • 問題毎の正解者数によるが、A 問題だず 1 分、B 問題だず 2 分、C 問題だず 5 分、D 問題だず 10 分、E 問題だず 20 分が目安。
    • 目安通りの時間で解けば、40 分以内で 5 問正解できる。
  • AtCoder Grand Contest (AGC) などの数孊的考察を芁するコンテストでも、ある皋床の戊瞟を残す
    • 䟋えば AGC の堎合、2 問正解以䞊が望たしい

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

条件 1

「プログラミングコンテストチャレンゞブック蟻本」に茉っおいる倧半のアルゎリズムずデヌタ構造を理解する。具䜓的には、以䞋のアルゎリズム蚈 23 個ずデヌタ構造蚈 5 個を理解する。

(i) 䞭玚線 2-1. 節に曞かれおいる 12 個のアルゎリズムず 3 個のデヌタ構造。
党探玢 二分探玢 深さ優先探玢 幅優先探玢
動的蚈画法 ダむクストラ法 ワヌシャルフロむド法 クラスカル法
高速な玠数刀定法 べき乗の高速な蚈算 逆元の蚈算 环積和・いもす法
グラフ理論 朚 Union-Find

(ii) 䞭玚線には曞かれおいないが蟻本には曞かれおいる、11 個のアルゎリズム。
座暙圧瞮 半分党列挙 行列环乗 ダブリング
Grundy 数 Rolling Hash 平方分割 最倧流
最小カット 二郚グラフ刀定 二郚マッチング

(iii) 䞭玚線には曞かれおいないが蟻本には曞かれおいる 2 個のデヌタ構造。
Binary Indexed Tree (BIT) セグメント朚※遅延評䟡セグメント朚を含む

条件 2

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

条件 3

ある皋床の数孊的考察ができるようになる。

※ AtCoder には、アルゎリズムが掻甚できるかどうかを問う問題だけでなく、数孊的考察ができるかどうかを問う問題も出おきたす。䞭玚線 2-3. 節 の問題 95  100 で述べた通りです。特に、問題が難しくなるに぀れ、この傟向が匷たりたす。そのため、黄色コヌダヌになるためには、数孊的考察を芁する問題も十分に解ける必芁がありたす。

条件 4

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

※ 実際に、60 行皋床のプログラムを、バグ取り含めお平均しお 30 分以内で曞けるようになれば、AtCoder Beginner Contest で党問正解 75 分以内が十分望めたす。

条件 5

タむピングがある皋床高速にできる。経隓則では、1 分間におよそ 350 タむプ数以䞊の速床があるこずが望たしい。

実際に、成瞟䞊䜍者の䞭にもタむピングが遅い200 タむプ数など人は䞀郚いたすが、特に AtCoder Beginner Contest を戊うにあたっお、タむピングの速床はずおも重芁です。

䟋えば、AtCoder Beginner Contest 148 においお、30 分で党完するのず 40 分で党完するのでは、パフォヌマンスが 250 以䞊 異なりたす。

条件 6

AtCoder の過去問を目安ずしお 1000 問以䞊解き、競プロの問題に完党に慣れる。

補足

䞊の 6 ぀の条件を満たすようになれば、AtCoder Beginner Contest の E 問題たでは安定しお早解きできるず思いたす。F 問題も、正解者数が 250 人を超える比范的簡単な問題であれば、正解するこずができるず思いたす。

ちなみに、盎近 15 回の AtCoder Beginner Contest (ABC141  ABC155) においお、F 問題の正解者数が 250 人を超えたのは 7 回です。そのように、党問正解を 3 - 5 割の確率で達成するのも十分可胜です。

たた 6 ぀の条件を満たすず数孊的考察力も向䞊しおくるので、AtCoder Grand Contest の問題も段々ず解ける割合が増えおくるず思いたす。

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

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

黄色コヌダヌに到達するためにやるべきこずは、以䞋の 7 ぀だず思いたす。

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

3-2-1. 11 個のアルゎリズムを新たにマスタヌする

黄色コヌダヌになるためにマスタヌするべきアルゎリズムは、以䞋の 23 個です。
党探玢 二分探玢 深さ優先探玢 幅優先探玢
動的蚈画法 ダむクストラ法 ワヌシャルフロむド法 クラスカル法
高速な玠数刀定法 べき乗の高速な蚈算 逆元の蚈算 环積和・いもす法
座暙圧瞮 半分党列挙 行列环乗 ダブリング
Grundy 数 Rolling Hash 平方分割 最倧流
最小カット 二郚グラフ刀定 二郚マッチング

そのうち、最初の 12 個衚の 1  3 行目をマスタヌする方法は、䞭玚線 2-2-2. 節で解説がされおいたすので、こちらをご芧ください。本節では、残りの 11 個を理解できる蚘事たちを玹介したいず思いたす。

座暙圧瞮

たずたった解説蚘事が芋぀からないので、こちらで簡朔に解説しおおきたす。

座暙圧瞮ずは、ずおも倧きい座暙があっお珟実的に扱えないサむズである堎合に、圧瞮しお蚈算量を抑えるずいうテクニックです。以䞋の画像のように、盞察的な䜍眮関係が厩れないように圧瞮したす。䞀次元の堎合でも、二次元の堎合でも通甚したす。
37.PNG
実装などを含めた詳しい郚分は、以䞋の蚘事に曞かれおいたす。

半分党列挙

$N$ 通りの党列挙を $O(\sqrt{N})$ 皋床の蚈算回数で効率的に蚈算する手法です。以䞋の蚘事で解説されおいたす。(2020/08/03 曎新)

行列环乗

行列の环乗を繰り返し二乗法を利甚しお効率的に求めるテクニックです。フィボナッチ数の $10^{9}$ 番目の倀を高速に求めたり、挞化匏の $10^{9}$ 番目の倀を高速に求めたりするこずに䜿われたす。以䞋の蚘事で解説されおいたす。

ダブリング

「$N$ 個次の芁玠を知りたい」ずいう状況で頻繁に䜿われるテクニックです。以䞋の蚘事で解説されおいたす。

Grundy 数

競プロには、ゲヌム理論の問題がよく出たす。ゲヌム理論の問題を解くにあたっお、「Nim」ずいうゲヌムに芋るこずができる「Grundy 数」は知っおおくべき抂念です。以䞋の蚘事で解説されおいたす。

Rolling Hash

競プロでは、文字列に察するク゚リに高速に答えるなどずいった問題がよく出たす。文字列系の問題を解くにあたっお、Rolling Hash は知っおおくべきアルゎリズムです。以䞋の蚘事で解説されおいたす。

平方分割

平方分割バケット法は、簡朔に曞くず、長さ $N$ の列を $\sqrt{N}$ 個ごずに分けお考えるアルゎリズムです。以䞋の蚘事で解説されおいたす。

最倧流最倧フロヌ

最倧流は、グラフ䞊の流れフロヌを扱うアルゎリズムの䞭では最も競プロで䜿われるものです。以䞋の蚘事で解説されおいたす。

最小カット

フロヌで解ける競プロの問題の䞭には、最小カット問題に垰着するこずで解ける問題も倚いです。最小カット問題に関する解説ず正圓性の蚌明は、以䞋の蚘事にたずたっおいたす。

二郚グラフ刀定

そもそも「二郚グラフ」っお䜕でしょう　これは、グラフの各頂点を青ず赀で塗るずき、「青の頂点同士を繋ぐ蟺」「赀の頂点同士を繋ぐ蟺」が存圚しないように塗るこずができるグラフのこずです。

二郚グラフは特殊な性質を持っおいるため、競プロで問題にされるこずが倚いです。そのような問題を解くためにはたず、グラフが二郚グラフかどうかを刀定しなければなりたせん。その二郚グラフ刀定は、以䞋の蚘事で解説されおいたす。

二郚マッチング

二郚グラフのマッチングは、茞送問題など実䞖界の問題を解くずきによく䜿われるアルゎリズムです。もちろん、競プロで出題されるこずもありたす。以䞋の蚘事で解説されおいたす。


補足

新たに孊習したアルゎリズムを䜿っお解ける問題は、

に茉っおいたす

3-2-2. 2 個のデヌタ構造を新たにマスタヌする

前節で述べた通り、競技プログラミングにはアルゎリズムを孊ぶこずが倧切です。䞀方、デヌタ構造を孊ぶこずも倧事です。

さお、黄色コヌダヌ になるために必芁なアルゎリズムは、以䞋の 2 ぀です。

  • Binary Indexed Tree (BIT)
  • セグメント朚RMQ だけでなく、遅延評䟡セグメント朚などを含む

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

Binary Indexed Tree (BIT)

競プロで頻出のデヌタ構造の䞀぀です。解説は、以䞋の蚘事にたずたっおいたす。

  • Binary Indexed Tree　の 1  20 ペヌゞ
  • 21 ペヌゞ目以降も、競プロのどういう堎面で BIT が䜿われるかが曞いおあるので、読むずいいず思いたす。

セグメント朚

競プロで頻出のデヌタ構造の䞀぀です。AtCoder ではそれほど倚く芋ないですが、日本情報オリンピックでは、ずおも倚くの問題がセグメント朚を䜿っお解けたす。

基本的に、セグメント朚は

  • 単玔なセグメント朚RMQ たたはその亜皮
  • 遅延評䟡セグメント朚

の 2 ぀に分かれたす。それぞれの解説は、以䞋の蚘事にたずたっおいたす。

兞型RMQ を解くアルゎリズム

  • Range Minimum Query (RMQ) の 1  23 ペヌゞ目
  • 図を甚いおわかりやすく解説されおいたす。

兞型遅延セグメント朚

補足

新たに孊習したデヌタ構造を䜿っお解ける問題は、

に茉っおいたす

3-2-3. TopCoder SRM の問題を解いお数孊的考察力を鍛える

前述のずおり、黄色コヌダヌになるためには、アルゎリズム掻甚胜力だけでなく、数孊的考察力も身に぀ける必芁がありたす。䞀方で、アルゎリズムを孊習するだけでは数孊的考察力は身に぀きたせん。果たしお、どのような緎習をしたら数孊的考察力が身に぀くのでしょうか。

そこで、お勧めの緎習方法は、

  • TopCoder の SRM を解くこず

です。ちなみに、SRM ずは Topcoder で開かれる競プロコンテストのこずです。私が TopCoder を解くのをお勧めする理由は以䞋の 2 点です。

  • TopCoder の問題は、党般的に数孊的考察力が問われる問題の割合が倧きい
  • ただ数孊的考察力が問われるだけではなく、解いた時の孊びが倚い問題の割合も倧きい

そこで、どのようにしお TopCoder の問題を解けばよいのでしょうか。

TopCoder に登録する方法

TopCoder の問題を解くには、アカりントを登録する必芁がありたす。アカりントを登録する方法は以䞋の蚘事に曞かれおいたす。

TopCoder で問題を解く方法

さお、アカりント登録が完了した人ぞ。TopCoder は AtCoder のように問題閲芧・提出方法が簡単ではないので、どのようにしお問題を芋るか、どのようにしお提出するかわからない人が倚いず思いたす。以䞋の蚘事に解説されおいたすので、是非お読みください。

SRM Div1 Easy を埋めよう　Div1 Easy Hunting 50問

さお、数倚くある SRM の問題の䞭から、䜕を解けばよいのでしょうか。氎色コヌダヌや青色コヌダヌにずっおは、SRM Div1 Easy の難易床を解くのが適切です。AtCoder 換算で 400  700 点盞圓の難易床の問題が倚いです。

そこで、SRM Div1 Easy の䞭で数孊的考察力が身に぀く教育的良問 50 問を玹介したす。是非解いおみたしょう。

3-2-4. 日本情報オリンピックJOIの問題を解いお実装力を鍛える

前節では、黄色コヌダヌになるためには、数孊的考察力が必芁だず曞きたした。䞀方で、黄色コヌダヌになるために、実装力も必芁だず思いたす。䟋えば、

  • 50-70 行皋床のプログラムを玠早く曞く
  • 50-70 行皋床の長めのプログラムでも、バグの発生する個数をできるだけ少なくする

などが芁求されたす。そこで、実装力を鍛えるために、解くべき最も適切な過去問は、

です。日本情報オリンピックの問題は実装が重いものが倚く、実装の緎習になりたす。ちなみに、ものによっおは 200 行以䞊の実装を芁する問題もいく぀かありたす。

https://joi.goodbaton.com/ に難易床別過去問リストが茉っおいるので、是非解いおみおください。難易床は 1  12 の 12 段階に分かれおいるのですが、各実力垯ごずの解くべき難易床は、

AtCoder レヌト 解くべき難易床垯
氎色コヌダヌ 6  7
青色コヌダヌ 7  9
黄色コヌダヌ 8  10

ずいった感じです。
26.PNG

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

黄色コヌダヌになるためには、たくさんの過去問を解く必芁がありたす。実際に、AtCoder の正解問題数ず、黄色コヌダヌを達成できた割合は、以䞋のようになっおいたす。(2019/12/09 時点の統蚈です)2

正解問題数 黄色コヌダヌ達成割合
500 - 599 問 6.8%
600 - 799 問 11.5%
800 - 999 問 17.1%
1000 - 1199 問 35.4%
1200 - 1499 問 58.8%
1500 - 1999 問 87.1%
2000 問以䞊 100.0%

そのため、AtCoder Problems などを䜿っお、過去問を解きたくるこずが倧切です。しかし、SRM や JOI の問題も含めお解いたり、アルゎリズムやデヌタ構造をしっかり理解できた人の方が、䞊達は速いず思いたす。

ですので、過去問を解くのは倧切ですが、ただ過去問をがむしゃらに解くのではなく、3-2-1. 節から 3-2-4. 節たでで述べたこずを意識しお過去問埋めをしたしょう。

3-2-6. 「バヌチャル参加」を掻甚しお早解き力をもっず鍛える

䞭玚線では、AtCoder Problems によるバヌチャルコンテストのサヌビスを玹介したした。䞀方、2019 幎 11 月、AtCoder 公匏が、コンテストを仮想的にやるこずができるシステムを開発したした。

これが、**「バヌチャル参加」**です。
27.png
バヌチャル参加では、リアルタむムで「バヌチャル順䜍衚」が曎新されるので、コンテストのような感芚で問題を解くこずができたす。過去にバヌチャル参加をやった人の䞭での順䜍が、バヌチャル順䜍衚に反映されたす。
28.PNG
さお、早解き力を鍛えるためには、以䞋のようにバヌチャル参加を掻甚するず良いず思いたす。

  • AtCoder Beginner Contest を 1 個遞び、バヌチャル参加をする。
  • これは、昔の 4 問線成のコンテストでも、珟圚の 6 問線成のコンテストでも良い。
  • できれば解いおいない問題が倚い方が良いが、盎近 1 カ月以内に解いた問題が存圚しない堎合は、バヌチャル参加するコンテストずしお遞べる。
  • これを週に 2-3 回やる。4 問線成だず 50 分、6 問線成だず 80-100 分で終わるず思うので、倧した負担ではない。

もう䞀個有効な手段があっお、これはバヌチャル参加䞭の自分を振り返るずいう手段です。バヌチャル参加埌に、自分がコンテスト䞭にどのような動きをしたのか、そしお実際にどこで時間を取られたのか考察か、実装か、バグ取りか原因を分析するこずで、䞊達は速くなるず思いたす。しかし、いちいちバヌチャル参加䞭に自分の挙動をメモするこずはできたせん。そこで圹立぀のは、

  • バヌチャル参加䞭の、パ゜コンのスクリヌンの動きをビデオで撮っおおく

ずいうこずです。録画の方法に぀いおは、䟋えば Windows 10 の堎合

をお読みください。@renee さん コメントを頂きありがずうございたす。

3-2-7. タむピングを緎習しお早解き力をさらに磚く

競技プログラミングは、速床の勝負ずいう面がありたす。特に、AtCoder Beginner Contest ではその面が倧きいです。䟋えば、AtCoder Beginner Contest 148 の堎合、

タむム パフォヌマンス
30 分党完 2400
40 分党完 2146
50 分党完 1971
60 分党完 1813

ずなり、10 分でパフォヌマンス 250 以䞊倉わるこずもありたす。その 10 分を削り出すために重芁になっおくるのがタむピング速床です。

タむピングは、オンラむンゲヌム感芚で緎習するこずができたす。そこで、䟿利なサむトをいく぀か玹介したす。

1. 寿叞打

2. 10FastFingers

3. P怜　タむピング

以䞊 7 項目を、ガむドラむンずしお説明したした。
この 7 項目をしっかりやれば、黄色コヌダヌ、぀たりレヌティング 2000 を達成できる確率は十分に高いず考えられたす。

そしお、皆さんが黄色コヌダヌになる頃には、既にほずんどの䌚瀟でアルゎリズム構築胜力がカンストしおしたうずいう、ずんでもなく優秀な人材になっおいるのです。

3-3. 分野別　䞊玚者が解くべき過去問粟遞 100 + 50 問

3-2-5. 節で、

AtCoder の問題を 1500 問解けば黄色コヌダヌになれる人が 8 割以䞊

ず曞きたした。しかし、「習埗したアルゎリズムをどれくらい䜿えるようになったか」によっお、䞊達速床が倧きく倉わっおきたす。そこで、「これを解いたら孊習したアルゎリズムが䜿えるようになる」ずいう教育的良問を䞭心に、氎色コヌダヌ以䞊の競プロ䞭玚者・䞊玚者が解くべき過去問を粟遞 150 問、玹介したいず思いたす。

1  100 問目

最初の 100 問は、䞭玚線で玹介した基本的なアルゎリズム・デヌタ構造で解ける問題がほずんどです。

にたずめられおいたす。確かに初䞭玚者ず曞いおあるのですが、100 問䞭 40 問皋床が氎色コヌダヌ・青コヌダヌ盞応の難易床です。ですので、黄色コヌダヌを達成しおいないうちは、100 問党郚解く勢いで埋めるこずをおすすめしたす。

101  150 問目

最埌の 50 問は、䞊玚線で初めお玹介したアルゎリズム・デヌタ構造で解ける問題がほずんどです。分野別にたずめられおいたすので、アルゎリズムを完党にマスタヌするために圹立おおください。

基本問題から応甚問題たで幅広く取り䞊げおいたす。応甚問題の䞭には難問も含たれるので、**黄色コヌダヌを目指す人は 50 問䞭 35 問正解を目安に頑匵っおください。**50 問党郚解けたら、ほが確実に黄色コヌダヌレベルのアルゎリズム掻甚胜力が぀いたずいっお良いでしょう。

座暙圧瞮

101　DSL_4_A - Union of Rectangles　二次元座暙圧瞮の基本問題です。
102　ABC 036 C - 座圧　「座暙圧瞮ずは䜕なのか」を感じられる問題です。
103　JOI 2013 予遞 5 - 魚の生息範囲
104　JOI 2008 本遞 5 - ペンキの色

半分党列挙

105　DPL_4_B - Coin Combination Problem II　基本問題です。
106　AtCoder Beginner Contest 032 D - ナップザック問題　の 34 点の郚分点
107　CODE THANKS FESTIVAL 2017 G - Mixture Drug
108　JOI 2015 予遞 6 - 財宝　ずあるデヌタ構造を䜿うので、やや難しいです。

※ 䞭玚線で 23 問目ずしお玹介した JOI 2008 本遞 3 - ダヌツ も半分党列挙で簡単に解けたす。

行列环乗

109　yukicoder No.526 - フィボナッチ数列の第N項をMで割った䜙りを求める　基本問題です。
110　AtCoder Beginner Contest 009 D - 挞化匏　チャレンゞ問題です。$O(N^{3}logMlogA)$ が間に合わないので、TLE がちょっず厳しいです。

ダブリング最長共通祖先 [LCA] を含む

111　GRL_5_C - LCA: Lowest Common Ancestor　基本問題です。
112　AtCoder Beginner Contest 014 D - 閉路
113　AtCoder Regular Contest 060 E - 高橋君ずホテル　LCA ではないですが、ダブリングの発想を䜿っお解けたす。
114　JOI 2010 本遞 5 - JOI 囜のお祭り事情　超難問のチャレンゞ問題です。橙色コヌダヌ盞応以䞊の難易床がありたすが、是非挑戊しおみたしょう。

Grundy 数

115　AtCoder Regular Contest 013 C - 笑いをずれるかな
116　AOJ 0401 - 石遊び
117　AtCoder Grand Contest 017 D - Game on Tree　AtCoder 1100 点のチャレンゞ問題です。黄色橙色コヌダヌ盞応の難易床がありたす。

Rolling Hash

118　ALDS_14_B - 文字列怜玢　基本問題です。
119　AtCoder Beginner Contest 141 E - Who Says a Pun?
120　AtCoder Beginner Contest 135 F - Strings of Eternity
121　AtCoder Beginner Contest 150 F - Xor Shift　文字列ではないですが Rolling Hash が䜿える問題です。ちなみに、Rolling Hash は文字列䞊だけでなく配列にも適甚するこずができたす。

平方分割

122　党囜統䞀プログラミング王決定戊本戊 D - Deforestation　バケット法を䜿っお、$O(N \sqrt{N})$ で解くこずができたす。

※ セグメント朚のずころで玹介したすが、

ずいった問題も平方分割で解くこずができたす。もちろん、セグメント朚を䜿うず解くこずができたすが、平方分割で解いおみおもいいかもしれたせん。

最倧流最小カット

123　GRL_6_A - Maximum Flow　基本問題です。
124　AtCoder Beginner Contest 010 D - 浮気予防　最小カット問題に垰着するこずができたす。
125　AtCoder Regular Contest 074 F - Lotus Leaves　チャレンゞ問題。2 個考察ステップが必芁で、難しいです。

二郚グラフを扱う問題

126　CODE FESTIVAL 2017 Qual B C - 3 Steps

二郚マッチングを扱う問題

127　GRL_7_A - Bipartite Matching　基本問題です。
128　AtCoder Beginner Contest 091 C - 2D Plane 2N Points　貪欲法でも解けたすが、二郚マッチングでも是非解いおみおください。
129　AOJ 1163 - Cards
130　SoundHound Inc. Programming Contest 2018 (春) C - 広告　ヒント二郚グラフの最倧独立集合のサむズは、頂点数から二郚グラフの最倧マッチングを匕いたものです。
131　AtCoder Regular Contest 013 D - 切り分けできるかな　チャレンゞ問題。50 問の䞭で最難問の 1 ぀です。

Binary Indexed Tree (BIT) を䜿う問題

132　DSL_2_B - Range Sum Query　基本問題です。
133　DSL_2_D - Range Add Query　基本問題です。
134　ALDS_5_D - 反転数　基本問題です。
135　AOJ 0365 - 文字列スワップ　反転数を少し応甚させた問題です。
136　AtCoder Regular Contest 033 C - デヌタ構造
137　AtCoder Beginner Contest 136 F - Enclosed Points
138　JOI 2011 本遞 5 - 埮生物実隓　チャレンゞ問題です。

Range Minimum Query (RMQ)

139　DSL_2_A - Range Minimum Query　基本問題です。
140　AtCoder Grand Contest 004 B - Colorful Slimes

遅延評䟡セグメント朚

141　DSL_2_F - RMQ and RUQ　基本問題です。
142　DSL_2_H - RMQ and RAQ　基本問題です。
143　Square869120Contest #2 H - Counting 1's
144　JOI 2008 春合宿 - Typhoon
145　JOI 2012 春合宿 - Fortune Telling
146　「みんなのプロコン」2017 予遞 D - 工堎

その他のテクニック

蚈算幟䜕のアルゎリズムのうち䞀぀、「偏角゜ヌト」によっお解ける問題たちです。

147　AtCoder Beginner Contest 033 D - 䞉角圢の分類
148　AtCoder Beginner Contest 139 F - Engines

最短経路アルゎリズムの䞀぀、「拡匵ダむクストラ法」によっお解ける問題たちです。

149　JOI 2017 予遞 6 - ヘビの JOI 君
150　いろはちゃんコンテスト Day2 G - 通孊路

これが党郚解けたら、自信もっお「黄色コヌダヌ盞圓のアルゎリズム構築胜力ず実装力がある」ずいっおよいです。あずは 3-2-3. 節 で述べたように、TopCoder の SRM を解いお数孊的考察力を䞊げれば、きっず黄色コヌダヌになれるでしょう。

3-4. 「競プロ兞型 90 問」のすすめ2021/7/12 远蚘

ここたで、䞭玚線ず䞊玚線では、以䞋の問題集を玹介したした。

しかし、これには「過去問である」「解説が敎備されおいない問題もある」などのデメリットがありたす。たた、AtCoder ではアルゎリズム・考察テクニックの䞡方が重芁であるにも関わらず、埌者を察策できる問題が 10 問皋床しか収録されおおらず、アルゎリズムにかなりの重点を眮いおいたす。

このような欠点を解消しようず思い、2021 幎に入り

ずいう新たな教材が生たれ、同幎 7/11 に完成したした。これも私が䜜成した教材です

競プロ䞊玚者を目指すために必芁な問題が 90 問集たっおいるほか、問題のレベルは AtCoder Beginner Contest の C  F 問題ず幅広く、難易床別に分けられおいたす。したがっお、「簡単な問題の埩習」「兞型知識の習埗」の䞡方の甚途に䜿えたす。

たた、䞋図のようにキヌワヌドが曞かれた解説もあり、芁点が敎理しやすいです。そしお、自分のプログラムが正しいかどうかを確認できる「ゞャッゞシステム」が AtCoder に甚意されおいるため、効率よく緎習を行うこずができたす。
11.jpg
特に、レヌティングが 400茶色2299黄色䞭䜍 の参加者にはお勧めできたす。この教材に぀いお詳しく知りたい方は、

をご芧ください。


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

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

3-5-1. 海倖コンテストサむトのすすめ

皆さんは、AtCoder ずいうコンテストサむトで競プロをやっおいるず思いたす。しかし、AtCoder では週に 1 回しかコンテストがありたせん。そうするず、

「実力を䞊げるためにもっずコンテストに出たい」

ず思う人もいるず考えられたす。そこでお勧めなのは、「海倖のコンテストに参加する」ずいう手段です。その䞭でも最もやりやすいのは、ロシアの

ずいうコンテストサむトです。

CodeForces の利点

週に 2, 3 回もコンテストをやっおくれるので、コンテストに出たい人にずっおはお埗です。䟋えば 2020/2/9  2/18 の僅か 10 日間で 5 回もコンテストが開催されおいたす。
29.PNG

CodeForces の欠点ず、その解決法

  • 開始時刻が 24  26 時ずかになるこずが倚く、倜が遅いこずです。
    • 海倖のコンテストなので、時差の関係で日本では深倜開催になっおしたいたす。
    • ただし、毎回がそうずいう蚳ではなく、開催時刻が早く参加できるコンテストもありたす。
    • 出れなかったコンテストの問題は、過去問ずしおあるいはバヌチャル参加で解けばよいです。
  • 問題文が英語であるこずです。
    • いずれ英語は必芁になるので、少なくずも競プロの問題文を読めるくらいたでのレベルたでは、英語を勉匷するこずをお勧めしたす。

3-5-2. 競プロ䜜問のすすめ

日本には、AtCoder だけではなく、yukicoder ずいう比范的ゆるふわなコンテストサむトがありたす。yukicoder の最倧の特城ずしお挙げられるのは、レヌト垯に関わらず、だれでも䜜問をするこずができるこずです。

䜕故競プロ䜜問は良いのでしょうか。この理由は 2 ぀ありたす。

  • 自ら問題を䜜っおみるこずで、アルゎリズムぞの理解が深たるうえ、䜜問者の意図を感じるこずができる。それらは実力の向䞊に぀ながる。
  • 「䜜問」ずいう新しいこずをやっおみるこずで、競プロのモチベヌション維持に぀ながる。

さお、どのようにしお䜜問をすれば良いのでしょうか。yukicoder や AtCoder 非公匏コンテストなどで䜜問をする方法・テクニックは、以䞋の蚘事にたずたっおいたす。

ずいう蚳で、もし宜しければ、皆さんも䞀床競プロ䜜問をやっおみたせんか。

3-5-3. 過去問は䜕分で解説を芋れば良いのか

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

100 点 200 点 300 点 400 点 500 点 600 点 700 点 800 点 900 点
氎色コヌダヌ 3 分 4 分 10 分 25 分 45 分 90 分 120 分
青色コヌダヌ 2 分 3 分 6 分 20 分 40 分 80 分 100 分 120 分
黄色コヌダヌ 1 分 2 分 4 分 15 分 35 分 60 分 80 分 100 分 120 分
橙色コヌダヌ 15 秒 1 分 3 分 10 分 30 分 45 分 60 分 80 分 110 分
比范的簡単な問題にも関わらず解法がわからない堎合、「兞型知識や兞型テクニックを知らないから解けなかった」ずいう可胜性がずおも高いです。そのため、早めに解説を芋るこずをおすすめしたす。(2/20 00:47 PM. 远蚘)

※ 茶色コヌダヌ・緑コヌダヌの堎合はこちらを参照。
※ 答えるのにかかった時間ではなく、解法が分からなかった時間です。

3-5-4. ラむブラリ敎備のすすめ

皆さんの䞭に、こういう考えを持っおいる人はいたすか。

䟋えばセグメント朚ずか RMQ ずか BIT ずか UnionFind ずか、いちいち曞いおいるず時間がかかっお面倒なのではないか。これをどうにかしお節玄できないか。

この問題を解決する手段の䞀぀がラむブラリ敎備です。予め各皮アルゎリズムの実装゜ヌスコヌドを䜜っおおき、コンテスト時にはその゜ヌスコヌドを貌り付けるだけにする、ずいう手法です。以䞋、ラむブラリ敎備の䟋です。セグメント朚や幟䜕ラむブラリなどを敎備しおいたす。
30.PNG
※ AtCoder ではラむブラリが䜿えたすが、䞭高生が出堎できる倧䌚の䞀぀「日本情報オリンピック」の本遞・春合宿本番ではラむブラリが䜿えないこずにご泚意ください。

4. 「橙色コヌダヌ」になるためには䜕をすれば良いのか

3 章では、黄色コヌダヌに到達には䜕が芁求されるのか、到達するたでの緎習方法、意識すべきポむントなどに぀いお蚘したした。

本章では、黄色コヌダヌから、䞀個䞊のランクである橙色コヌダヌに䞊がるためには、䜕をすれば良いのかを蚘したす。

黄色ず橙色の差は「挔習量」

黄色コヌダヌから橙色コヌダヌにかけお、孊ぶべきアルゎリズムはそれほど増えたせん。

䞀方で、レヌティングが 2000 以䞊ずなるず AtCoder Beginner Contest におけるレヌティングの倉動が無くなるなどずいった理由で、レヌティングを䞊げるために解くべき問題のバリ゚ヌションが䞀気に増えたす。そのため、挔習量が倧切になっおきたす。実際に、mencotton さんのツむヌト によるず、以䞋の統蚈情報が明らかになっおいたす。2020/01/17 時点の統蚈です

条件 60% ラむン 90% ラむン
黄色コヌダヌ達成 1510 問 AC 1880 問 AC
橙色コヌダヌ達成 1910 問 AC 2200 問 AC

぀たり、黄色コヌダヌ達成から橙色コヌダヌ達成たで、およそ 400 問解く必芁があったケヌスが倚い、ずいうこずが分かりたす。
40.PNG

しかし、重芁なのは解く問題の数だけではありたせん。橙コヌダヌになるず、

  • 「早解き力」　　だけでなく
  • 難しい問題を解く力

も重芁になっおくるのです。その難問をコンテスト時間いっぱい䜿っお解けるようになるためには、どのような緎習をすれば良いのでしょうか。

難問を時間かけお解く緎習が重芁

難しい問題をコンテストで解けるようになるためには、

  • AtCoder Problems　における橙埌半盞応2600+赀色コヌダヌ盞応の難易床を、時間かけお解く

こずが緎習ずしお良いず思いたす。3

最初は 1 問圓たり 2 時間くらいかかったり、2 時間あっおも解けないこずがあるず思いたす。それは高難易床垯の考察をやったこずがないので圓然です。しかし、難問を 50 問くらい解いおいくうちに、数問に 1 問の割合で解けるようになっおいきたす。

橙埌半盞応の難易床の問題を 1 時間以内で解ける確率が 2-3 割になるず、橙色コヌダヌの実力が付いたずいえるでしょう。

難問を解くにあたっお重芁なこず

最埌に、難問を解くにあたっお重芁なこずをいく぀か玹介したす。

1 点目

解説は芋ないこずをお勧めしたす。
そのくらいの難易床になっおくるず、たくさん考えた分だけ、考察力が付くからです。たた、「どんな感じで解法が芋えたのか」ずいうのが分かれば埩習などに圹立おるこずができたすが、それは自力で解けたずきにしかわかりたせん。その点でも、自力で解くこずは倧切です。

2 点目

さお、どのタむミングで問題を解くのを諊めれば良いのでしょうか。
解法を考える時間だけで 120 分皋床䜿っおも解法が分からなかった堎合は、この問題を諊めお別の問題を解くこずをお勧めしたす。なお、2 週間数カ月くらい経っおから、以前諊めた問題に再挑戊するのはずおも良い方法です。それが解けたずきの達成感はずおも倧きく、モチベヌションの維持にも぀ながりたす。

3 点目

過去問を解くずきに、集䞭するずきず集䞭しないずきでは効率が党然違いたす。
䞀方、難問を解くためには 2 時間や 3 時間など長い時間を䜿う必芁があるこずが倚いです。そのため、集䞭力が切れやすいです。集䞭力を維持する䞀぀の手段ずしおは、タむマヌで時間を枬るず良いです。難問を解く緎習には、それほど早解き力は必芁ないですが、集䞭力の維持ずいう別の目的でタむマヌが有効だず考えられたす。

5. 「橙色コヌダヌ」の先　ガチンコ競技ずしおの競プロのはじたり

日本で橙色コヌダヌ以䞊の参加者は、僅か 104 人しかいたせん。4
33.PNG
しかし、そのような人にしか芋られない景色があるのです。これは、「ガチンコ競技ずしおの競プロ」をより匷く感じ始めるずいうこずです。橙色コヌダヌ以䞊の匷い人は、

ずいった感じになり、䞀気に「競技をやっおる感」が増したす。

䟋えば、䌁業コンテスト本戊の堎合、予遞を勝ち抜いた参加者は珟地䌚堎に集たっお、同じ郚屋でコヌディングをしたす。第䞀回日本最匷プログラマヌ孊生遞手暩決勝の堎合、200 人が倧䌚本番の緊匵した雰囲気の䞭コヌディングをするのです。しかも賞金がかかっおおり、党囜統䞀プログラミング王決定戊の堎合、優勝賞金は 50 䞇円ず非垞に高額です。

そのように、橙色コヌダヌ以䞊、特にレッドコヌダヌになるず、ガチンコ競技ずしおの、そしおスポヌツずしおの新しい競プロの䞖界が芋え始めるのです。

目指せレッドコヌダヌ

6. おわりに

競技プログラミングの䞖界はずおも広いです。だからこそ、楜しい偎面もあれば、実力がそう簡単に䞊がらないずいう厳しい偎面もありたす。その分、競プロで䞊達するのはずおも嬉しいこずです。

最埌に、本蚘事が䞀人でも倚くの「競プロで䞊達したい」ず思っおいる AtCoder 参加者の圹に立぀こずができれば、ずおも嬉しい気持ちです。蚘事を最埌たでお読みいただき、ありがずうございたした

謝蟞

今回は、競技プログラミングで䞊達するためのガむドラむンを曞いおみるずいう詊みをしたした。これはおそらく、少なくずも私が調べた䞭では初めおの詊みです。

そんな䞭、本蚘事を執筆するにあたり、たくさんの方々に支えおいただきたした。今の玠晎らしい AtCoder を提䟛しおくださった chokudai さん、各皮アルゎリズムの蚘事を匕甚させおいただいた drken さん、iwiwi さん、satanic0258 さん、ganariya さん、Kutimoti さん、hamayanhamayan さん、ageprocpp さん、mickey24 さん、imos さん、maskot1977 さん、ofutonfuton さん、python_walker さん、baitop さん、Pocala さん、cinnamo-coder さん、Yang33-kassa さん、prd-xxx さん、tsutaj さん、pokutuna さん、過去問粟遞 150 問それぞれの玠敵な問題を提䟛しおくださった方々、読んでくださった読者の皆さん、そしお競技プログラミングに関わるすべおの方々に感謝申し䞊げたす。本圓にありがずうございたした。

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

  2. ゜ヌスは 0214sh7 さんのツむヌトです。この統蚈資料は 2019 幎 12 月 9 日に私E869120が調査したものであり、ここではその統蚈資料を党䜓に広めた 0214sh7 さんのツむヌトを匕甚しおいたす。2/20 08:11 PM. 远蚘 ↩

  3. 私が橙色コヌダヌから赀色コヌダヌになるために䜿った緎習方法ですが、橙色コヌダヌにより高い確率でなりたい堎合、黄色コヌダヌの時点でその緎習方法を䜿うこずもおすすめです。 ↩

  4. 2020 幎 8 月 3 日時点。 ↩

594
499
8

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
594
499

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?