あるたいるの競プロ手記

競プロについてちまちまと書いています

AtCoderで水色になりました！

はじめましてこんにちは、あるたいるです。

2021/1/10 の ABC188 でめでたく水色になることができたので、色変記事を書いてみることにしました！

「競技プログラミング始めたばっかりなんだけど、何すればいいの？」という灰Coderさん🐘から「はやく水色になりた〜〜い！！」という緑Coderさん🌿まで、お役に立てれば幸いです（あるいは「水色なんてとうの昔に過ぎ去ったぜ…」というガチプロさんも、暖かい目で読んでくれると嬉しいです）。

 

f:id:altairrr:20210111172543p:plain

入水！！

0. 自己紹介

　所属：東京大学前期教養学部理科二類1年

　競プロ歴：8ヶ月（入水時）

　Twitter：あるたいる（@altair_kyopro）

　AtCoder：altairrr

　Codeforces：altair_codf

 

　プログラミングは中高一切やったことがなく、5月にはじめて竸プロに出会いました。数学はそこまで得意ではありません（東大入試数学4割切り・JMO予選落ち等々…）。パソコンも詳しくありません。

　でもそんなのは関係なくて、楽しければなんでもOKです。ただし、やるからには強くなりたいので、いろいろ頑張ってみたところ、8ヶ月ほどで水色になることができました。うれしいね！！

　この記事が脱初心者の道標になったらいいなあと思い、記事を書いてみます。

 

1. 入水への経緯

  • 竸プロを始める（2020/5/8）
    　4月中頃から、Twitterのタイムラインでみんなやってたので「楽しそうだな〜、でもパソコンよくわかんないしなあ〜」と思って見ていました。しかしある日、ふとコンテストサイトを覗いてみると、環境構築しなくてもできることに気づき、APG4bから始めました。自分の書いたコードが実際に動いて問題を解けるのがめちゃくちゃたのしくて、のめり込んでしまいました。

  • 初めてのコンテストに出る（2020/5/10）
    　初めて出たコンテストは 2020/5/10 の ABC167 でした。「とりあえずおためしで出てみよ〜」と思い、レジりました。このときは "Yes" と "YES" を間違っていることにしばらく気づかず、2ペナ。B問題でも1ペナして、結果2完3ペナ、パフォは84でした。先は長い…

  • 入茶（2020/8/2)
    　2020/8/2 の ABC174 で入茶。個人的にはなかなかいいペースだったと思っています。（が、TLの人の中にはすでに水色とかがいたりして…）11回目のコンテストだったので、ちょうどレート補正が外れたころだったみたいです。

  • 環境構築をする（2020年8月ごろ）
    　夏休みに実家に帰省したときに、パソコンにやたら詳しい弟に環境構築をしてもらいました。（残念ながら自分にはよくわからず…）　しかし、これのおかげでコーディングがかなり速くなりました。

  • 入緑（2020/10/12）
    　2020/10/12 の ARC105 で入緑。夏休みの精進が効いたのか、9.10月で一気にレートを伸ばすことができました。ちょうど20回目のコンテスト！

  • Codeforcesを始める（2020/11/29）
    　AtCoder は週に1.2回しかコンテストがなく、しかも時々参加できないこともあるので、すこし物足りなく感じていました。そこで噂に聞くCodeforcesを初めてみることに。最初の方は面白いようにレートが伸びるので、気分が良かったです。（笑）
    　ちなみにCodeforces は 2020/12/17 に入青し、現在も青です。

  • 入水（2021/1/10）
    　2021/1/10 のABC188 でついに入水しました！年末のうちに入水したかったのですが叶わず、1/9のARC111は大荒れで冷えてしまい、すこし不安もありましたが、しっかり5完して入水することができました。合計で32回目のコンテストでした。

