![AtCoderで水色になるまでにやったこと [C#]](https://webbibouroku.com/wp-content/uploads/eye_atcoder.png)
AtCoderで水色コーダーになりました
AtCoderは毎週定期的に競技プログラミングコンテストを開催しているWebサービスです。
このAtCoderのコンテストにに2019年8月から取り組んでいます。ほぼ毎週末9時からコンテストが開催されます。できる限り参加すること27回、ついに水色コーダー(レート1200)になれました。約8か月の取り組みでした。
今回はAtCoderで水色になるまでやったことを振り返っていこうと思います。
レーティングの推移。
レーティングと精進の推移。11月以降は結構過去問やりこみました。グラフは AtCoder Scores で確認できます。
パフォーマンスの推移。AtCoder Performances で確認できます。
解いた問題数は 631、他にも yukicoder の問題や AOJ の問題も30-40問くらいはたぶん解いてます。
ざっとこんな感じです。
AtCoder に参加するまでの経歴と実力
大学は文系卒、業務系システムを開発をする会社でプログラミングをやってまして、ほとんどが .NET (VB or C#) での開発経験でした。
一応、基本情報は持ってますが応用情報は持ってないくらいの知識量でした。アルゴリズムは各種ソートアルゴリズムを勉強で実装したりくらいでほとんどAtCoderきっかけで勉強しました。
プログラミング歴は大体6年弱です。開始時に競技プログラミングの実力がどれくらいだったかというと、大体茶色中位(600前後)だったと思います。パフォーマンスの推移をみるとそんな感じでした。
問題でいうとC問題は20-30分くらいで解ける程度の実力です。もちろん実装力で解けない典型アルゴリズム問題は最初は解けませんでした。ただし参加当初のコンテストではちょっとした発想と実装力で解ける問題が多かったのが良かったです。具体的には以下の問題が20-30分程度で解ける感じでした。
D問題(Difficulty緑)はまるで歯が立たない感じでした。
コンテストに参加して気づいたこと
最初に参加したのは AtCoder Beginner Contest 136 です。
初参加の感想としては
- D問題が難しすぎる(とっかかりすらない)
- 計算量が大きいとTLEすること
でした。
この頃はアルゴリズムと計算量は一切考えてません。C問題まではだいたい言われた通りの実装を丁寧に考えさえすれば解けてました。
3回目くらいの参加後にパフォーマンスとレーティングについて詳しく知って、これをモチベーションにして参加することにしました。
水色になるまでにやったこと、精進
レーティングを上げるために取り組んだことをまとめてみます。基本的には自分のレートにかかわらずやることは予習復習、コンテストへの準備です。
過去問を解く
まず最初のうちは何より問題数をこなすことが大事です。基本的には直近のABCからさかのぼりつつ過去問を解いてました。
そのうちに AtCoder Problems を知り、Recommendations で現在のレートに合わせた難易度の問題を中心に解くようになりました。
基本は30分考えて何も思いつかない場合は、たいていの場合解くのに必要な手段(アルゴリズム)を知らないからなので、その場合は諦めて解説を見てました。
解いた問題はアルゴリズムの種類ごとに記録しておき、定期的に復習してました。例えば二分探索や累積和、DPみたいなくくりで問題をまとめておいて、気が向いたときにまとめて解きなおすみたいな感じです。
あと高校数学も少し復習しました。というのも特に組み合わせと整数問題は知らないとどうしようもないです。約数列挙の方法や約数の総和の求め方、組み合わせの計算方法は数時間の勉強で済むので必要になった段階でざっと復習しました。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 – Qiita
上記記事が公開されてからここであげられている100問も解きました。結局まだ70問くらいまでしか解けてませんが非常に勉強になるのでお勧めです。コンテストの問題が少ないので単純に初見の問題が多くて勉強にもってこいです。
基本的には問題を解けばレートは増えていくというデータもあるくらいなので、とにかく精進あるのみです。
上記のデータによると1100問解けば90%の確立で水色コーダーになれるようです。
代表的なアルゴリズムを勉強する
単純に過去問を解くのに加え特定のアルゴリズムに絞っての勉強もしました。
水色になるまでに勉強したアルゴリズムや問題は以下の通りです。
- 単純な全探索
- ビット全探索
- 順列全探索(
next_permutation) - 深さ優先探索、幅優先探索
- 二分探索
- 累積和、いもす法
- 尺取り法
- 動的計画法(ナップザックDP、桁DP)
- グラフ問題(木構造の深さ優先探索とか)
- UnionFind
- 素数列挙、約数列挙
- 最大公約数GCD、最小公倍数LCM
- 優先度付きキュー
- ModInt(剰余をとる必要がある四則演算やべき乗、nCr、階乗)
- XORの問題
- ダイクストラ、ベルマンフォード、ワーシャルフロイド
一番下の最短経路問題はいろいろ問題を解いたりはして勉強してますが、コンテスト中に使ったことはないですね。
基本的な勉強の仕方は「よさげなWeb記事を見る」->「実装する」->「過去問で試す」->「ライブラリにして使いやすくしておく」みたいな感じです。
手元に蟻本と螺旋本、アルゴリズムイントロダクションを用意しておき、理解できないときは調べたりもしました。が、蟻本は難しいの前半の理解できるところだけしか読んでないです。
コンテスト用のライブラリ(スニペット)を整備する
パフォーマンスを高めるには早解きも重要になります。できる限りこう素早く正確に実装する練習もすると同時にライブラリを準備をしましょう。
私の場合だと特にC#を使っている関係上、コンテスト用ライブラリの整備は必須です。何せ優先度付きキューもなければ、順列列挙(next_permutation)もありません。なのであらかじめいい感じに使いまわせるように実装したクラスをスニペットに入れてコンテスト中はそれをすぐに取り出せるようにしてました。
例えば剰余計算が必要な時、計算が単純にできるように ModInt を作っておくとか準備しておくとよいですね。
スニペットを使わずにコードをべた書きしておくと提出コードが大きくなりすぎるのでスニペットを使ってます。
VSCode, VS でのスニペットの使い方は以下のページにまとめてます。
Visual Studio のスニペットを自作する方法 │ Web備忘録
PAST – AtCoder アルゴリズム実技検定 に参加した
[C#] AtCoder 第一回 アルゴリズム実技検定 の振り返り │ Web備忘録
ちょうど第1回のPASTが開催されたのでこれにも参加しました。普段無料で参加できるコンテストと違い、有料で問題数も多いです。
内容としては、私が解いた範囲では典型アルゴリズムみたいな問題は出題されず、どちらかというと発想と実装力が試される感じでした。
普段のコンテストと勝手が違って面白かったです。第2回も開催が決まっているのでこれにも参加しようと思います。
1日1問AC
AtCoder Problems の機能で何日連続で新規ACという記録 streak が確認できます。この数字を伸ばすというのを一時期やっていました。どんなに忙しくても1日1問は新しい問題に取り組むということです。
数字として記録が残るので、なんだかんだ惰性でも続けられます。継続が上達への近道なのでこれは結構いい練習でした。A問題だけでも新しく解けばいいので忘れなければ1日3分程度で簡単に続けることは可能です。
結局私の場合は年末年始のなまけで、5分超過してしまいstreakが途切れてしまったのでやめました。最高で91日続けました。
今後の目標
今後も競技プログラミングを継続するにあたり、以下の2つを目標にしようと思います。
- 青コーダーを目指す
- ABCで全完する
どっちが先かは微妙です。現状ギリギリ青パフォーマンスが最高記録なので青コーダーは少し遠そうです。ABCは最高で5完なので、F問題が水色レベルの優しいコンテストにうまくはまればいけそうです。例えば ABC153 や ABC148 みたいな回だといけるかもしれないです。
今後も頑張ろうと思います。
以上。
