はじめに
AtCoderを始めて約4ヶ月、何とか茶色コーダーになれました!!
この記事では、実際にやってきたことや茶色になるまでに何を考えてきたかをまとめました。言語はC++です!
1.AtCoderを始める前のスペック
大学は工学部に所属していますが、情報系ではないためアルゴリズムやプログラミングについての知識は全くありませんでした。数学も高校時代は苦手科目でした。
2.AtCoderを始めたきっかけ
この動画に出会ったことがAtCoderを始めるきっかけになりました。動画を見たときは「初心者が無料でプログラミングの勉強をできるサイトがあるらしい」くらいにしか思っていませんでしたが、問題を解いているうちにハマってしまいました。なんとなく、「プログラミングできるのって面白そうだな」と思っていたのでこの動画に出会えてラッキーでした。ちなみに、このときまでまったく競技プログラミングの存在を知りませんでした。
3.茶色になるまでにやったこと
1.APG4bを読む
はじめに3章まで軽めに読んで、問題を解きながら何度も見返すという使い方をしていました。いまのところC++の教材はこれで十分です。
2.AtCoder Problemsで過去問を解く
A,B問題の精進 (1~2ヶ月目)
AtCoderを始めて1,2ヶ月目はA,B問題の精進をしていました。ここでAPG4bの1章、2章の内容をある程度使えるようになりました。
いま思うと、少しここに時間をかけすぎてしまったと感じており、慣れてきた時点でC問題に挑戦し始めたほうが効率良かったと思います。
C問題 灰diffの精進 (2~3ヶ月目~現在)
最初はC問題を最新のものから順に埋めていこうとしていたのですが、とても難しく感じたのでdiffが低いのを選んで解いていました。それでもB問題と比べるとかなり問題が難しく、ほとんど解説放送を見てACしていました。
C問題 茶diffの精進 (3ヶ月目~現在)
灰diffが7割ぐらい解けるようになってから始めました。今の自分のレベルより少し上がC問題の茶diffだと感じていて、自力AC率は30%ぐらいです。解けたときはすごく嬉しいです。解説の内容を理解することにすごく時間がかかることがあります。
3.鹿本をやる (2~3ヶ月目)
なぜか学校の図書館にあったので借りてやってみました。中級編まで読み、練習問題を解きました。全探索、連想配列、グラフ、累積和などを学びました。ジャンルごとに練習問題が15問ほどあるので知識の定着に活かせました。
4.アルゴ数学本をやる (3~4ヶ月目)
数学に苦手意識があったので購入しました。難易度が☆1~5まであり、☆4までの問題をすべて解きました。数学の幅広いジャンルを学べました。とくに逆元や素数、数学的考察についてかなり勉強になりました。C問題よりもD,E問題、典型90で本領を発揮する内容だと思ったので今後、この本を読んだ効果がより出てくると思います。
5.AtCoder Daily Training (EASY)にでる (4ヶ月目~現在)
精進がマンネリ化してきたときに始めましたが、めっちゃやってよかったです。A,B問題に時間をかなりかけていることや一度解いたC問題を解けないことがあり、自分の弱さに気づくことができました。今後も定期的に参加していくつもりです。いつか1位をとりたい!
以上が私が入茶するまでにやってきたことです。
どれか一つが入茶の決め手になったというよりは、いくつかの教材をやることで理解が深まり、入茶できたような気がしています。最後に私のAtCoder Problemsのリンクを貼っておくので気になる方は見てみてください。 japaneseotaku
4.入茶するにあたって大事だと思うこと、気づいたこと
1.C問題は与えられた制約が大きなヒントになっている
最近ようやく「計算量を意識する」という言葉の意味を理解できるようになってきました。
C問題は計算量を問う問題であることは知っていましたが、「二重ループにならなければいいのかな」ぐらいにしか考えていませんでした。そのため、問題を解く時にどのようなアルゴリズムとデータ構造を使えばよいのか頭の中でうまく整理できていませんでした。しかし、それぞれのアルゴリズム、データ構造の計算量を知ってからは制約を見て、ある程度解法を予測できるようになりました。例えば、問題を見ても解法がわからなかったとき、問題の制約上O(N^2)が使えなくて、O(NlogN)やO(N)が可能ならば二分探索や累積和が使えないか考えてみるというように、どうしたら与えられた制約の上で計算量を最大限活かせるかを考えることで解法が見えてくるということがありました。多くの人にとっては当たり前のことだったかもしれませんが、この発見をしてからC問題を解けることが多くなりました。
2.全探索をないがしろにしていた
C問題を解き始めたとき、はじめから全探索を考えないようにしていました。なぜか頭の中で全探索と他のアルゴリズムをわけて考えてしまっていました。しかし、全探索で解ける問題もありますし、全探索を考えてみることでどのような工夫が必要かわかることもあることに気づきました。これも当たり前のことかもしれませんが、全探索も探索アルゴリズムのひとつであるという意識は大切だと思います。
3.問題を読んだときに適切な図やグラフ、数直線などをイメージできるようにする
けんちょんさんのブログ記事や解説放送、前述したアルゴ数学本に出てくる図解が非常にわかりやすく、おそらく猛者の方々は問題を読んですぐに具体的なイメージや図が頭の中に浮かんでいるのだろうと思います。私はまだうまく適切な図などを具体的にすばやくイメージできませんが、これを意識するようになってから問題を解く速度は上がりました。また、紙(ペイントソフト)に書き出すこともしています。
4.式をとりあえず変形してみる
解説を見たら式変形をしているだけなのに、問題を解いてる最中は全く解法がわからないということが何回かありました。原因はおそらく、なんのアルゴリズムを使うかということばかり考えていたからです。いまは式を見たらとりあえず色々といじってみるようにしています。
5.FAQ
1.問題の解き方どうしてた?
問題を数分みて解法がわからなかったら解説みるというやりかたが主流っぽい?けど、私は「もうちょっと考えたい!解けないの悔しい。」ってなるタイプだったので考察にかなり時間をかけていました。(長いときだと1時間半ぐらい。)上級者にもいろんなタイプがいるようなので、自分にあう解き方で良いと思います。
けんちょんさんのTwitterより引用解説 AC は思想別れるイメージ
— けんちょん (@drken1215) July 22, 2020
・ちょくだいさん:解説 AC ドンドンしないと効率悪い
・evima さん:(AtCoder の得点) /20 分考えて取っ掛かりも掴めなかったら解説見るべき (500 点なら 25 分)
・Rubikun さん:知識ゲーと思ったら解説 AC する
・E8 君:解説 AC はせずに自分で考えることが大切
2.精進にAIは利用していますか?
学生が無料なので、Geminiを使っています。
使い方は、難しい問題にあたって解説みても理解が怪しい時、コードに直接自分なりの解説を書き込んだものをGeminiに投げて、自分の考え方が正しいか判定してもらったりしてました。あとは、Geminiがしてくれた解説に対して、「それってつまりこういうことですか?」と自分なりの言葉で言い換えてちゃんと理解できているか確認するなどしていました。
3.早解きは考えていますか?
いまは早解きより解ける問題を増やすことを優先しています。早解きできることはとても重要ですが、茶色になるために一番大切なことはC問題を解けるようになることだからです。最速2完は最遅3完より順位が高くなることはありません。また、今後は4完を目指そうと思っていて、4完を目指すことで、アルゴリズムやデータ構造の理解が深まり、ある程度までは自然に早解きできるようになると考えています。
6.今後やるべきこと
次の目標は緑色コーダーになることです!
そのためにできそうなことをいくつか考えてみました。
-
C問題の精進を続ける
- 確実に早くACできるようにするため。
-
EDPCを解く
- 4完,5完を目指す上で必ずDPが必要になるから。
- C問題で必須の内容ではなくほとんど触れてこなかったから
-
けんちょん本を読む
- D,E問題を解くために必要な基本的なアルゴリズムとデータ構造の理解を深めるため。
-
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】の2-3. 分野別 初中級者が解くべき過去問精選 100 問を解く
- 実力より1、2段階上の問題、アルゴリズムを知るため。
-
正規表現を学ぶ
- 他の言語にも使えて便利そうだから。優先度は低め。
-
競プロ典型 90 問の★4以下を解く
- 考察力をつけるため。
- 過去問だけだと飽きそうだから。
7.おまけ 言い残したこと
環境構築をえびまさんの動画で行いました。とてもわかりやすい内容でスムーズに環境構築できました。えびまさんありがとうございます。
【競技プログラミング】プログラミング初心者がAtCoderを始めて10か月で水色になった方法【ゆっくり解説】は最近AtCoderを始めた人全員に見てほしい、というか公式で紹介してほしいぐらい役に立つ内容で、私はこの動画で言われていることを実践して入茶することができました。この動画で紹介されている内容に大きく逸れることをしなければほとんどの人は上達できると思います。Frestさんありがとうございます。今後も参考にさせていただきます。
やってよかったこと
-
拡張機能を入れる
AtCoderには便利で面白い拡張機能がたくさんあります。拡張機能を入れることで効率的になったりよりAtCoderを楽しめたりするので導入することをおすすめします。
-
Twitterのアカウントを作る
- 当初、作る気はありませんでしたが、Twitterをやることを勧めている上級者の方が多かったので作ってみました。
- いまのところ作ってよかったです。勉強熱心な方や似たようなレート帯の方が精進しているのをみて、勉強意欲が湧くことが多かったです。
-
マクロを使う
- 【競技プログラミング】真似するだけでコーディングが爆速になるマクロ27選【ゆっくり解説】を参考にしました。非常に役に立っています。また、猛者の方のコードを見に行くといろんなテンプレがあって面白いです。何が書いてあるのかよくわからないことも多いですが。
雑なアドバイス
コンテストの日は昼寝をして眠いままコンテストに参加しないようにした方が良いです。私が大きく盛れた日はよく眠れた日でした。考察は紙やペイントソフトに書き出したほうが良いです。私は解説放送の書き方を参考にしました。グラフを作成するサイトを使う方もいるようです。私はまだ使ったことがありません。
Union-Findとラムダ式は使えなくても茶色になれると思いますが少しでも使えるととても便利です。
私ははじめ必要十分条件、コーナーケース、配列のインデックスを考えることが苦手でしたが、ある程度問題を解けば慣れると思います。
あと、気分が落ち込んだときは、AtCoderの実況動画を見てました。面白い動画が多いし、他の人が問題を解く姿を見ることで発見できることがあるかもしれないので暇があれば見たほうがよいと思います。個人的にはAtCoderのボイロ実況者もっと増えてほしいです。
8.最後に
正直なところ、茶色になれたのは相性のよい問題が何週間も連続で出てからだと思います。Cの精進をしていて、まだまだ解けない問題に出会うことが多く、灰色に落ちそうで怖いです。
また、緑コーダーになったらまた再度記事を書きたいと思います。次はもう少し可読性の高い記事を目指して精進しようと思います。
うまくまとめられず無駄に長い記事になってしまいましたが、ここまで読んでいただきありがとうございました。