2. ここまで何をしたのか？

  • APG4b
    　個人的にはやはり竸プロするならC++だと思っているのですが、それはAPG4bの影響が大きいです。 竸プロを始めたばかりのころは、これを順番に埋めていきました。とりあえず3章まで頑張って読みましたが、途中途中でかなり難しい内容（参照や再帰関数、構造体など）があり、しんどくなっていました（実際のところほとんど理解できていなかった）。今考えてみると、1章がしっかり読めていたらあとは割と適当でもよかったのかなあと思っています。

  • AtCoder Beginners Selection
    　APG4bを終えた後はこれをやりました。竸プロたのしい！と感じるには最適なセットだと思います。ただし、「白昼夢」とかは相当難しいと思うので、解説をみるか、一旦飛ばしても全然良さそうです。（実際C問題は解説見ました）

  • 過去問埋め
    　結局はこれに尽きます。AtCoder Problemsを使うのがおすすめです。最初はABCのA~Dのうち茶diff以下のものを近い順に片っ端から埋めて行ったのですが、これ以上やるのは無駄だと踏んでABC126まで（ABCが6問になったところ）でやめました。
    　そのあとをAtCoder Problems の List を用いて茶diffと緑diffをdiffが低い順に全埋めしました。自分は変な完璧主義を発揮してUnratedもやりましたが、別にRatedだけでいいと思いますし、なんなら全埋めもしなくていいと思います。ただし、これをやったことにより確実に力がついたとは感じています。
    　その後、その流れのまま水diff埋めに移行し、現在その途中です。入水達成時のAC数は602でした。

    f:id:altairrr:20210111214452p:plain


    　「過去問を埋めるときには、しっかり時間をかけて粘り強く考えるのが大切」という話があります。しかし、茶色・緑色の場合、「そもそもアルゴリズムやデータ構造を知らないので解けようが無い」というパターンがかなり存在するので、個人的には、解説を見るハードルはかなり低くていいのではないかと思っています。
    　また、公式解説は上手くまとまってはいるのですが、「じゃあ実際にどうやって実装すればいいの？」まではフォローしてくれないことも多いです。そういうときはすぐにググりましょう。「ABC180 c」みたいな感じで調べればたくさんヒットします。特にけんちょんさんのブログや記事がとてもわかりやすいので、よくお世話になっております。ありがとうございます🙏　解説放送もおすすめです。

  • Educational DP Contest (A~J)
    　緑後半になってある程度典型がわかってきたところで、さらにDPに特化して詰めたくなったので。ただし、後ろの方は相当難しいという話だったのでとりあえず前半だけ。これも知らないと厳しい問題が多いので、パパッと解説を見ても良いと思います。サーバルさんたちに教えてもらいましょう。

  • Codeforces
    　上でも書きましたが、11月からロシアのコンテストサイト・Codeforcesにも手を出しています。といってもこちらはほぼコンテストに出て復習するだけで、個人的にはAtCoderの練習だと思ってやっています。コンテストの頻度がとても高いのが何より魅力的です。モチベーションのアップにつながりますし、コンテストという形でたくさん経験を積めるのは非常にありがたいです。レートもAtCoderより上がりやすいので、気分が良くなります（逆に言えば下がりやすいということでもありますが）。一つ欠点があるとすれば、コンテストが真夜中なことですかね…　深夜起きるのがつらくない人にはおすすめです。（英語はそこまで難しくないので心配ないと思います。翻訳サイトも使えるし）

  • 環境構築・テンプレート/ライブラリの整備・AtCoder Library の導入
    　最初はコードテストで頑張っていたのですが、ある程度のレベル（茶色以上）になると、やはり環境を整えることは偉大です。特にエディターを整備することは速解きに大きく貢献します。自分はVSCodeを使っているのですが、スニペット（事前に設定しておいた文字を打つと、登録しておいたコードを出してくれる）の存在が大きいです。速くなる上、typoも圧倒的に減ります。僕の場合、弟（高1）がパソコン・プログラミングに関して非常に（異常に？）詳しかったので、彼に任せましたが、この記事を参考にしたそうです。（弟くんは、競プロではなく開発系に興味があるみたいです。すごい）

    　環境構築をしたことで、毎回最初に書くテンプレートを作成することができるようになりました。自分のテンプレートはこんな感じです。

    f:id:altairrr:20210113024119p:plain

    謎の呪文、マクロ、なんでもござれい

    　また、自作のライブラリを作っておくのも大切です。ABCの後半ともなると、基本的な関数等は簡単に取り出せるようにしておくのが不可欠です。内容は、後述の「覚えたテクニック」を読めば大体わかると思います。

  • f:id:altairrr:20210112093356p:plain

    ここからコピペして使います

    　一方で、AtCoder Library (ACL) というものがAtCoder側で用意されています。（水Coder的には）非常に高速ですし、最近のABCではACLを使うことで簡単に解ける問題も出題されています（ABC185-Fなど）。使えるものは使った方がいいと思いますので、がんばって導入しましょう。やってみると意外と簡単で、パソコン音痴でもなんとかなると思います。ただし、ブラックボックスは怖いし応用が効かないので、どういう原理なのかはがんばって理解するようにします。後述しますが、入水にあたってはDSU(UnionFind)とSegtree（とFenwick Tree(BIT)も一応？）だけ把握していればおそらく大丈夫です。また、実用上はnaoya_tさんが作成してくださったクイックリファレンスが非常に便利です。

  • 竸プロの本を読む
    　そんなに熱心にはやってないのですが、いわゆるけんちょん本と蟻本を買いました。けんちょん本はがんばって最後まで読みましたが、蟻本はほとんど辞書のような使い方をしています。入水にあたっては特にけんちょん本がおすすめです。説明が丁寧ですし、初心者に必要なトピックが厳選されている感じがします。あと純粋に面白いです。

  • 精進ツリーを作る
    　月ごとに、解いた問題のコードをを日付・問題タイトル・感想や簡単な解法とともにツイートしてツリーに貼り付けています。

    自分が今月どれくらい精進したかが目に見えてわかるのでモチベーションアップにつながりますし、一言でいいから感想をまとめておくと、似たような問題を見たとき思い出しやすいし探し出しやすいです。ブログに解説記事を書くつもりはないので、これくらいが継続しやすいと思います。ただしTLの人にネタバレすることになるので、フォロワーが増えたら検討すべきかもしれません（杞憂か？）

  • 頼れる強い人・同レベルのライバルとつながる
    　Twitterや大学などのコミュニティを利用して、強い人と繋がりを持つことは重要です。わからないことをツイートしたり質問したりしたときに答えてくれる人がいると、非常にありがたいです。また、「こいつには負けたくないな〜」という相手がいると、精進も捗りますし、モチベーションも上がります。

