この記事は、大阪工業大学 Advent Calendar 2020の8日目の記事です。
あくまで体験談(ココ重要)です
1.はじめに
senarice(著者の競プロname)は、2020/6/21に茶色コーダになりました。今もマイペースに頑張っています。今回はちょっと調子にのって色変記事を書いてみました。
2.競技中にやってはいけないこと
その1 お酒を飲みながらやる
競プロはたまに「パチンコ」と言われます・・・。「ギャンブル×酒」はろくなことになりません。
その2 途中であきらめる
A問題やB問題でWAを連発してしまう時があるかもしれません。ですが、その時は心を切り替えてレートをなるべく下げない方向性に切り替え、できるとこまで足掻きましょう。(たまに、ほんのちょっぴりレートが上がったりもする)
その3 検索するのを拒む
問題で「ここどうやってやるんだっけ・・・」と思ったら躊躇せずすぐにググりましょう。
3.茶色になるために求められること
その1 AB問題の早解き
これができないと正直厳しいです。これは、過去問をやりこむしかないと私は考えます。ABCのB問題は全部埋める勢いで精進しましょう。実際私自身、B問題をやりこむことでABの早解きができるようになったと自負しています。また、まれに昔のB問題が少し形を変えて出題されることがあります。
・Atcoder Beginner Contest 030 B-時計版
・Atcoder Beginner Contest 168 C- : (Colon)
見てわかると思いますが前者(B問題)が解けば後者(C問題)も解けそうですね。
その2 アルゴリズム
最近のAtcoderでは、優しめのアルゴリズムだと普通に難易度は灰色になります。(厳しい)
これから書くアルゴリズムは茶色コーダーを目指すなら知っていてほしいと考えるものを列挙しています。自分で調べてメモ帳等に保存しておきましょう。(ただ単にメモするだけじゃなく、返り値の形といったプログラムの内容をある程度理解することをお勧めします)
最大公約数,最小公倍数
出現率はやや高めな気がします。(以下は例題)
・鹿島建設プログラミングコンテスト2020（AtCoder Regular Contest 110）A - Redundant Redundancy
約数列挙
約 数 を 列 挙 し ま す
・AtCoder Beginner Contest 180 C - Cream puff
素因数分解
約数の数を数えたりするのと色々使えます。
(例題は難しめです)
・AtCoder Beginner Contest 169 D - Div Game
全探索
愚直な全探索です。これを見抜けるセンスを磨くと後々楽だと思います。
・AtCoder Beginner Contest 175 B - Making Triangle
・AtCoder Beginner Contest 170 B - Crane and Turtle
bit全探索
bitを用いて全探索します。習うより慣れろだと思います。
個人的なイメージではn個からm個(n>=m)選ぶときに多用するイメージです。
・AtCoder Beginner Contest 182 C - To 3
・AtCoder Beginner Contest 167 C - Skill Up
(やや難)
・AtCoder Beginner Contest 173 C - H and V
(やや難)
next-permutation
配列の順列を生成します。難しいことを言っているように見えますが、やっていることはすごく単純なので必ず理解できると思います。(内容は割愛。各自調べてください)
コンテストでは忘れたころに出てきます。
・AtCoder Beginner Contest 183 C - Travel
Union-find
名前が頭よさそうですが、中身はそこまで難しくないです。(むしろ簡単?)
グラフをかじってるとかなり理解しやすいです。(内容はカット)
・ACL Beginner Contest C - Connect Cities
・AtCoder Beginner Contest 177 D - Friends
(やや難)
imos法・累積和
内容は各自で。これも全然複雑ではないです。
個人的には計算量を減らす際に用いることが多いイメージです。
・AtCoder Beginner Contest 183 D - Water Heater
3.さいごに
筆者も初めの方は全然できませんでした。(for文を理解するのに1時間くらい、配列の添え字を理解するのにも1時間くらいかかった気がします・・・)
また、競プロのモチベを失い三ヶ月くらいしなかった時もあります。ですが、精進等を重ねるうちに少しずつできるようになりました。なので茶色コーダは努力で何とかなると思います。