はじめに
AtCoder Beginner Contest 258でRateが800に到達し, Atcoder緑色になることが出来たので色変記事を書こうと思いました。
およそ2年, 約70回のコンテスト参加で入緑することは珍しい(?)と思うので記録を残しておきたいと思います。
やりました!!!
— Sc0ττîsħFa||°Ç (@49405C4) July 2, 2022
Gex777さんのAtCoder Beginner Contest 258での成績:2886位
パフォーマンス:939相当
レーティング:791→807 (+16) :)
Highestを更新し、6 級になりました!#AtCoder #ABC258 https://t.co/nrsfUCWvl9
基本情報
・大学は工学系(非情報系)の学科出身
・プログラミングは大学までまともにやった経験なし, よくわからんロボットをスクラッチみたいなので動かしたくらい
・持っている資格は基本情報技術者と自動車免許くらい
・競技プログラミングではC++しか使えない, 簡単なプログラムならPythonも書ける
・地頭は競プロerの中では秀でているわけではないと思います
・そのため記憶力でカバーすることが多く, 実装系の問題のほうが得意なように思います
・ABCは基本rated参加でARCは参加しないかunrated参加
記事執筆時点での状況
パフォーマンス(こちらのサイト)
入緑までに使ったアルゴリズム, データ構造, 手法, やったこと
・C++のSTL(APG4bで紹介されているもの)
・BFS, DFS, bit全探索, 順列全探索
・二分探索(upper_bound, lower_boundなども含む, 決め打ち二分探索は除く)
・約数列挙, エラストステネスの篩
・論理演算AND,OR,XORなど
・GCD, LCM
・1~Nの総和みたいな簡単な数学知識
・場合の数とか
・ランレングス圧縮
・累積和
・いもす法(1次元)
・座標圧縮
・貪欲法(あまり自信ない)
・包除原理
・線形代数(回転行列と行列式で三角形の面積出すくらい)
・グラフや経路の探索(BFS, DFS)
・ワーシャルフロイド法(あまり理解してない)
・区間スケジューリング
・尺取り法
・けんちょんさんの本(ピラミット本)の前半部分
習得したけど本番では使わなかった使えなかった気がするアルゴリズム
入緑する直前に習得したため, なくても緑にはなれそう???
・Union Find(使い方のみ)
・2次元DP(ナップザック, 部分和くらいの簡単なもの)
緑色になるまでの時系列
灰色前半(~200)
・特に精進などはせず,とりあえずコンテストに出ていた
・C++の書き方を覚えていなかったためcin,coutやvectorの書き方も毎回ggっていた
・STLの存在を知らなかったのでsetやmapを知らなかった
・auto for文やイテレータも当然知らなかった
灰色後半(~400)
・Rateの伸びがあまりにも遅いことに気づきとりあえずA問題を全て埋めた
・APG4bをやった
・少しだけ精進をするようになった
・あまりにもレートが上がらかったので少しやらなくなった
・ABCのB問題埋めをするようになった
茶色(~800)
・あさかつやまよこん(Atcoder Problemsのバーチャルコンテスト)に参加するようになった
・ABCのC問題埋めをするようになった
・解き方を思いつくのが前よりも速くなった
・特に自分と同じくらいのdiffの典型問題やデータ構造を工夫する系の問題は問題を見ながら思いつけるレベルに
・ARCで冷え次の日のABCで元に戻ることを繰り返したため, ARCのunrated参加を決意
・少しずつRateを高くしていった(爆発できる回がなかった)
・ABC3完が安定するようになり稀に4完できるようになった
・解説ACをするようになった(それまでは自分が解けそうな問題を優先して解いていた)
・Twitterで自分と同じくらいのレートの人を探し, 追い越されない/追いつくことを目標とした
・特にきりみんちゃん(というVtuber)のAtcoderへの向き合い方には深い影響を受けたように思います
なぜこれほどまでに時間がかかったのか?
・単純に頭が良くない
・灰色では精進をあまりしなかったため, 前回のコンテスト時からの成長がなかった
・解説ACをあまりせず, 解ける問題を解いて満足していた
・精進するにしても集中力が持たず1日に数問ACするのが限界
・逆に他の参加者が賢すぎるという点
・TwitterのTLを見ていると参加者の多くは旧帝大や有名な高校で明らかに才能の差があった
・モチベーションを保つために色変記事を検索するとその多くが参加回数N回(N << 自分の参加回数)で絶望した
・一瞬で色変するような人に抜かされすぎたこともありあまり他者と自分を比較しないことにした
・昨日の自分より強くなっていければもっと上にいけるはず...
その他(雑談)
・解法分かった瞬間, ACが表示される瞬間にアドレナリン出るのたまらん
・コンテスト後のTwitterのタイムラインが三者三様って感じで面白い
・コンテスト結果が出るまでの時間が待ち遠しすぎる
・Atcoderのレベルは以前よりはあがっているのではないかと思う
・たまに実用的な問題出るの良すぎる(浮動小数点誤差関連とか)
・Atcoderとかいうネトゲ, 無料で出来て教育的なのでおすすめ(伝え聞くところによるとたまに賞金も出るらしい)
最後に
Atcoderをやっていたのとやっていなかったのではおそらく人生が大きく変わっているはずです
今後も競技プログラミングを続けるので, Atcoder社はこれからも解けた!を世界に届けてほしいと思います