3. 覚えたテクニック（アルゴリズム・データ構造）

  • 累積和・imos法
    　言わずもがな。かなり初期から必要になります。imos法は茶色レベルらしいですね。以下の記事が参考になります。三度登場けんちょんさん。ありがたい。

  • vector,deque,queue,priority_queue,map
    　この辺は知っているか知らないかがかなり大きい要素です。バケットソートで用いられるバケットの考え方とそれを用いた高速化も勉強しましょう。コンテナについては、APG4bのこのページを参照するといいと思います。

  • sortによる高速化、しゃくとり法による高速化
    　ABC-C/Dで出がちな高速化二大巨塔はこれだと思います。とりあえず一番最初に考えるべきです。

  • 二分探索（lower_bound,upper_bound）
    　いわゆるめぐる式というやつを使うのがいいと思います。lower_boundやupper_boundは便利ですが、普通に二分探索で書いても全く問題ないので、正直なところ、自分はあまり使ったことがありません。むしろ、内部構造を知らずになんとなく使う方が応用が効かず危険です。またもやけんちょんさんの記事を貼ります。

  • 素数判定・約数列挙・素因数分解・ユークリッドの互除法
    　整数系の問題では不可欠なアルゴリズムなので、これらも早いうちに勉強しておくべきだと思います。ここでもけんちょんさんの記事を貼らせて頂きます。

  • modの扱い・繰り返し二乗法・逆元
    　最初の方は「mod 10^9 + 7 で求めてください」にビビってしまうことがあるのですが、体系的に勉強すると、意外と恐れるものではないことがわかります。繰り返し二乗法も、二進数の考え方がわかれば難しくありません。一方で、逆元を理解するためには、Fermatの小定理や拡張ユークリッドの互除法を理解する必要があるので、なかなかレベルが高く骨が折れます。入水にあたってはとりあえずコピペでも問題ないかな、とは思います。もちろん理解するに越したことはないですが、優先度は高くないです。またまたですが、けんちょんさんの記事を貼ります。

  • 二項係数
    　逆元を学んだら、是非とも履修しておきたい内容です。300点問題程度ならパスカルの三角形を用いた実装でも問題ないのですが、問題のレベルが上がると、計算が間に合わなくなるので、逆元の前計算を用いた高速化が必須となります。一つ上に貼った記事内にも記述があります。

  • 座標圧縮
    　入水を目指すレベルだとたまに出てくる程度ですが、基本的な考え方や雛形は知っておいて損はありません。この概念を知らずに問題を解くことも可能だとは思いますが、速解きが重要なABCにおいては、やはりライブラリとして持っておくべきでしょう。

  • 再帰関数
    　とても大事です。下記のDPや探索系アルゴリズムで使用することになります。ただし、一筋縄ではいかないと思います。最初はなんだ簡単じゃないかと思うんですが、いざ問題の中で使おうとすると「？？？？？」となりがちです。APG4bの再帰関数の章を読んだ上で、たくさん問題を解くしかないと思います。

  • 動的計画法（DP）、メモ化再帰
    　入緑・入水で中心となるアルゴリズムの一つ、DPです。様々な形式があり、慣れが必要だと思います。出るたびにきっちりパターンとして覚えていきましょう。上記もしましたが、EDPCはおすすめ。解説記事も多いです。

  • グラフに関わるアルゴリズム（DFS,BFS,Warshall-Floyd,Dijkstra）
    　グラフ、理解するまでは大嫌いだったんですが、今では一番好きなタイプの問題です。「今俺アルゴリズムしてるな〜」ってモロに感じられるのがいいんですよね。迷路探索（グリッドグラフ）は別にライブラリとして持っています。個人的にはDijkstraよりもWarshall-Floydの方が、実装が楽なのも含め優先度が高いと思っています。Warshall-Floydは直感的に分かりにくいと思うので、以下のツイートを参考にどうぞ。

     　また、これはアルゴリズムではないのですが、入力などを全て行ってくれるmake_Graph, make_Tree, make_Cost_Graph という関数をライブラリとして持っています。いちいち書いてると頂点のデクリメントを忘れたりするので、コピペすると安心です。

  • DSU（UnionFind）
    　これは下手するとグラフ探索より先に出てくるかもしれません。ACLにもありますが、非常に重要なデータ構造なので、中身もしっかり履修することをおすすめします。中身はABC157-Dの解説放送が分かりやすいと思います。

  • Segtree
    　こちらも同じくACLですが、割とハイレベルだと思います。知らなくても入水はできそうです。

  • bitset、bit全探索、bit演算
    　bitsetを用いたbit全探索はいまや茶diffとなっています。APG4bにも説明がありますので、そちらを読むといいと思います。bit演算系の問題は、自分の場合慣れるまでは苦手意識が抜けませんでした。まずはxorとかにビビらないことが大切です。「桁ごとに計算する」という意味が徐々にわかり始めると、急に解けるようになったりします。

  • next_permutation、bitDP
    　順列を列挙したいときに用います。前者は非常に重要で、かなり基礎的なレベルとして問われます（入緑には必須）。後者はいわゆる巡回セールスマン問題で用いられます。こちらは少しハイレベルで、入水には必要ないかもしれません。この2つは制約を見た瞬間に思いつけるようにするといいと思います。N = 8 程度なら next_permutation のセンが濃厚です。

