入青記念アルバム

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

プロフィール

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

きろく

Performance
レート推移は異常な谷があって壊れています。すいません。
なので内部パフォーマンスの推移をご覧ください。2枚目はAtCoder Charts様のグラフで、破線が内部パフォです。
PAST上級本を終えた参加11回目以降は、だいたい水～青前後で推移しているのがわかるかと思います。

Achievement・Climbing
入青時点では745AC、割合は灰～黄までほぼ均等にばらけている感じです。
Otherが多いですが、これはPAST本で解いたPAST過去問です。
典型90はサボり気味ですが、★5～★6は意識的に埋めています。

やったこと

1. PAST中級本
   1月の初参加までに一週しました。これの復習で入水まではいけると思います。
   ABC-A・Bはだいたい解けるけど、C問題以降は難しい･･･そんなPython勢におすすめです。
   ただし基本文法のフォローは弱いので、「if文ってなに？setってなに？」という方には鹿本から始めることをおすすめします。

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

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

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

5. TDPC (Typical DP Contest)
   全問解説記事を書くくらいにはやりこみました。
   ですが明らかにオーバーワークです。やらなくてよいです。
   ところで2週目全問TAの記録は12時間でした。皆様もいかがでしょうか。

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

できること

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

凸包	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の得意分野を壊せると黄パフォに化けます。
おわりです。

コツ

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

累積和

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])

楽な実装法は、秘伝のタレめいて上級者の間で伝承されています。
上位提出や模範解答を読んで、便利そうなものはどんどん真似しましょう。(終)

げんご

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

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

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

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

1. 典型043 Maze Challenge with Lack of Sleep
   想定解が実行時間きつめです。
2. ABC314G Amulets
   sortedcontainersだと実装方針次第ではTLEします。
3. ABC322F Vacation Query
   ものすごく工夫しないと想定解も通せません。
4. PAST第8回-L K-th Abs
   logを2個から1個に減らす考察が必須です。かなり大変です。

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

すきなもんだい

ABC068C Cat Snuke and a Voyage
PAST本のダイクストラ法の練習問題で解きました。
当時はBFS・DFS・ダイクストラの区別がついていなかったので、別解が多くて楽しい問題だなと感じていました。その名残で今も好きです。
猫のすぬけ君つながりでは、ABC999やRed Scarfも好きです。

ABC155D Pairs
億マス計算です。難しいです。
これを$O(N^2 logN)$から$O(NlogN)$に落とす工夫が競プロの醍醐味だと思います。

ABC301E Pac-Takahashi
基礎の複合問題です。青diffですがかなり好きです。
本番では落としました。

ABC331G Collect Them All
コンプガチャの問題です。
超難しいですが題材が面白いです。

ABC333G Nearest Fraction
入青の決め手となった問題です。
実は嘘解法でACしました。すいません。

ARC157A XXYYX
初0完を喫した思い出深い問題です。

AGC051F rng_58's Last Problem
有名なAGC最終問題です。
evimaさんの解説動画を読んで数日かけてACしました。
数学と競プロとパズルの融合といった感じで綺麗な問題でした。

AGC062F Preserve Distinct
ソリティアです。1週間くらいかけて自力ACしました。
超難しいですが、必要なアルゴリズムの知識はそう多くありません。
皆様もぜひ挑戦してみてください。

おわりに

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