こんにちは、Blueberryです。入水してから時間は経ってしまいましたが記事を書こうと思います。
はじめに
まずレート遷移を貼っておきます。
3/12に入緑し、5/28に入水しているので、約2か月半で入水したことになります。今回はTwitterで募集した質問に回答しつつ記事を書いていこうと思います。
どうやったら水色になれるの？
一言で言うならば「精進」です。
(画像はAtcoder Problemsより)
低難度埋めをしているのでAC数は比較的多い方だと思います。とにかくたくさん解けばレートは上がるので、コツコツと解き続けていれば水色になれると思います！(もっと効率的にレートを上げたい方はE8さんのこの記事が良いと思います)
また、(「やるだけ」問題を例外として)ただ解くだけではなく、解法を残しておくのも良いと思います。Scrapboxで解いた問題の振り返りをしたり、Twitterで解いた問題について一言を残しておくなど。
僕は本当にただひたすらに問題を解きまくって水色になった人間なので、これ以上特に言うことはありません...！
初心者の方はまずはわからないところはどんどん調べてプログラミングに慣れていくことからだと思います！プログラムが書けるようになってきたらひたすら問題を解きましょう！(最初はA埋めがオススメです！)
「埋め」を忌避する方もいると思いますが、効果がないわけではないと思うので、やらないよりはやった方が良いと思います！始めたてのころは簡単な問題からでも多くの学びが得られるはずです。
言語はC++/たまにPythonです。茶色時代はPythonを使っていましたが、JOIでC++しか使えないらしいのでC++をはじめました。書きやすくて気に入っています。多倍長整数を使いたいときなどにPythonを使います。
拡張機能は何を入れてる？
この記事を参考に、自分の好きなものを入れましょう。特にAtcoder Easy test v2は非常に便利なのでおススメです(ただし、コンテスト開始直後は正常に動作しないことが多いので注意が必要です)
テンプレート
こんな感じです。(ながい)
using namespace std;
#include<bits/stdc++.h>
void _main();int main(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);_main();return 0;}
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
typedef long long ll;typedef long double ld;template<class ll> inline bool chmax(ll& a, ll b) { if (a < b) { a = b; return 1; } return 0; }template<class ll> inline bool chmin(ll& a, ll b) { if (a > b) { a = b; return 1; } return 0; }
#define rep(i, star,fini) for (ll i = star; i < fini; i++)
#define ALL(x) std::begin(x), std::end(x)
#define INF ((1LL<<62)-(1LL<<31))
#define bit(x,i)(((x)>>(i))&1)
//入力を受け取りつつ宣言する
inline void scan(){}
template<class Head,class... Tail>
inline void scan(Head&head,Tail&... tail){std::cin>>head;scan(tail...);}
#define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;scan(__VA_ARGS__)
//vectorのcout,cin
template<typename T>
std::istream &operator>>(std::istream&is,std::vector<T>&v){for(T &in:v){is>>in;}return is;}
template<typename T>
std::ostream &operator<<(std::ostream&os,const std::vector<T>&v){for(auto it=std::begin(v);it!=std::end(v);){os<<*it<<((++it)!=std::end(v)?" ":"");}return os;}
long double my_distance(long double xi,long double yi,long double xj,long double yj){return sqrt(abs((xi-xj)*(xi-xj))+abs((yi-yj)*(yi-yj)));}
//Union-Find from https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/union-find
class UnionFind{public:UnionFind() = default;//注：0-indexed
explicit UnionFind(size_t n): m_parentsOrSize(n, -1) {}
int find(int i){if (m_parentsOrSize[i] < 0){return i;}return (m_parentsOrSize[i] = find(m_parentsOrSize[i]));}
void merge(int a, int b){a = find(a);b = find(b);if (a != b){if (-m_parentsOrSize[a] < -m_parentsOrSize[b]){std::swap(a, b);}m_parentsOrSize[a] += m_parentsOrSize[b];m_parentsOrSize[b] = a;}}
bool connected(int a, int b){return (find(a) == find(b));}
int size(int i){return -m_parentsOrSize[find(i)];}
private:std::vector<int> m_parentsOrSize;
};
ll modpow(ll a,ll n,ll mod){ll res=1;while(n>0){if(n&1)res=res*a%mod;a=a*a%mod;n>>=1;}return res;}
ll modinv(ll a, ll mod){return modpow(a,mod-2,mod);}
bool iskaibun(string s){ll k = s.size();rep(i,0,k/2){if(s[i]!=s[k-1-i]){return false;}}return true;}
プログラミングの経験年数など
Scratchを始めたのが小5、Pythonをまじめに学び始めたのは中2、C++を始めたのは中3の1月ごろです。それ以外にはゲーム制作でC#をかじっていた程度です。競プロを始めるまではほとんどプログラミングは出来なかったと思います。
習得したアルゴリズム
この方の記事を参考に書きます。
- 〇→まあ使える
- ◎→得意！
- △→微妙、調べれば使える
- ×→使えない
- ？→聞いたことがない、聞いたことしかない
グラフ
| アルゴリズム | 習得度 |
|---|---|
| ダイクストラ法 | ○ |
| ワーシャルフロイド法 | ○ |
| ベルマンフォード法 | × |
| オイラーツアー | △ |
| トポロジカルソート | △ |
| プリム法 | × |
| クラスカル法 | ◎ |
| 強連結成分分解 | ○ |
| HL分解 | ？ |
| 木の直径 | ○ |
探索
| アルゴリズム | 習得度 |
|---|---|
| 幅優先探索(BFS) | ◎ |
| 深さ優先探索(DFS) | ◎ |
| bit全探索 | ○ |
| 半分全列挙 | △ |
| 順列全探索 | ○ |
| 二分探索 | ○ |
| 三分探索 | 〇 |
| 答えで二分探索 | △ |
| しゃく取り法 | ○ |
| Mo's Algorithm | ○ |
DP
| アルゴリズム | 習得度 |
|---|---|
| 1次元DP | ◎ |
| 2次元DP | △ |
| 最長共通部分列 | × |
| 最長増加部分列 | × |
| 区間DP | × |
| 期待値DP | ◎ |
| 確率DP | ◎ |
| bitDP | ○ |
| 桁DP | △ |
| 竹DP | ？ |
| 耳DP | ？ |
数学/幾何
| アルゴリズム | 習得度 |
|---|---|
| GCD/LCM | ◎ |
| 累積和 | ○ |
| いもす法 | △ |
| 二次元累積和 | △ |
| 素因数分解 | ○ |
| 約数列挙 | ○ |
| 高速素数判定 | ◎ |
| 素数列挙 | ◎ |
| 繰り返し二乗法 | ○ |
| 回転行列 | ？ |
| 逆元/MOD上の割り算 | ○ |
| 拡張ユークリッドの互除法 | × |
| 行列累乗 | × |
| FPS | × |
データ構造
| アルゴリズム | 習得度 |
|---|---|
| Union-Find | ◎ |
| map | ◎ |
| set | ◎ |
| multiset | △ |
| BIT | △ |
| SegmentTree | ○ |
| LazySegmentTree | 〇 |
| Sparse Table | × |
| WaveletMatrix | × |
その他
| アルゴリズム | 習得度 |
|---|---|
| 座標圧縮 | ◎ |
| RLE(ランレングス圧縮) | ◎ |
| ローリングハッシュ | × |
| 最大長方形 | × |
その他、TLで見かけた高度そうなアルゴリズムはストックしてあります。いつか習得したい...！
ここからはTwitterで募集して来た質問に答えていきます。
数学は得意ですか？
算数は得意ですが、数学はそこまで得意ではありません。発想を求めるような分野の問題が好きで、覚えなければ解けないような分野の問題が苦手です。特に幾何が苦手です。
ただし、場合の数・確率は得意なので、僕の数学力は競プロ的にはプラスの方向に働いてると思います。
競プロerに向けて、ゲーム制作の魅力について熱く語ってください
もともと競プロを始める前はゲーム制作をしていて、主にUnityでゲームを作っていました。競プロを始めてからゲーム制作をしてみると、今まで使おうとも思っていなかった&存在も知らなかった、setなどのデータ構造が息をするように使えるようになっていて成長を感じました。
競プロerのみなさん！ゲーム、好きですよね？自分で作ってみたくなりますよね？？競プロで培ったその狂気の実装力、ゲーム制作に活かしてみませんか...！？
AtCoderを毎日やってて飽きないですか?
飽きないです。飽きるわけがないです。JOI本戦に出ると決めた日から、Streakを繋ぎ始めたときから、競プロは僕の人生です。JOIで結果を残せなくて後悔したくないので準備を怠るつもりはないです。自分が所属している部活を盛り上げるために実績が必要で、実績を得るための最短ルートがJOIだと思ったから。
そして、ここまでStreakを繋いで来れたので、途中で切らしたくないと思っています。正直言って自分がここまで競プロに熱中するとは思っていなかったですが、初めてここまで熱中できるものに出会えたので大事にしたいと思っています。
次の目標は？
入青です！少し前にTwitterで、「JOIの本戦突破の最低ラインが青」という話を聞いたからです。青になるために今は青DiffStreakをしています！時間はかかるかもしれませんがコツコツと努力していきたいです。
おわりに
最後まで読んでくださりありがとうございました！引き続き精進頑張ろうと思います。次回は入青記事で会いましょう！