4. あるたいるの「おさえておきたい」お気に入り問題　15選

 　「入茶・入緑・入水を目指す上で欠かせない」と僕が思うAtCoderの問題を15問選んでみました。下に行くほど難しくなります（境界は曖昧ですが、一応、入茶・入緑・入水に5個ずつ対応しているつもりです）。個人的にネタバレされるのが嫌なのであえてポイントは書かないでおきますが、どの問題もしっかりと理解すべき問題ばかりです。「精進したいけど時間がないよ〜！」という方、ぜひご活用ください。（最近のコンテストがやたら多いですが、許してください）

5. 意識していること

ここからは、僕が競プロをするときに意識していることをいろいろ書いていきます。

 

　　問題を実際に解いているときに意識していること

  • 実際に手で書いて考える
    　サンプルケースを見つめるだけだとなかなか解法は浮かびません。サンプルケース1なんかは細かく説明されていることが多いので、実際に問題の操作を実行してみるのが大切です。また、自分で例を考えて書いてみるのも助けになることが多いです。自分はiPadを使って「竸プロ考察ノート」を作っています。

  • 一回で完璧に書こうとしない
    　これは個人で流派が分かれるところだと思うのですが、方針が浮かんだら、自分はとりあえず一回書いてみてからバグを消していくようにしています。コーナーケースなども、よほど自明なとき以外、最初は無視して書いていきます。

  • 制約でアルゴリズムを決め打ちしない
    　これは最近気を付けていることなのですが、制約を見た瞬間特定のアルゴリズムを思考から外すのは危険な感じがしています。もちろん制約をヒントにするのは大切ですが、考え方を整理するためにもまずは愚直に考えてみるのもよいと思います。（かといって無理筋に固執するのも良くないですけどね）

  • 全探索できるなら全探索
    　これは入水レベルの問題に対してのみ有効な策かもしれませんが、なによりもまずは全探索を検討すべきです。探索する範囲を絞ったり、うまく式変形をしたりすることでなんとか全探索できないか考えましょう。

