灰色スタックしていた私が考える「茶色になるために必要なこと」
初めまして。セグ森です。
昨年の5月から趣味で競技プログラミング(AtCoder)をやっています。
ずっと灰色から抜け出せず苦戦していたのですが、先日のAtCoder Beginner Contest (ABC)189で、ついに念願の茶コーダーになることができました！
目次
はじめに
AtCoderの参加者には「めちゃくちゃ地頭がいい人」や「数強」「天才」「う し た ぷ に き あ く ん 笑」などがその辺にゴロゴロいます。コンテスト初参加から一か月で緑や水色になったりするすごい人たちです。
一方で私はいわゆる普通の人です。
茶色になるまでに19回もコンテストに参加しています。
茶色というとAtCoder内で特別高いレートというわけではありませんし、Twitterをやっていると全人類が茶どころか緑以上であるかのような錯覚を覚えますよね？
しかし実際は参加者の半分くらいは灰色です。
私のような凡人も相当数いるはずなんですが、あまり表に出てきません。
そこで「一般人」が茶色になるまでに頑張ったこと、というのも需要があるのではないかと思い記事を書いてみることにしました。
自己紹介
・プログラミング未経験(APG4bで学びました)
・文系の大学を中退（最終学歴高卒）
・情報科学の知識はほとんどなかった
・Twitter → セグ森 (@segment_three) | Twitter
はじめてのAtCoder(余談)
今となっては笑い話ですが、私は初めてABCに参加したとき、まさかの0完太陽をしています。正直絶望しました。こんなことすらできないのか…と。
なので、B問題が難しい…と悩んでる初心者の方がいても気にしないでください。
プログラミング未経験なら最初はそんなもんです。(いや0完はありえないが)
そこから茶色は目指せます！あきらめないでもうすこし続けてみてください。
ちなみにこれが当時の提出コードです。
https://atcoder.jp/contests/abc167/submissions/13056293
'if(1 <= Ssize <= 10)'
と書いてます。数学じゃあないんだよ。
やったこと
私のAtCoderProblemsです。
競プロで頻出の典型もある程度勉強しました。
基本形であれば実装できるようになったものを列挙します。
・累積和
・†二分探索†
・BIT全探索
・素因数分解(エラトステネスの篩)
・順列列挙
・いもす法
・しゃくとり法
・BFS/DFS
データ構造
・queue
・deque
・set
・map
・Union Find
もともと茶色の先の緑を目標に見ていたので緑向けのアルゴリズムも混ざっています。体感ですが、茶色になりたい人が最低限学ぶアルゴリズムとしては
・累積和
・BIT全探索
くらいでも十分だと思います。
あとはsetやmapは便利なので早めに理解しておくと実装で楽できることが増えます。
実際、茶色になるために必要なのはアルゴリズムや考察力ではありませんでした。
灰色に足りないのは「プログラミングの基礎」
見出しの通りです。
AtCoderで灰色→茶色になるために必要なのは実はアルゴリズムの勉強ではなく、データ構造やプログラミングの基礎の理解である
というのが私の考えです。
私が苦戦した理由として大きいのは、解法が思いつかないというより「解き方はわかったけど実装できない」「バグをなおせない」「エラーがなぜ起きているかわからない」といった部分でした。(今も苦戦してます)
例えば、あ！この問題は累積和で解けそうだ！
と問題を見て5秒でわかっても、実装してみたら未定義動作が起きて提出できないといったことや
直近だとABC188-Dで
「いもす法だ！解ける」と飛びついたものの、10^9という巨大なサイズの配列がメモリに乗らないことを知らないためにパニックになったりしていました。
ほかにもABC169-Cでは浮動小数点数の誤差をあまり理解していなかったり、max(a,b)の中身をint型とlong long型でやろうとしてコンパイラに怒られたり、イテレータをint型に代入しようとしたり…
とにかく自分が扱っている「便利なもの」の中身と、それができることを理解していないのが原因だったように思います。
バグってしまうと解法の方向性があっていても一切得点にならないのが競プロです。今まで何度も「解き方はわかってるのに…」と悔しい思いをしてきました。
どうすればいいのか
・とにかくがむしゃらに問題を解いて慣れる
・基礎理解を深めておく
の２つの方法があると思います。
私は前者でした。競プロの問題を解くのは非常に楽しいので悪いことではないと思いますが、レートを上げるということを目的にした場合効率が悪いように感じます。
後者の方法ですが、エラーを吐くたびに「C++の日本語リファレンスを読みにいく癖」をつけるのは結構いいです。これを繰り返しているとちょっとずつ言語仕様の理解が深まってきて無茶なコードを書かなくなると思います。
あとはぜひ読んでほしい記事があります。
えびちゃんという方のブログなのですが、まさに私のような「よくわかってないものを使ってる競プロer」のために書いてくださっている記事があり、非常に参考になりました。
特にこの３記事を読むと灰～茶くらいの人がハマってそうな実装の罠をかなり回避できるようになります。実装で悔しい思いをすることが多い方はぜひ読んでみてください。
それと私は応用情報技術者を取得したのですが、体系的に情報科学の分野の勉強ができてためになりました。
もともと情報系出身の方なら必要ないかもしれませんが、文系出身の方は基本情報か応用情報の勉強をしてみるのも一部ですが競プロの役に立つと思います。(BIT演算やデータ構造をイメージしやすくなりました)
競プロかじってるひとなら灰色でも午後のプログラミングは満点取れると思います。体感だとABC-Bくらいの難易度です。競プロは応用情報の役に立つ。
おわりに
特に私のようにプログラミング未経験から競プロを始めた人が茶色を目指す場合、実装の壁が立ちはだかってくると思います。
もし「そこそこ典型覚えてるはずなのに茶色になれない…」と思っている灰コーダーの方がいたら、一度えびちゃんさんのブログを読んでみてください。私は最近読んだのですが、もっと早い段階で知って起きたかった！！！と思いました。
あと、茶色ってう〇この色みたいでいやなので早く緑になれるように頑張って精進します。
おわり。
