Atcoderで水色になった！

はじめに

先日のARC157で水色になりました！うれしい！

本記事では主に勉強した内容について記載します。

自己紹介

• データ分析の仕事、社会人2.9年目
• 旧帝大の非情報工学の修士卒
• 高校数学はとても好きだった。
• Atocoderを始めた当初はプログラミングに関してほぼ無知識（研究でMatlabを少し触っていた程度)

Atcoderを始めたのは院生時代（始めたきっかけは忘れました）。数学は得意な方だったのですぐに緑色・水色にはなれるだろうと思って始めましたが、考えが甘かったです。Atcoder難しい😢
以下は現在のレート推移です。

勉強方法

灰色→茶色

ABC(Atcoder Beginner Contest)に参加する以外の精進はほぼ何もしていないです。したことといえばc++の文法を勉強したくらい。longlong型なんかはABCに参加して初めて知りました。
新しく覚えたアルゴリズムは何もなかったとおもいます（貪欲解法?のものしか解けなかった）
（当時に比べると、今は灰茶の段階でも基本的なアルゴリズムを知る必要があるかもしれないです。）

身についたこと

• c++の文法
• 計算量の感覚

茶色->緑色

引き続きABCには参加しましたが、過去問を解くような精進はあまりしていません。代わりに、「レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】」 等を参考に、基本的なデータ構造・アルゴリズムを勉強してライブラリとして整備しました。
ライブラリを整備する際は「計算量・使用用途・例題」の3つは同時に記載するようにしました。

この期間でライブラリ化したデータ構造・アルゴリズムは以下の通りです。

• 二分探索
• 累積和, イモス法
• DFS, BFS
• ダイクストラ法
• UnionFind
• 順列全探索, bit全探索
• 逆元, 二分累乗法, 二項係数
• 約数列挙, 素因数分解, エラストテネスのふるい
• DP(ナップサック等)

当時はダイクストラ法・UnionFind・逆元あたりは中身をあまり理解せずに使っていました（問題を解く中でアルゴリズムの中身の理解が必要に迫られることがあり、そこで都度勉強することで今はなんとなく理解できています。）

また、標準ライブラリの使い方等を自分用に整理しました（計算量がよくわからなくなることがあり、ネットで逐一調べるが面倒になったため）。

基本的なアルゴリズムを勉強したことでABCのDがちょこちょこ解けるくらいのレベルに行き着いたのがこの時期です。

身についたこと

• 基本的なアルゴリズムへの理解

緑色→水色

緑になった時点で、就活が始まりAtcoderからは遠ざかっていましたが、社会人2年目になって再開しました（きっかけは忘れました）。

緑色->水色は、緑色になるまでと比べてかなり難しかったです。時間で言うと、緑色->水色は緑になるまでと比べて10倍は勉強したと思います。
私の競技プログラミングの知識はほとんどこの期間で身についたといっても過言ではない。

以下にこの期間にやったことを記載します。

典型考察集の作成

後述するようにこの頃から過去問を解き始めましたが、解説文で「この考察はよくある典型です」の文字列をよく見かけるようになりました。これまでは名前の付いたアルゴリズムを覚えること目が行きがちでしたが、考察の仕方にも典型要素があることに気づいてからは、いつでも引っ張り出してこれるようにとこれらを自分のメモとしてまとめていくことにしました。

