入青記念アルバム

先日のABC333で入青したのでアルバムを残しておきます。

# プロフィール

Python1年生です。
AtCoderは1年前、Pythonの独学中にフォロワー経由で知りました。
楽しそうだしプログラミング練習にもなるし･･･と始めたらハマりました。

# きろく

__Performance__
レート推移は異常な谷があって壊れています。すいません。
なので内部パフォーマンスの推移をご覧ください。2枚目は[AtCoder Charts](https://atcoder-charts.netlify.app/#/)様のグラフで、破線が内部パフォです。
PAST上級本を終えた参加11回目以降は、だいたい水～青前後で推移しているのがわかるかと思います。
![入青.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3624214/118eb212-5f11-6740-7fbb-00113a9d270f.png)
![パフォ推移2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3624214/5aca4118-2331-5177-4048-09269e1c93e9.png)

__Achievement・Climbing__
入青時点では745AC、割合は灰～黄までほぼ均等にばらけている感じです。
Otherが多いですが、これはPAST本で解いたPAST過去問です。
典型90はサボり気味ですが、★5～★6は意識的に埋めています。
![achieve.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3624214/d27ba2b1-f01d-d8b0-a18a-e18f98fdb72f.png)
![Languages.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3624214/21639b4c-703c-8d4d-a182-f1d19774f573.png)
![Climbing.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3624214/693a6f55-5e78-de1c-7280-8eaa39502d1a.png)
![diff pies.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3624214/9f9e58b6-c3eb-82d7-41ff-559acf38e105.png)
![tenkei 90.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3624214/d3b68f4f-461c-14ef-4011-3d92384a278c.png)

# やったこと

1. [PAST中級本](https://book.mynavi.jp/ec/products/detail/id=120229)
1月の初参加までに一週しました。これの復習で入水まではいけると思います。
ABC-A・Bはだいたい解けるけど、C問題以降は難しい･･･そんなPython勢におすすめです。
ただし基本文法のフォローは弱いので、「if文ってなに？setってなに？」という方には[鹿本](https://www.kadokawa.co.jp/product/321904000758/)から始めることをおすすめします。

2. [PAST上級本](https://book.mynavi.jp/ec/products/detail/id=135840)
入緑してすぐに一週しましたが、ものすごく大変だったので入水してからでよいです。
ABC-Fまでのアルゴリズム面をサポートしています。特にDPとセグ木の章が完成度高かったです。
章末類題は解説がないのでやらなくてよいです。

3. [典型90問](https://atcoder.jp/contests/typical90)
結構サボっていますが、★5・★6は重点的に埋めました。
というのも __PAST本だけだと数学・グラフ・文字列の知識が不足します。__
たとえばmod 998244353での分数計算や二項係数の演算、素因数分解、SCC(強連結成分分解)、Rolling HashやZ-algorithm･･･ これらは他の教材から得る必要があります。
頻出事項なのでABCに出場していれば自然と覚えるのですが、典型90で集中演習するとちょうどよくカバーできます。

4. [EDPC (Educational DP Contest)](https://atcoder.jp/contests/dp)
二週しました。PAST上級本でやりますが、[U - Grouping](https://atcoder.jp/contests/dp/tasks/dp_u)あたりまで押さえれば十分でしょう。
ところで2週目全問TAの記録は6時間でした。いつか3時間切りを目指したいです。

5. [TDPC (Typical DP Contest)](https://atcoder.jp/contests/tdpc)
[全問解説記事](https://qiita.com/navel_tos/items/4dd0b6dbc88db08a9d57)を書くくらいにはやりこみました。
ですが明らかにオーバーワークです。やらなくてよいです。
ところで2週目全問TAの記録は12時間でした。皆様もいかがでしょうか。

6. 私設コン荒らし
yukicoderやMojacoderで定期開催される私設コンテストに沢山お邪魔しました。
ABCと比べると、低難度帯でも工夫が必要な問題が多く刺激になりました。
[MMA Contest](https://yukicoder.me/contests/444)や[緑以下コンテスト](https://yukicoder.me/contests/471)、[take44444_BC](https://mojacoder.app/users/take44444/contests/tbc001)は特に沢山解き直したので記憶に残っています。主催の皆様ありがとうございました。

# できること

手持ちのライブラリをまとめておきます。
上にいくほど苦手です。

||||
|:----: | :---: | :---: |
|凸包|Convex Hull Trick|Li Chao Tree|
|FFT|NTT|kitamasa法|
|最大流|最小費用流|undo-UF|
|中国剰余定理|SCC|最小共通祖先|
|スライド最小値|最大長方形|Z-algorithm|
|ロリハ|2^61-1 modint|行列累乗|
|nCr mod|素因数分解|遅延セグ木|
|UnionFind|二次元累積和|セグ木|

undo可能UnionFindより上のアルゴリズムは、殆ど使わないので自信がありません･･･。
遅延セグ木はPAST本でたたき込まれましたが、これもあまり使いませんでした。

逆にできないことは、ぱっと思いつく範囲だと2-satやEuler Tourあたりですね。
これからがんばります。

# せんりゃく

水diffまでを安定させれば水上位～青下位パフォが取れます。
余った時間で青diffの得意分野を壊せると黄パフォに化けます。
おわりです。

<details><summary>コツ</summary>

後者は運次第なのですが、前者は安全で慣れた実装を増やすのがコツと思います。
具体例で説明します。
たとえば一次元累積和を毎回発明して実装すると、余計な思考量やバグ確率が増えてしまいます。
一方、書きやすく使いやすい「楽な実装」を自分の中で決めておけば、事故率を大きく減らすことができます。
~~~python: 累積和
A = [1, 2, 3, 4, 5]

#1: おすすめ
C = [0]
for i in range(N):
    C[i+1] = C[i] + A[i]
print(C[Rt] - C[Lt])  #sum(A[i]: Lt <= i < Rt)

#2
C = [0] * (N+1)
for i in range(N):
    C[i] = C[i-1] + A[i]
print(C[Rt] - C[Lt-1])  #sum(A[i]: Lt <= i <= Rt)

#3: けわしい
C = A[:]
for i in range(N-1):
    C[i+1] += C[i]
print(C[Rt] - C[Lt-1] if Lt > 0 else C[Rt])
~~~
楽な実装法は、秘伝のタレめいて上級者の間で伝承されています。
上位提出や模範解答を読んで、便利そうなものはどんどん真似しましょう。(終)

</details>

# げんご

Pythonだけ使っています。
コードが簡潔で、多倍長整数や動的型付けで雑処理ができる点が優れています。
言い換えると、初心者に優しいのがPythonの魅力です。
PyPyの再帰が遅く、SortedSetがデフォルトで存在しない点だけ対策すれば、水色までは困らないと思います。

再帰はkemunikuさんの記事に注意点がまとまっています。

https://qiita.com/kemuniku/items/1f1537e1df2ac8180d9b

SortedSetはsortedcontainersか、tatyamさんのSortedSetを使えば大丈夫です。
それぞれの紹介記事を貼っておきます。

https://qiita.com/Shirotsume/items/706742162db68c481c3c

https://qiita.com/tatyam/items/492c70ac4c955c055602

弱点は実行速度の遅さです。
PythonはC++に比べてlog半分くらい遅いです。
初心者のうちは気にならないのですが、解く問題の難易度が上がってからは速度を気にしないといけないケースが増えてきたように感じます。
よく言われる例を示します。

1. [典型043 Maze Challenge with Lack of Sleep](https://atcoder.jp/contests/typical90/tasks/typical90_aq)
想定解が実行時間きつめです。
2. [ABC314G Amulets](https://atcoder.jp/contests/abc314/tasks/abc314_g)
sortedcontainersだと実装方針次第ではTLEします。
3. [ABC322F Vacation Query](https://atcoder.jp/contests/abc322/tasks/abc322_f)
ものすごく工夫しないと想定解も通せません。
4. [PAST第8回-L K-th Abs](https://atcoder.jp/contests/past202109-open/tasks/past202109_l)
logを2個から1個に減らす考察が必須です。かなり大変です。

考察や定数倍高速化を頑張る道もありますが、根本的な解決はC++を使うことです。
主軸のPython・速度のC++と使い分けられるようになりたいですね。


# すきなもんだい

__[ABC068C Cat Snuke and a Voyage](https://atcoder.jp/contests/abc068/tasks/arc079_a)__
PAST本のダイクストラ法の練習問題で解きました。
当時はBFS・DFS・ダイクストラの区別がついていなかったので、別解が多くて楽しい問題だなと感じていました。その名残で今も好きです。
猫のすぬけ君つながりでは、[ABC999](https://atcoder.jp/contests/abc111/tasks/abc111_a)や[Red Scarf](https://atcoder.jp/contests/abc171/tasks/abc171_e)も好きです。

__[ABC155D Pairs](https://atcoder.jp/contests/abc155/tasks/abc155_d)__
億マス計算です。難しいです。
これを$O(N^2 logN)$から$O(NlogN)$に落とす工夫が競プロの醍醐味だと思います。

__[ABC301E Pac-Takahashi](https://atcoder.jp/contests/abc301/tasks/abc301_e)__
基礎の複合問題です。青diffですがかなり好きです。
本番では落としました。

__[ABC331G Collect Them All](https://atcoder.jp/contests/abc331/tasks/abc331_g)__
コンプガチャの問題です。
超難しいですが題材が面白いです。

__[ABC333G Nearest Fraction](https://atcoder.jp/contests/abc333/tasks/abc333_g)__
入青の決め手となった問題です。
実は嘘解法でACしました。すいません。

__[ARC157A XXYYX](https://atcoder.jp/contests/arc157/tasks/arc157_a)__
初0完を喫した思い出深い問題です。

__[AGC051F rng_58's Last Problem](https://atcoder.jp/contests/agc051/tasks/agc051_f)__
有名なAGC最終問題です。
[evimaさんの解説動画](https://www.youtube.com/watch?v=jNHJ3z6L5AQ)を読んで数日かけてACしました。
数学と競プロとパズルの融合といった感じで綺麗な問題でした。

__[AGC062F Preserve Distinct](https://atcoder.jp/contests/agc062/tasks/agc062_f)__
ソリティアです。1週間くらいかけて自力ACしました。
超難しいですが、必要なアルゴリズムの知識はそう多くありません。
皆様もぜひ挑戦してみてください。

# おわりに

おわりです。
にゅうきしたらまたかきます。