はじめに
先日(2023/01/21)行われました、ユニークビジョンプログラミングコンテスト2023 新春 (AtCoder Beginner Contest 287)にて入緑しました。
本記事においては、入緑までに行ったこと等をまとめます。
自己紹介
私は某私立大学の学部三回生であり、情報系の学科に所属しています。
特筆するような実績だったり特徴を有するような人間ではありません。
AtCoderでは主にC++言語を使用しています。
それ以上のことを知りたいようならTwitterを見てください。
https://twitter.com/seeton_kyoupro
ところで多くの競プロerが読むであろう以下の記事があります。
ここに、茶色の説明として以下の記載があります。
各大学の情報系学部でしっかりとプログラミングを勉強して上位 1 割の成績を収めている学生さんの実力です。
私は上位1割の成績ではありません。
平均かそれ以下くらいに位置しています。
緑色になりましたが成績が上がるとは思えません。
入緑するために必要なこと、やったこと
以下に入緑するために必要だと思われること、行ったことを記載します。
個人的主観に基づくものもあります。
1 前提条件として
AtCoder Beginner Contest(以下ABC)で入緑する十分条件に『一回以上のコンテストで、パフォーマンスが800以上である』があります。1
私は24回目の緑パフォ(800以上、1200未満のパフォーマンスを取ること)で入緑しましたが...
最近のABCにおいては、上位30%の成績をとることでパフォーマンスが800程度になります。
AtCoderで緑色(レート800以上)であることは比率としては上位15%以上ですが、コンテスト的にはコンスタントに上位30%以上の成績を取れればそのうち入緑することができます。
2 解いた問題数
AtCoder Problemsというサイトで解いた問題数等が見れます。
他の入緑記事を見ると大体これくらいと同じか、数をこなす人ならもうすこし多いかといった感じです。
私は、一つの問題を解き切りたい人なので、問題数を稼ぐということはしませんでした。
ただし、入緑程度では記事を書かないという人は問題数はもっと少ないと思います。
特に俗に灰diffと呼ばれる簡単な問題を解くことは茶色後半程度からのレートの上昇に寄与するとは思えないため解きませんでした。
実際には典型90等の問題も解いたりはしているのでこれよりも多いですが、今振り返ると精進2はあまりしてないように見えます。
3 アルゴリズムとデータ構造
3.1 使用できるもの
☆:それ自体は完璧に使用できる、発展形の問題も解ける
◎:ある程度発展形の問題も解ける
〇:やるだけの問題なら解ける
△:解けることもある
使用頻度に関しては、私がコンテストで解く問題(ABCのA~D)に限ります。
| 名前 | 使用頻度 | 理解度 |
|---|---|---|
| 全探索 | 極高 | ☆ |
| エラトステネスの篩 | 低 | ☆ |
| bit全探索 | 中 | ☆ |
| 座標圧縮 | 低 | ☆ |
| 約数列挙 | 中 | ☆ |
| 貪欲法 | 中 | ☆ |
| 幅優先探索(BFS) | 高 | ◎ |
| 深さ優先探索(DFS) | 高 | ◎ |
| 二分探索 | 高 | ◎ |
| UnionFind | 高 | 〇 |
| 三分探索 | 低 | 〇 |
| 動的計画法(DP) | 極高 | 〇 |
| 優先度付きキュー | 中 | △ |
| imos法 | 低 | △ |
| bitDP | 中 | △ |
抜けがあるかもしれません。
3.2 オススメのもの
オススメ順に書きます。
3.2.1 UnionFind
UnionFindに関しては構造を理解しなくても動作を理解すれば、かなりアドバンテージを取れるためオススメです。
例えば上の問題に関してですが、DFSやBFSでも解けますが、UnionFindを使用すれば2~3分程度で解くことができます。
解説を読めば分かるように実装のコードの量は一目瞭然です。
UnionFindを使用する問題はこのように、UnionFindを使用する+簡単な処理をするだけの問題も多く出ます。
3.2.2 動的計画法(DP)
DはDPのDと言われるくらいには動的計画法はよくでます。
私が入緑をかました回でもDはDPでした。
ちなみにコードはこんな感じです。(マクロを消してます)
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
int N,X;cin>>N>>X;
vector<int>A(N);
vector<int>B(N);
for(int i=0;i<N;i++){
cin>>A[i]>>B[i];
}
vector<bool>DP(X+1);
DP[0]=1;
for(int i=0;i<N;i++){
for(int j=0;j<B[i];j++){
for(int k=X;k>=0;k--){
if(DP[k]==1)DP[k+A[i]]=1;
}
}
}
if(DP[X])cout << "Yes" << endl;
else cout << "No" << endl;
}
最初に書くときは脳がこんがらんがって、訳わからんことになりますが、そのうち訳わからんとは思いつつも書けるようになります。
でも解けた回は緑パフォくらいは簡単に出るのでオススメです。
Dくらいだと、コード量もそんなに長くはならない（例外もある）ので論理をしっかり確認しながら書くのと、今回の問題も典型なので
の問題を解くと良いです。
私はGまで解きました。
3.2.3 二分探索
競プロerの伝家の宝刀†二分探索†は、A~Dくらいまでだとそんなに出ることも無いという印象です。
よく、水色以上コーダーの人が二分探索+なんらかのアルゴリズムで問題を解いたと発言されることがありますが、それらは難しい気がします。
ABC246のD問題では二分探索を用いて解くことができます。（他の方法でも解けます）
以下コードです。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll func(ll a,ll b){
return a*a*a+b*b*b+a*a*b+a*b*b;
}
int main(void)
{
ll N;cin>>N;
ll ans=LONG_MAX-1;
for(int i=0;i<1e6;i++){
ll ok=1e6;
ll ng=-1;
while(abs(ok-ng)>1){
ll mid=(ok + ng) / 2;
if(func(mid,i)>=N){
ok=mid;
}else{
ng=mid;
}
}
ll tmp=func(ok,i);
ans=min(ans,tmp);
}
cout << ans << endl;
}
この問題は緑diffの最上位級(diff1148)であるのにも関わらず二分探索のみで解くことができます。
二分探索に関しては、めぐる式二分探索が有名です。
中身は
4 その他の知識、能力、環境
最初に書いてあるように、私は情報系の学科に所属しています。
この点で非情報系の人に比べてアドバンテージが存在すると思います。
競技プログラミングは結局のところネトゲだとしか思ってはいないのですが、他のネトゲと比べて、罪悪感がありません。
なんなら「就活でC++は何で勉強したの？」とか「普段からプログラミングはやってるの？」とか聞かれたときに競技プログラミングの話ができます。
あんまり競プロのことを話すとかえってデメリットになりかねない気もしますが
私は中学の頃は数学が得意教科でしたが、高校になって全く分からなくなりました。
暗記能力があまりないので、積分公式だとか三角関数の公式とかで何もわからなくなりました。
競プロでは、暗記はあまり必要なく、公式等はその場その場で調べれば問題ないので、そういった苦手な点が解消されています。
まあでも根本的にあんまり数学ができるわけではないため、入緑までに時間がかかったわけですが。
緑になった感想、雑感
茶色で停滞していた期間が長かっため、かなり嬉しいです。
成功体験の一つとして非常に大きなものになりました。
次の色は水色ですが、個人的には相当厳しいのではないかと思います。
とはいえ、灰色の時は、茶色の人がすごいと思っていたし、茶色の時は緑色の人がすごいと思っていたので案外続けてればそのうち入水するかもしれません。
今でも入茶したとか言ってる人を見るとすごいなと思うので、なんとも言えませんが。
入緑するために何をやったのかという話をすると、本は読みました。
この二冊が良かったです。
蟻本は紙でも電子でも持ってますがnot for meでした。
他にも何冊も持っていますが、この二冊で十分でした。
アルゴリズムを知らないと解けない問題も多々あるので知っておくと楽しくなれます。
また、大体の入N（Nは任意の色）記事にも書いてありますがコンテストに参加し続けるのが良いです。
精進は色々な方法でやりましたが、結局数をこなすのが一番ではないかと。
diffは自分のレート以上ならなんでも為になります。（問題が古すぎるのは良くない）
そういえば、入茶するまでは灰と茶までの間に色を欲しいと思っていましたが入茶したときからあまり気にしなくなりませんでした。
むしろ400～599と600～799までの能力の隔たりが気になっていました。
緑になって、そこらへんもあまり気にならなくなりました。
でも、何級とかだと味気ないので色を加えて欲しいなとは思いますね。
最後に
書き疲れたので終わりです。
これからも競技プログラミングは続けていく所存です。
次は入水記事で会いましょう。