【色変】全完黄パフォで入水しました！

一昨日5/3(日)のABC166で初の全完を果たし、さらに黄パフォで入水いたしました！

f:id:Rorent:20200504165346p:plain

そこで、他の競プロerもすなる色変記事というものを、私もしてみむとてするなり、です。

ただし、読んでいただく前に一つ注意書きを。
この色変記事を書くにあたって、十数人の方の色変記事を読ませていただいたのですが、
そうして思ったのは「精進の仕方は十人十色」だということです。
ですので、以下に書かれている内容は、「おすすめの精進法」ではなく、あくまでも「精進の仕方の一つ」として読んでいただければ幸いです。

私自身のことに関しては、前回の記事で書きましたので、もしご興味のある方はそちらも読んでいただけると嬉しいです。

各種精進データ

入水した現在の精進の状況については以下の通りです。

f:id:Rorent:20200504172510p:plain f:id:Rorent:20200504172526p:plain f:id:Rorent:20200504172558p:plain f:id:Rorent:20200504172625p:plain f:id:Rorent:20200505141705p:plain f:id:Rorent:20200504172651p:plain

入水までに勉強したアルゴリズム

はい、色変記事あるあるです。
書き漏れがないようにプログラミングコンテストチャレンジブック（通称：蟻本）やAtCoder Tagsのカテゴリ分類を眺めながら、自分の知っているかつ使えるアルゴリズムを全列挙しておきます。
そしてそれらを、水色になるために重要そう（Lorent調べ）な順に並べ直したいと思います。
また、自分がそのアルゴリズムを初めて勉強したときに読んだ記事、見た動画の中で特にわかりやすかったもののリンクを貼っておきます。

☆☆☆：入緑でも確実に必要になるはず
☆☆★：まあまあよく使う
☆★★：数回使ったことがある
★★★：コンテストではまだ一度も使ったことがない

前提として

☆☆☆：入緑でも確実に必要になるはず

☆☆★：まあまあよく使う

☆★★：数回使ったことがある

  • Warshall-Floyd法

    • 全点対最短路問題を解くアルゴリズム。つまり任意の点から任意の点までの最短路を求めることができる。ただし計算量はO(|V|^3)（Vは頂点集合）。
    • 実装がめちゃくちゃ軽いので、計算量が間に合うなら、他のアルゴリズム使うべきであろうときもこれで済ませてしまうことも。
    • 蟻本2-5

  • Bellman-Ford法

    • 負辺があるときの単一始点最短路問題に使える。負閉路の検出にも使える。実装もまあまあシンプル。
    • Bellman-Ford法の解説 - Qiita

  • 桁DP

    • 未満フラグという状態変数を理解することが重要。
    • 「未満フラグが立っている」＝「どんな数字を選んでもよい」
    • xorの問題でもよく使われる。
    • まだサクサクとは書けない。
    • Digit DP 入門 - torus711 のアレ

  • Fenwick Tree（BIT）

    • 区間和を高速に計算できる、かつ、ある要素にある数字を加えていくことができる。
    • 今のところSegment Treeの軽量版、累積和の強いやつみたいなイメージ。あっているかは不明。
    • ABC136Fの解説放送
    • 蟻本3-3

  • bitDP

    • 例題として、巡回セールスマン問題という有名問題が用いられることが多い。
    • 状態集合を添字として持つDP（定義は人によって曖昧らしい）。
    • 蟻本3-4

  • 三分探索

    • 連続関数の極値を求める手法。二分でダメなら三分すればいいじゃない。
    • 通称「さぶたん」（嘘です、聞いたことありません）。
    • 三分探索 - 忘れても大丈夫

★★★：コンテストではまだ一度も使ったことがない

精進の内容

これは私の精進グラフです。

f:id:Rorent:20200504172110p:plain

不思議なグラフの形ですね。経緯が気になる方は自己紹介記事をどうぞ。

以下、2020年3月から入水するまでに行った精進の内容についてです。

  • APG4b3章まで + 4.04.イテレータ

    • 以前は主にPythonで書いていたのですが、3月からC++を勉強し始めました。競プロをやるためにC++を学びたいなら間違いなく最適な教材です。

  • 蟻本の購入

    • 全競プロerが購入すべきだと思います。個人的には前から順に読むものではないと思っていて（DPあたりで心が折れる）、自分のレート帯の問題を解いている際に解説で知らないアルゴリズムが出てき始めたら、蟻本の対応するページを開いて読むとよいです。
    • 一度読んで全く理解できなかったところも、あとから読むとなぜかスッと理解できることがあります。不思議すぎて、書き換えられたのではないかと思うくらいです。

  • AtCoderProblemsのBootCamp全埋め

    • ものすごく力になりました。ひたすら全探索をする問題が多かったです。これを通して「まず全探索を考えてみる」という発想が自然と身についたように感じます。

  • あさかつ、よるかつに毎日参加する

    • AtCoderProblemsで、有志の方が毎日（よるかつはAtCoderのコンテストがない日以外で）企画してくださっているVirtual Contest。
    • Twitterで交流している他の競プロerさんと競い合えて、よい刺激を受けます。

  • けんちょんさんの蟻本記事

    • これは手元に蟻本あってこその記事です。私は蟻本を買う前にこの記事を読んだとき、挙げられているキーワードをヒントに以下の問題を解け、という記事だと勘違いしておりました。
    • そもそも蟻本が前から難易度順に並んでいるかと言われると、そうではないような気がするので、この記事もきっと、前から順に解いていくといったことはしない方がよいと思われます。私はそうして心が折れました。
    • 蟻本を勉強した際に、そのアルゴリズムについて理解を深めたいとき、この記事ほど有用なものはありません。

  • E869120さんの精選100問

    • 水色コーダーになるために解くべき100問をまとめてくださっています。
    • 7割くらい埋めました。個人的にはナップサックDP以外のDP、最小全域木、その他のテクニックあたりは余裕のある方が手をつければよいと思います。私はやれていません。

  • AtCoderProblems Recommendation Medium

    • 私の最近の精進のメインコンテンツです。自分のレート帯なら約50%の確率で解けると推定された問題が表示されます。素晴らしい機能です。
    • 疲れたときはEasyを進めます。Hardは無謀です。

