AtCoderで水色になりました!

zekeです。AtCoder競技プログラミングをしている大学1回生です。先日、三日連続rated(初日はunrated)でめでたく入水できましたので、色変記事を書いた次第です。

 約10か月で水色になれました。4月に一応の目標としていた水色に到達できてほっとしています。水色の色変記事を書くことは夢だったので、自分語りを加えながら、これまでの競プロ人生を振り返っていきたいと思います。

一応の注意

完全な自己満記事です。覚悟してください。

 

競技プログラミングを始めたきっかけ

 高校まではプログラミング自体をほとんどやったことがなく、むしろハードの方面をやっていました。ロボカップなどに出ていたこともありました。しかし、大学の新歓でKMCというサークルに出会い、そこで競プロと出会いました。そのサークルでは毎週、競プロ練習会が開かれていて、自分のようなC++を触ったことのないような初心者に対しても親切に教えていただいたので徐々にはまっていった感じです。先輩方には感謝してもしきれないですAtCoderもその流れで知って、ABC124にて初参加を果たしました。平成ABCにしては簡単な回で3完などをしています。

灰~茶にかけて

先述した通り、毎週の競プロ練習会でいろんなことを教わったのですが、始めたばかりの自分には荷が重く、あまり理解はできませんでした。その頃は、あまり競プロを熱心にはやっておらず、毎週末のコンテストに出るだけだったのですが、7月ぐらいにICPCがあることを知りました。これは大学生向けの競プロの大会であり、3人組で出るものだったので、同じサークルの同じく同時期に始めた人と組んで出場しました。このコンテストのために最低限のC++の文法(配列、データ構造)や基本的なアルゴリズム(全探索など)を頭に突っ込んでいた覚えがあります。そして、コンテスト直前ぐらいで茶色になりました。

f:id:zekehamp:20200112235812p:plain

 そのあとにあったICPCですが、やはり初心者には荷が重く、2完しかできませんでした。しかし、その時印象的だったのは、自分たちの向かいのチームが終わる直前で難問を通していたことです。そのチームは「heno world」さんで、めちゃくちゃ強い方々だったのですが、その姿を見て「早く強くなって、あんなふうになりたい」と思った記憶があります。

茶~緑にかけて

ちょうど夏休みに入ったので、大学図書館に行っては精進を繰り返していました。蟻本を買ったり、drkenさんの記事(神記事たくさん!)を読んだりして、いろんなアルゴリズムを頭に叩き込みました。全探索、BFS、DFS、累積和、二分探索、尺取り、動的計画法などのアルゴリズムの存在を知りました。とにかく、このころはICPCで振るわなかったこともあって、必死でABCのC問題を埋めていた気がします。この時、同時並行でゲーム製作をしていたこともあり基本的な実装力がついた気がします。具体的にはA、B問題は確実に解ける、C問題も令和ABCになってからは安定してとけるようになる、といったところでしょうか。レートが伸び悩んだ時期もありましたが夏の終わりまでに色変を目指して頑張っていました。そうやってしているうちに、緑パフォが安定してきて9月初めごろに緑になれました。

f:id:zekehamp:20200113001427p:plain

緑~水にかけて

かなり大変でした。緑になるまでに、いろんなアルゴリズムを学びましたが、それがまだ実践段階にはなかったのです。具体的には二分探索の使いどころや基本的な動的計画法の書き方とかです。またbitを用いた問題(XORなど)、グラフ問題と出会った問題と出会ったのもこの頃です。しかし、今まで学んだことを組み合わせて使ったり、違った視点から見る問題にも出会って、だんだん競プロの楽しさに気づき始めました。問題もAtCoderにとどまらずAOJやCodeforces、yukicoderにも手を出して片っ端から解いていた感じです。難易度帯としてはAtCoderだとdifficultyが緑~水ぐらい、yukicoderでは星2~3ぐらいでしょうか。AOJは新たなアルゴリズムを知った時に、それを試すために利用しました。コンテストのほうは令和ABCに切り替わってからA、B、C問題はACして当たり前、Dも大体解けて、E問題にチャレンジしていこうという感じです。しかし、時々爆死してしまうこともあり、それは他の記事にまとめています。

zeke00.hatenablog.com

11月ぐらいで順調に上がっていたレートがカクっと下がったり、解けそうで解けない問題に出会ったりして歯がゆい思いもしました。しかし、この頃に始めたTwitterであほみたいに強い方々や、同じぐらいのレベルで頑張っている人を見てモチベをもらったりしていました。そんな感じで精進を続けていたら二回のunratedを経て無事に水色になりました。

やったことに関してあれこれ

精進などの内容をつらつら語ります

その1:コンテストに出る

多分一番大事なのでは?と思います。もちろんABCは出るとして、諸意見ありますがAGCや企業コンにもどんどん出るべきだと思います。自分は理不尽に難しい問題を解くのが好きなこともあるのですが、二時間ぐらい頭を抱えながら問題を考える経験を付けるべきだと思います。また、ACしたときの快感は凄まじいものがありますし、たとえできなかったとしても解説を見るなどして、いろんな気づきがあるからです。Twitterでコンテストについてワイワイするのも楽しいですし、とにかく出ましょう!