　　コンテストに出ているときに意識していること

  • まずはテストケースも含めて問題を最後まで読む
    　A問題でも流さずちゃんと読むべきです。「何を答えれば良いのか」「どういう罠がありそうか」をしっかり捉えましょう。焦ってコーディングして、結果そもそも問われていることが違ったなんてパターンが最悪です（僕はしばしばやりがちです）。

  • 順位表は多少の参考に
    　順位表を見すぎるのは良くないですが、多少の参考にするのはいいと思います。特に注目すべきは現在の順位ではなくACの人数です。難易度の逆転なんかは参考にしても良いかな？という印象があります。もちろん速解きすべきときに見るのはご法度ですが…

  • 目標を立てておく
    　AtCoder Rating Simulatorなどを用いて目標を決めておくのは大切です。その上で大体何完すればよさそうか考えておきましょう。ABCであれば、入茶には3完、入緑には3完速解きか4完、入水には4完速解きか5完くらいが目安になるでしょうか。

　　その他普段意識していること、あるいはメンタル的なこと

  • コンテストは出れるならできるだけ出よう
    　とりあえずコンテストには出る、というのを一つの方針にしていました（20時まで新宿で麻雀して、そのまま近くのスタバでABCに出たりしました）。ただし、無理する必要はないと思っています。この辺りは後述。

  • 上を見過ぎない、つよいひとはつよい。過去の自分と戦おう
    　Twitterをやっていると、あるいは東大の競プロ勢を見ていると、初めて1年もしないうちに黄色になる人とか、当然のようにABC全完する人とか、中学生なのに自分よりずっと上にいる人とか、すごい人がたくさんいます。自己紹介でも書きましたが、僕はさほど数学が得意なわけではないので、どれだけ頑張ってもその域にはいけないかもしれません。だからこそ、いずれ追いつけたらいいな〜くらいに考えて、自分と比べることはあまりしないようにしています。
    　逆に、過去の自分ができなかったことができるようになったとき、知らなかったことを新たに知れたときに喜ぶようにした方がいいかなあと思います。精進も、AtCoder Problemsが緑色に埋まっていくことに達成感を感じられるようになると、しんどくなく続けられると思います。自己肯定感大事。

  • 楽しく競プロしよう
    　これが一番大切なのですが、競プロは楽しくやってなんぼだと思います。僕は幸い競プロつらいな〜と思ったことはまだないのですが、つらくなったらその時はすぐにやめるつもりでいます。（笑）また、「コンテストはできるだけ出よう」と言いましたが、友達との晩ご飯の予定を蹴ってまで出る必要はないかな〜と思いますし、他にもっと楽しいことがあるならそちらを優先すべきだなあと思っています。競プロと関わる方法はコンテストに出ることだけじゃないですし、なんならプログラミングと関わる方法も競プロだけじゃないです。ただし、僕は出るからには強くなった方がもっと楽しいと思うので、精進を続けています。

6. さいごに

　いかがでしたか？（定型文）

　長々と書いてしまいましたが、大概のことは他の方の色変記事にも書いてある気がします。ずいぶん偉そうなことを書いてしまった気もします。書いてて自分が楽しかったので関係ないですけどね。もし、この記事を読んで面白く思ってくれる方が一人でもいれば幸いです。

　次の目標は入青です。競プロはじめて1年で入青できれば上出来だなあと思っています。バチャとかも積極的にやっていきたいですし、他の競プロerさんとの交流もしたいですね。UTPCやICPCにも挑戦したいですし、しばらくは楽しく続けていけそうです。
　AtCoderの運営の方々や、けんちょんさんをはじめとするわかりやすい記事を書いてくださる方々、先生でもありライバルでもあるUTB1のみなさん、いつもアドバイスをくださるTwitterの競プロerのみなさん、環境構築してくれた我が弟、そしてこんな長い記事を読んでくださった方々、いろんな人に感謝しつつこの記事を締めたいと思います。ありがとうございました。