精進のTips

解説ACは悪ではない

解説ACとは、分からなかった問題の解説を読んでからACすることを指します。

「解説ACをできる限りしたくない。解けないのはまだ私の実力が足りていないからだ。」
→気持ちは大変分かります。私もその一人でした。しかし一度見た問題をわからないままにしておくことの方が私にとっては気持ち悪いのです。その問題を解説ACしておくことで実力を高めましょう。

「わからない問題があったら解説を見て理解し、次に出会ったときに解けるようにしておく」
→それができたら一番よいと思います。解説ACしてしまった問題は区別できませんもんね…。ただ、解説を読んで理解しただけで、今後その問題と再び出会った時にACを取れる実装ができるでしょうか。少なくとも私にはできません。せっかく解説を読んで理解したならば、その流れで実装までしてしまった方がお得ではありませんか。

私の実践方法についてです。

青diffまでの問題は、一目見てしまったら、何が何でもACを取っておくようにしています。なぜ青diffまでと決めているかといいますと、自分の理解度的に、それ以上のdiffの問題は解説を読んでも理解し難く感じたのと、継続的にあさかつやよるかつに参加していれば、解説ACをした問題とも再び出会える可能性が高いからです。最近は復習キューをToDoアプリで管理するようにしています。

また、解説ACをする際に、写経は絶対にしません。初めから終わりまで自分で書いたコードでACできるようになることを重視しています。解説を読んで十分に理解したと思っても、実際にコードを書き始めると、意外と書けないという経験はありませんか？自分で書けない部分＝理解し切れていない部分なので、改めてその部分の解説を重点的に、しっかり理解できるまで読みましょう。写経しないと分からない問題が多く感じたら、解説ACの閾値diffを下げればよいかと思います。

解けた問題の復習もしっかり行う

解けた問題についても、解説pdfや解説放送、また他の競プロerさんが書かれている解説ブログを見たりして、実装上より簡潔に書けそうなテクニック等を探すということを意識して行っています。

また、自分の解き方とは異なる解法があれば、それも理解して書けるようにしています。一つの問題を多面的に見る力を養うことで、考察力も上がります。

考察パートと実装パートはしっかり分ける

ある程度難しい問題になってくると、曖昧な考察のままコードを書き始めたところで、うまくいくことは少ないです。 手元に紙とペンを用意して、しっかりと考察しましょう。
考察で行き詰まった時は、

  • 小さいケースでシミュレーションして特徴を捉える

  • 全探索をすることを考えたときに、どの部分で計算量が落とせそうかを考える

とうまくいく場合が多いかと思います。
また、最後にコーナーケースが通るかは確認しておくようにしましょう。

そしてどう実装するかというイメージが固まってきた段階で、やっと実装パートに入るようにしています。きちんと考察できていれば、実装にはそれほど時間はかかりません。

考察が詰め切れていないまま実装し始めると、最悪の場合、実装途中に方針そのものが間違っていることに気付き、全部書き直しになってしまうということにもなりかねません。

Twitterを始めよう

もしこの記事を読まれている競プロerさんで、Twitterをされていない方がいたら、すぐにでも始めましょう。

多くの競プロerはTwitterをしています。特にコンテスト前後のタイムラインはとてつもない流速です。競プロ界隈で話題となったワードがトレンド入りすることもしばしばあります。 また、AtCoder公式情報もTwitterが最速です。

Twitterをしていると、同レート帯の競プロerがどういう精進をしているのか、その日のコンテストに出た問題の多種多様な解法、実装のちょっとしたテクニック、など競プロに関する様々な情報が自然と得られます。
わからないことをTwitterに投げると大抵優しい競プロerさんが丁寧に教えてくださります。
競プロタイムラインは温かいです。

「あなたがTwitterをしている間にライバルは競技プログラミングの問題を解いています。」 と言われて焦ってしまうこともあるとは思いますが、私はTwitterも精進の一貫と考えます。

おわりに

この色変記事で、多くの競プロerさんにとって少しでも役に立つ情報をお伝えできれば幸いです。
最後までお読みいただきありがとうございました。
これからもぜひお互いに切磋琢磨していきましょう。