その2:問題を解きまくる

はい、精進です。解きまくりましょう。個人的に精進の助けになったページを下に貼ります。 

 

qiita.com

drkenさんの蟻本シリーズです!蟻本で習った内容をAtCoderの問題で復習できるので、最高です!

www.hamayanhamayan.com

はまやんはまやんはまやんさんの分野別問題まとめページです!ある分野に関して集中的にやりたいときに最適です。

atcoder-rivals.herokuapp.com

AtCoder Rivalsというサイトです。登録したユーザーの問題の提出状況をTL形式で観測できます。異常精進している人々を観測してモチベを上げましょう!

他にもたくさんのサイトにお世話になりました。感謝します。

その3:刺激を受ける

こちらのサービスは天才や人外がうようよいて、奢りそうになった時に見るといいかもしれません!!!

twitter.com

 他にも、解説記事を書いてみたり、サークル内で講座をやったりすることで自分は精進をしました。拡張などを作ったりするとテンションが上がります。

水色になるまでに勉強したアルゴリズム、テク(若干、上から目線)

いろんなマクロ

自分は緑になったぐらいでC++でマクロを導入しました。賛否が分かれますが、自分は競プロの本質のみを追求できるので愛用しています。

全探索系アルゴリズム

BFS、DFS、bit全探索、貪欲などを含みます。この辺りは類似問題を解きまくって、慣れるしかないと思います。実装が重いことがあるので注意です。コンテストでは真っ先に疑う癖をつけたほうがいいと思います。

二分探索

これも真っ先に身につけたほうがいいと思います。応用範囲が大きいですし、何よりよく出ます。これもコンテストで真っ先に疑うべきものです。

(基本的な)動的計画法

最初の難関です。ナップサックを始め様々な形があるのが特徴です。自分は、全然できなかったのでEDPCなどを解きまくって習得しようとしています。以下、自分が書いた精進記事です。

qiita.com

累積和

めちゃくちゃ出ます。他のアルゴリズムとの組み合わせの相性がとてもいいです。一次元、二次元imosを習得しましょう。

以下の記事が最高なのでぜひ読みましょう!

qiita.com

グラフ

最短距離問題、全探索系問題、木、二分木、抽象グラフに落とす…などバリエーション豊かです。概念自体を競プロで初めて見たので大変でした。

こちらも神記事なので読みましょう!

qiita.com

 

UnionFindなどの集合系

UnionFindだと思わせない問題が多いように感じます。

小学校算数

いっぱい出ます。組み合わせ、確率、整数、いろいろあります。自分は中学受験勢だったので当時のことを思い出しながらやっています。

受験数学

いっぱい出ます。整数、幾何、三角関数、いろいろあります。数学が得意な人々は持ち前の数学力で殴っていくらしいです。自分はよわよわです。

C++の文法あれこれ

コンテナ、構造体、STLなどです。C++には競プロのために作られているのではないかと思うほど便利なSTLがあったりするので、ぜひ覚えましょう。

ぶっちゃけ使えなくても大丈夫なやつ

セグメント木など

これから勉強していこうと思います。一回だけ実戦で使ったことがあり、青パフォをたたき出したときには発狂しました。

幾何とか

あまり出ないし…誤差に注意なことを覚えておくといいかもしれません。

フローとか

知ってはいるけど実戦では使ったことはない、そのようなものです。

Twitterでみかけるような難しそうなやつ

ぶっちゃけそんなものを覚えるよりも、既存の知っているアルゴリズムの熟練度を上げるのが大事だと思います。

 最後に

自分は大学に入ってから競プロに出会ったのですが、この界隈には天才、奇人、人外、神、その他諸々がうようよしています。自分はただの凡人なので、そういった人たちを見ると自己肯定感がガリガリ削られます。でも、自分は頭を限界まで使う競プロが好きで、この界隈に入り込んだことの後悔を全くしていません。むしろ、自分の力がどこまで通用するか試したいぐらいです。この度は水色になりましたが、次は青目指して猛進していきたいです(/・ω・)/。

長くなりましたが、ここまで読んでいただきありがとうございました。

どうして自分は水色になれなかったのか

これは、KMC Advent Calendarの25日目の記事です。

adventar.org

前日はid:cc141君の公認会計士試験を受けてみたでした。 公認会計士すごい。

はじめましてzekeです。競技プログラミングとかやっています。

突然ですが見てほしいものがあります。

f:id:zekehamp:20191227013945p:plain
水色になれなかった人

目標としていた「この記事を書くまでに色を変える」ことができませんでしたーーーーー!!!!!

いや、Advent Calendarに登録した時点では色変記事書く気満々だったんですよ。いや、ほんとに。 しかし、この度色を変えることができなかったので、色変記事ならぬ「色が変わらなかった記事」を書こうと思うんですよ、書くネタがマジでなかったため。 趣旨としては、ここ最近のコンテストで好成績を残せなかった反省をつらつら述べるだけになっております。 それでもいい方は、最後まで読んでいただけると、ありがたいです。