学生時代と違い競技プログラミングにかけられる時間はそんなに多くはないので(仕事疲れるし）、せっかく身に着けた知見を風化させない意味でも、メモにまとめることは非常に良かったと思います。メモとして残していると、ふとした時に復習をしたくなりますし。

過去問を解く中で、これは使えそうなテクニックだなと思ったものはどんなものであれメモに記録しました。
以下は自分の典型考察メモの一部ですが、今では500行程度の大きさになっています。

- グラフの問題に帰着させる
    - 順序関係がある場合->有向グラフ
    - 2つに対して何かするのは頂点間に辺を張る操作に帰着しやすい
    - 最小系問題は最小全域木やダイクストラ法が使えないか
    - grid座標をグラフ化する(x, yを別の頂点として扱うなど abc131f)
- 2変数ある時は片方を固定する
    - 3変数は中央を固定
    - 片方は二分探索で求める
    - 任意の区間i,jに関して条件を満たす数え上げやminmaxなどを求める場合は, 右側を固定してその左側を探索するのは典型
        - ex1 数え上げ: f(i) =(or <) g(j)のように変数分離の形にできる場合, cnt[f(i)]を記録しながら右端jを全探索すればcnt[g(j)]でansが取得できる abc146e, abc164d, abc166e
        - ex2 minmax(二次元): ans=min[f(i, j) + g(i', j')] (i < i', j < j')のようなとき、min[f(i,j)]を記録しながらi', j'を探索すれば高速にansが計算できる 210d

### クエリ系問題
- クエリ先読み
- 前計算で求める
- 値を別途持って置き、それだけを更新していくことで計算量を減らす
- データ構造を使用して各クエリを高速に計算
    - セグメント木等, priority_queue等STL
    - 木データ構造(永続スタック?) abc273e
- 差分計算
- Mo's Algorithm
    - 区間内の種類数
- 2グループに分けてデータを格納する -差分更新 × 先頭からK個に関して答える問題 
    - 先頭K個を格納するmultisetとそれ以外のM-K個を入れるmultisetの2種類とK個に対する値(合計値等)を変数として順に更新していく abc281e
- 合成関数を前処理で作成してクエリに答える
    - 変換行列の積
    - minmaxの合成関数　abc196e

競技プロ典型 90問

典型だからある程度解けるだろうと思って望んだら1問目から撃沈しました。
結構難しめですが、勉強になる問題ばかりです。

難易度が★1~★7までありますが、私は★6までのすべてを解きました。正直★6は解説を見ても理解に苦しむ問題ばかりですが、この難易度の問題をこの時期に解いてよかったと思っています。自分より上のランク(水・青~）に必要な知識がどのようなものを理解することで、その後の精進で似たような問題に出会ったときに逃げなくなります。例えば★6の問題でgrundy数というものを初めて勉強したのですが、arc151c問題の解説でgrundy数に出会っても怖気ずに済みました。要はアルゴリズムや典型要素は難しいものでも早めに勉強しておくの精神でやるということです）

EDPC（Educational DP contest）

DPの苦手意識はこれを解いてからなくなりました。今ではDP来たらラッキーくらいの感じです。

ライブラリ整備

引き続き新たなアルゴリズム・データ構造を学習しました。基本的には、過去問や上記の問題たちを解いていく中で出会ったものについて勉強する方針です。

以下は、この期間で身に着けたアルゴリズム・データ構造です.

名称	使用頻度※	その他
重み付きUnionFind	1
ベルマンフォード法	3
ワーシャルフロイド法	3
クラスカル法	2
プリム法	1	最小全域木はクラスカルでしかやったことがない
最近共通祖先(LCA)	4
オイラーツアー	3	好き
二次元累積和	3
イベントソート	1
桁DP	2	理解してはすぐ忘れる
区間DP	2	好き
bitDP	3	ややこしい
部分列DP	1
三分探索	1
0-1BFS	2	ダイクストラで代用する人多そう
最長共通部分列(LIS)	3
座標圧縮	3
ダブリング	2	意外と最近出会っていない
強連結成分分解(SCC)	1	有向グラフが出たらすぐにこれを疑うようにしてるけど出会わない..
BIT(fenwick tree)	1	すべてセグメント木で対応していたので個人的には使用しなかった
セグメント木・遅延評価	5
トライ木	1
Mo's Algo	3
幾何	2
行列操作・行列累乗	3
半分全列挙	3
ローリングハッシュ	4
game系	4	grundy数・minmax・後退解析
DFS全探索	5	めっちゃ好き
中国剰余定理	1

※使用頻度は5段階で5:多用, 3:ぼちぼち, 1:1・2回しか使用したことがない（≒個人的な理解度）

過去問精進

過去問をたくさん解きました。灰や茶diffよりは緑から青diffを中心に解くようにしました

身についたこと（感想）

• DFSの苦手意識がなくなった
  • 以前はBFSで探索するところをBFS・DFSを使い分けて書くようになった
  • DFS全探索が便利なことに気づいた
• 緑diffまでの典型問題ならすぐに解法が浮かぶようになった
• 「アルゴリズムすこしわかります」と頭の中で言えるようになった

その他お世話になったサイト

• かっつぱ競プロ
  • 典型90の解説等でお世話に
  • 上位の人がどのように考えて解法に至っているかわかるので、典型なのかそうでないのか等よくわかる
• アルゴリズムロジック
  • ライブラリ整備の際にめっちゃ参考にさせてもらった.

水色->

とりあえず青色を目指してゆっくり頑張る