はじめに
初めまして。shirogane1234と申します。
この度先日開催されたABC440にて当初の目標としていた入緑を達成しました。
これから様々な役に立つ情報や経験をまとめてみたいと思ったので、その第一歩として色変記事というものを書いてみようと思います。
こういった記事を書くのは初めてであるため読みにくいところ等あると思いますが楽しんで読んでいただけると嬉しいです。
目次
目次
簡単に自己紹介
競プロ歴1年に満たないただの高校2年生です。
競プロ界隈の高校生はやたらと凄い人ばっかりいますがそんなことは無く本当に平凡に競プロを楽しんでいる人です。
AtCoderを始めるまではプログラミング経験なんてものは全くありませんでした。
言語に関してはC++でやっています。最初はPythonを勉強してましたが1週間で捨てました。
入茶時点ではC問題の打率が6割程度とまあ普通の茶色ぐらいだと思います。
入緑までにやったこと
この記事の本題です。
精進
みんなやっています。私ももちろんやりました。色変に必要なことの9割がこれといっても過言ではありません。
私の精進は質より量派なので(もちろん質も量もあった方が良いですが)、入緑当時のProblemsのAC数は結構少ない部類だと思います。
streak繋ぎのA問題で60問ぐらいかさ増してるので実際の精進量はもっと少ないです。
ここからは精進で具体的にやったことを紹介していきます。
APG4B
茶色になるまでは少し怪しかった3章をちゃんとやりました。構造体だけ読んでないですがclassとほぼ同じらしいので何の問題もありませんでした。
それに加えてテンプレートの部分だけセグ木の一般化に必要だったので別でやりました。
鉄則本
買いました。以上です。
一応目は通しましたが実装に関しては二次元累積和ぐらいしかやってません。
必要になったら引っ張り出してきてやろうのスタンスで生きてます。
EDPC
DP超絶苦手人間なのでやろうと思いましたがDP超絶苦手人間だったのでEまでしかやりませんでした。なのでナップサックDPすら少し怪しいです。
C,Dに超頻出なので普通の人間なら絶対やった方がいいです。
ABC過去問/バチャコン
ABC過去問に関しては基本的にstreak繋ぎの一環としてやってました。ちゃんと精進しようと思ったときは基本的にバチャを回してます。
Atcoder Problemsからdiffだけ見て身の丈に合った問題を適当にピックするか、バチャガチャを回すかのどっちかでやってました。
問題の選び方の関係上浅く広い知識が身につくのでC,D問題の打率を上げたい人にはまあまあいいと思ってます。
ABCのupsolve
真面目に精進してこなかった私にとってほぼ唯一の実力向上手段でした。
結局コンテスト中に悩んでAC、分からなくても解説を見て納得して解説ACするのが一番力になります。
JOIの過去問
精進としてやることはあまりなかったですが、JOI2次に向けてやってた時期がありました。
難易度7以上は結構勉強になると思います。
おまけ
Codeforces
18:05~など日本人に人権があるタイプのこどふぉには出ました。ちなみに計2回しか出られてません。
ABCとは方向性が少し違い、考察要素が少し多めです。知識があまり必要なく結構楽しいので人権有りのコンテストに出ることはおすすめです。
Paiza
AtCoderユーザーにとっては簡単めな問題が結構集まってます。
早解きの練習としてちょうどいいくらいだと思います。
やらなかったもの
ADT
バチャコンでよくね？と思っていたのでやってませんでした。
高校が早く終わった日とかにはたまにやっていました。
Novisteps
自分でAC,解説ACなどつけるところや、一つのアルゴリズムの問題集的な使い方がされているイメージが私には合いませんでした。
特に後者は私の精進のやり方と真逆なので...
典型90
典型ならある程度は大丈夫だろうという慢心からやりませんでした。
茶色になれてるならCまでの頻出典型は一通り押さえているだろうし、E問題はやってもどうせ解けないので、D問題の知らない典型を死ぬ気で通す方が典型問題としての定着度は高いと思います。
ただ自分の色+1色分ぐらいの典型90は普通にやった方が良いです。
ライブラリの整備
精進よりもこっちの方が長くやっていたような気がします。
ライブラリとは:
簡単に言うと、よく使うアルゴリズムやデータ構造を事前に実装しておき、必要な時にすぐに使えるようにするもの。
AtCoderにはAtCoder Library(ACL) という公式のライブラリがありますが、私は使うライブラリは全て自分で実装しました。
自力で実装することによってそのアルゴリズムの原理が分かるので、必要な時に適切に改造するなど融通が利きやすいと思います。
ACLに頼ることは悪いことではないですが、内部実装を知らずにブラックボックスなまま使って分かった気になるのはよくないと思います。
また、ACLにはないもののライブラリとして持っておいた方が楽になるアルゴリズムもあるので、ライブラリの整備は精進の一環としてもおすすめです。
緑色になるまでに実際に用意したライブラリとその使用頻度はこんな感じです。
| アルゴリズム | 使用頻度 |
|---|---|
| セグメント木 | 高 |
| Union_find | 中 |
| ランレングス圧縮 | 中 |
| 座標圧縮 | 中 |
| 区間をsetで管理するテク | 中～低 |
| ローリングハッシュ | 中～低 |
| 遅延セグメント木 | 現状低 |
| 全方位木DP | 現状低 |
| Trie木 | 低 |
| エラトステネスの篩 | 低 |
| 基数変換 | 低 |
| manacher | 0 |
| RollbackabeなUnion_find | 0 |
知らないアルゴリズムがあったらぜひ調べてみてください。特に太字にしたアルゴリズムを理解できたら様々な問題を高度なアルゴリズムでオーバーキルできるようになるので、ABCがもっと楽しくなります。
入緑に必要なこと・あった方がいいもの
入緑記事で書いている人があまり見当たらなかったので書いてみます。
私が思うのはこんな感じだと思います。
-
必要なこと
- 典型知識
- 考察力
- 応用力
- 実装力
- コードの正確性
-
あった方がいいもの
- 数学力
- ライブラリ
- AI
- 紙
- 自信
必要なこと
結論、緑色に上がるためには典型問題を早く通すこと、Ad-hocを通すことが必要になります。(どの色でも基本的にそうですが)
特に後者が茶色には大事だと思います。
ABCのセットにはほぼ確実に茶が1問、緑か水が1問含まれていますね。
灰色以下はC問題を通せば大抵は暖まるため、灰色にはとにかく典型問題を通すことが重要であると言えるでしょう。
しかし、茶色に上がるとC問題を通すだけでは暖まりにくくなってきます。D問題を通すためにもC問題は早めに解いておきたいです。C問題の典型問題に時間をかけたくないので、典型力が必要になると言ってもいいでしょう。
しかし、C問題にはAd-hoc(=他の問題で使うことがないタイプの応用)な問題がたまに出題されます。これが茶色コーダー最大の敵で、これを通せなければ死、通しても遅かったら+1桁など渋い結果になります。
D問題もできれば通したいので、入緑には以下の力が必要になってくると思います。
- 典型知識
- 考察力
- 応用力
- 実装力
- コードの正確性
それぞれ何に影響するかをまとめてみるとこんな感じになります。
| 早解き | 典型 | Ad-hoc | D問題 | |
|---|---|---|---|---|
| 典型知識 | 〇 | ◎ | ||
| 考察力 | 〇 | ◎ | ||
| 応用力 | 〇 | 〇 | ||
| 実装力 | ◎ | 〇 | ||
| 正確性 | ◎ | 〇 |
これらをどうやって鍛えるかに関しては難しいですが、結局日々の精進で身につくものなので、気長に頑張るのが一番でしょう。
あった方がいいもの
数学力
競プロではたまに数学力に関して言及されます。私は数強ではないのでよくわかりませんが、数式や数列の問題は頻出なので数学ができる人はそれらの問題が通しやすくなりうると思います。
ライブラリ
ライブラリという概念の性質上あればあるだけ得ではあります。実際セグメント木はド典型の問題でも現状緑下位程度のdiffなので、ライブラリだけでも持っておく価値は大いにあります。
また、ライブラリを持っておくと高度なアルゴリズムで問題をオーバーキルする、いわゆる殴るということができるようになります。問題を殴れるようになると、細かい部分の実装がスキップできたり大幅に簡易化できたりするため、非常に楽になります。
AI
勿論コンテスト中に使うのではなく、解説を読んでも分からない部分をAIに聞いたり、アルゴリズムやデータ構造の解説を出力させたり、コードのバグ診断などをするために使います。
データ構造についての質問は原理の理解に役立ちますし、バグ診断に関しては非本質のケアレスミスに時間をかけずに済みます。
精進の効率を上げるためにも活用していく方が良いでしょう。
また、余談ですが学生さんはGithub Educationを申請することで卒業までGithub Copilot Proを無料で使うことができます。
学生の方なら登録し得なので競プロに真面目に取り組みたい方は申請してみるといいでしょう。
学生証とその英訳を一緒に写真を撮って提出すればいいですが、それなりに落ちるので通るまで頑張ってください
紙
考察を頭の中だけで収めるのではなく、アウトプットすることで考察の効率が上がります。
特に数式や数列の問題などは紙に書きだすことで考えやすくなりますし、その他の問題でも実験すると何か見えてくることもよくあります。
自信
あなたは優秀なので最終的に勝ちます。 私はこのメンタルでAtCoderと高校受験を通したので多分効果あります。
余談
書きたいことを色々書いていきます。
おまじないに関して
C++の方はコードの頭におまじないが書いてありますよね。本当に最小限しか書いていない方もいれば、ありえないぐらい長いマクロを書いている方もいます。
正直個人の好みとこだわりなのでどれがいいとか言うつもりはないですけど、repマクロとか型宣言を短くするやつとかは個人的にあんまりやらない方が良いと思ってます。非本質の部分を抜き出してる感じがするので。
他人のおまじないだけ批判するのも良くないので、私が普段使っているおまじないも貼っていきます。好きなだけ馬鹿にしてください。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX LONG_LONG_MAX
#define INT_MIN LONG_LONG_MIN
#define ynstream(f) (f ? "Y" : "N") << (f ? "e" : "o") << (f ? "s" : "")
struct dcin{template<typename T>dcin&operator>>(T&x){return std::cin>>x,x--,*this;}}dcin;
long long pray(string s=""){random_device rd;long long x=(static_cast<long long>(rd())<<32)|rd();return x;}
signed main(){
}
3行目:intをlong longにキャスト
4,5行目:3行目と矛盾がないように関数をキャストする
これのせいで毎回2個警告が出てる
6行目:fがtrueならYesを、falseならNoを返す
カスみたいな見た目をしているがちゃんと動く
7行目:cinした後にデクリメントする 有能
8行目:本物のおまじない
pray()すると64bit signed long longのランダムな数値を神から授かる
これにより1ns程度の時間を棒に振れる
10行目:main関数はintで終了コードを返さなくてはならない
int main()だとlong longで返すため仕方なくsigned main()
例外として、
#define endl "\n"
これをやっている人は絶対に今すぐやめてください。 インタラクティブな問題で死にます。
"\n"は改行はしますが、出力をflushしません。
出力ごとにflushを求められるインタラクティブな問題でTLEする可能性があります。
拡張機能に関して
拡張機能を入れると色々快適になってとても便利です。
私が入れているものを紹介するので気になったものはぜひ入れてみてください。
-
TemperMonkey
拡張機能を使うなら導入必須 -
AtCoderResultNotifier
提出結果を画面左側で通知してくれる -
AtCoder Dropdown Tasks
問題のタブにカーソルを合わせるとドロップダウンしてくれる -
mod noticer
答えでmodをとらなくてはいけないときに提出ボタンで警告してくれる(たまに誤作動) -
ac-predictor
順位表に現在のperfとレート変動を表示してくれる -
AtCoder Difficulty Display
コンテスト終了後に問題ページにdifficultyなどが出るようになる -
AtCoderStandingsAnalysis
こういうのが出るようになる -
AtCoder Easy Test v2
こういうのができるようになる
おわりに
最後まで読んでいただき本当にありがとうございます！！
記事を書くことが初めてなため読みにくいところ等たくさんあったと思います。
分かりにくい部分などあったら何かしらで教えていただけるとありがたいです。
私は他の人と違ってほとんど真面目に精進をしていないのにも関わらす上振れて入緑してしまい、参考になることを書けていないかもしれませんが、ほんの少しでも助けになる部分があれば幸いです。
最初にも書きましたが今後色々な記事を書いていく第一歩としてこの記事を書きました。今後の記事をもっとわかりやすく書けるように競プロと一緒に精進していきたいと思います。
それでは、改めてここまで読んで下さり本当にありがとうございました！