水色になれなかった理由その一 : やはり精進が足りなかった

競プロの原点にして最も大事な精進。やっぱりこれが足りないのが第一の理由でしょう。

f:id:zekehamp:20191227015114p:plain
12/27時点でのABC埋め状況
うーんって感じです。Cはともかくとして、Dをもっと埋めるべきですね。過去ツイで見たことがあるのですが、自分のレートの0~200上ぐらいの問題を埋めるのがよいとのこと。確かに、将来的にはそのレベルに達するために頑張るわけなので道理にかなってます。しかし、自分の悪い癖として「分からん………解説見るか…あっ(何かを悟る)…そっ閉じ」を繰り返してしまうというのがあります。問題を解いてレベルを上げないといけないのに「自分にはまだ早い」とか「やるだけなのでメンドイのでやらない」とか自分に言い訳をして、敬遠してしまう傾向があるようです。それだといつまでたっても成長しませんね。そういう反省もあり、最近はバチャをやったり緊張感のある状態でやることで「解説ACをできるだけ避ける、解説を見たとしても頑張って、一から実装する」ということを意識しています。 あと、これは個人的な意見なのですが、自分のレートより著しく低い問題を埋めることはしていません。AC数だけを稼いで「今日は競プロめっちゃやったなー」という仮想満足をしないためです。もちろん解くスピードをあげるために解く必要はありそうですが、難しい問題を頭抱えて考えるほうが自分は好きなので水色以上のdifficultyを埋めることを意識してます。

水色になれなかった理由その二 : コンテストに最後まで集中できる環境、体調を整える

これは意外に大事だと思います。

f:id:zekehamp:20191227020601p:plain
AtCoder Performancesより
11月後半にガクっと下がっているのが分かります。わかりやすく大爆死をきめています。 この理由として、

  • この時学祭があって気持ちが浮ついていた
  • サークルのシフトを七時間こなした
  • コンテストをやるよい場所がなかったので、ネカフェでコンテストをした

これらの状況でやったのが大きいと思います。結果、ABCでAB二完という惨敗をしています。 これは余談ですが、このコンテスト終わった後、憂さ晴らしに朝までカラオケなどをやっています。 つまり、「落ち着いて集中できる状態で」、「体調を万全にして」、「慣れた場所で」コンテストを行うことが大事でしょう。 そういった状況下では、

  • 少なくとも爆死の可能性は大幅に減らせる
  • 過去に解いた問題を効果的に想起することができ、類似問題が出た時に大きなアドバンテージになる
  • いつもと違うことが起こっても(5完しても緑パフォなど)気持ちが乱されない
  • コンテスト終了間際まで集中力を維持できる

といったメリットがあると思います。 なので、最近は可能な限り、自室で30分ほどの仮眠をとった後に、ウォーミングアップとして数問解いてからコンテストに臨もうとしています(なかなか難しいですが)。

水色になれなかった理由その三 : 本番慣れしていない

これは競プロにとどまらず、受験などにも共通すると思うのですが、やはり本番になれるというのは大事です。つまりは、もっとratedに出ろってことですね。やはり練習だけでは

  • 解いている問題がどのくらいの難易度かわからない(順位表情報からある程度分かることもありますが)
  • 思いついた解法にしがみついてしまう
  • 初手で躓いた(簡単な問題でWAを生やす)などの想定外な出来事に弱い

といったものがあると思います。 特に二つ目は自分では大きいと思っていて、この問題ではO(1)の解法にコンテスト中ずっととらわれていて二分探索でできることに気づくことができませんでした。 やはりレートが関係するコンテストならではの緊張感を毎回感じていて、それによる失敗はあると思います。 そこで数日前、初めてCodeforcesのdiv2に出ました。ratedのコンテストを増やして、早く本番慣れをしたいです。

水色になれなかった理由その四 : フラグを立てた

これはお手本のようにフラグを立てる阿呆の図です。

ほんっとにフラグを立てるのは危険です!!!! 間違ってでも、

  • コンテスト前に「あっ次のコンテストで色変わるわwwww」
  • コンテスト中に「あっ勝確www」

とかをやってはいけません!!!!! 慢心ダメゼッタイ。 こんなことをするから、

こんなことになるわけです。

こんなことを言ってきましたが、

自分は競プロが好きです。19年生きてきて、ここまで一喜一憂しながらも、ここまで熱心に取り組んでいるのは初めてかもしれません。やっぱり難問にぶち当たって、悩みに悩みぬいた挙句、思いついた解法で実装してはWAを生やし、ドイツ語の授業を犠牲にして考察を重ねた結果出すACには格別なものがあります。やはり、水色になるには、その過程を楽しむといったことが一番かもしれません。年内にはあと二回のratedがあります。これまでの反省を踏まえて、水色めざしてがんばっていきたいと思います。