中１不登校がatcoderで入緑した話

# はじめに
ABC384で入緑しましたー
えーはい、E問題が比較的簡単で、すぐダイクストラを引き出して、1400台だして、瓦一つすっ飛ばして入緑してしまったんですけどね
こんな感じ
![スクリーンショット 2024-12-17 093156.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3889080/769c725f-f133-ccf1-7ac1-b35a8e0d19ec.png)

入茶したときにも記事書いたので、そちらもよろしく

https://qiita.com/hidehic0/items/0d483f5452cd35c7d49e

# プロフィール
* 中学１年生　不登校
* 長野県在住 松本盆地のどこか
* JOIで本名公開されなかった(**つまり二次予選落ち**)でも本戦行けてたら、一発で割れてた
* python勢
* 他の人よりも、バグらせる確率が高い(なんで)
* 歴史ゲームが好き(音ゲーじゃないです)

半年前にユーザー登録、2か月前に入茶、そして先日のABC384で入緑しました。

# 緑になるためにしたこと
* Atcoder ProblemsのRecommendationでひたすら精進する
これは結構おすすめです。
ちょうどいい難易度の問題が出てくるため、練習になっていいです
</br>

* JOIの過去問を解く
典型的な問題が多いので、結構解きました。
まあメインは、二次予選対策でしたね
</br>

* AHCに出る
いつもと違った面白さが、あって楽しいです。
ちなみに、実装力がなさすぎて、妥協しながら頑張ってます。
レートは780ぐらいです
</br>

* C++を少し勉強する
何かあったときの保険に、C++を入れてます。
基本的にpythonを使うのですが、たまにpypyの再帰関数が遅すぎてTLEするときとかは、使うようにしています
あとAHCには、ほとんどメインにしています。
</br>

* 蟻本と鉄則本を読む
親にアルゴリズムイントロダクション(1.5万円)を勧められましたが、蟻本にしてもらい、少し読みました。蟻本は、グラフ系のアルゴリズムがわかりやすくていいです。
ほかは、ハイレベルであまり読めてません
鉄則本は、アルゴリズムがこんなふうに動いてるとか、ささっと、実装を見たいときに重宝してます。
</br>

* 書いたコードをgitで管理
新しいライブラリを追加するときとか、issue使うとやりやすいです。
あとなんかできる感じがしてなんか楽しい

# やっていないこと
* ARCに出る
レートはつかないし、出たとしても、一完ぐらいも怪しいので、あまり出てません
AJLのスコア稼ぎにしようと思ったらボコボコにされたことが、数回あります
あとdiv2初回、あれのA問題ほんとに400点問題ですか、水diff　ABCの予選レベルじゃん
</br>

* codeforcesに出る
眠すぎて無理
前div3が日本人に優しい時間帯であったのでそこに、出たかったです。
直前リマインダーで親を起こしたことがあります

# 使えるアルゴリズム
理解度の指標
* 1 -> 知らない、または、ほんのちょっとできるぐらい
* 2 -> 典型だったらわかる
* 3 -> 典型から多少外れても、だいたいできる
* 4 -> 難問でない限り、実装可能
* 5 -> 絶対実装可能
ただしあくまでも、筆者の中でのABCのE問題以下の指標としてお考えください

| 名前 | 理解度 | コメント | 
| ---- | ---- | ---- |
| 全探索 | 5 | 基本の基 |
| bit 全探索 | 5 | 確実にわかるけど、実装方法で迷う |
| 二分探索 | 5　| どのパラメータを使えばいいのか迷う | 
| 累積和 | 5 | 標準ライブラリで実装してる |
| imos法 | 4.5| 多分大体できる |
| 尺取法 | 4.5 | バグらせなければだいたいOK |
| DFS BFS | 4 | 出てくるとき、典型のことがほぼない |
| ダイクストラ法 | 4 | BFSより便利な気がする |
| ベルマンフォード法 | 0| 蟻本に載ってるから見ればわかると思う | 
| ワーシャルフロイド法 | 5 | いちばん簡単な、最短経路アルゴリズム |
| UnionFind | 4 | ac-library使ってる |
| セグ木 | 3 | 簡単なのなら |
| 一次元DP | 5 | 確実 |
| ナップサックDP | 4.5 | 難問でない限り |
| bitDP | 3 | 簡単なのなら |
| 確率DP | 3 | フェルマーの小定理がめんどい |
| 期待値DP | 3 | こっちも実装がめんどい |
| 区間DP | 0 | そういえば鉄則本にあったな |
| 素数判定 | 4 | $\log N$のライブラリだからゴリ押せるかも |
| エラトステネスの篩 | 4 | ライブラリ用意済み |
| 素因数分解 | 3 | ライブラリを高速化させたい |
| 繰り返し二乗法 | 4.5| 標準ライブラリで実装してる |
| 他の数学系 | 2 | 数学問題難しくない? |

足りないとこあったら教えて下さい

DPを鍛えすぎるのは、真似しないほうがいいと思います。
あとグラフを、鍛えたいです。

# 使っているライブラリ
[github](https://github.com/hidehic0/my-kyopro-code/blob/main/Performance/.template/code/main.py)に載せてあるので、よかったら見てください。


#### アスキーアート
```text
 _____________________
< it's hidehico's code >
 ----------------------
   \
    \
        .--.
       |o_o |
       |:_/ |
      //   \ \
     (|     | )
    /'\_   _/`\
    \___)=(___/
```
tuxくんかわいい

<details><summary> import系</summary>

```py
from collections import deque, defaultdict, Counter
from math import pi, gcd, lcm
from itertools import permutations
import bisect
import sys
import heapq
from typing import List, Any

# from atcoder.segtree import SegTree
# from atcoder.lazysegtree import LazySegTree
# from atcoder.dsu import DSU

# cortedcontainersは使うときだけ wandbox非対応なので
# from sortedcontainers import SortedDict, SortedSet, SortedList

# import pypyjit
# pypyjit.set_param("max_unroll_recursion=-1")

sys.setrecursionlimit(5 * 10**5)

```

まあ基本的な、pythonでライブラリ使っている人のimport文って感じですかね。
あとCounter一度も使ったことないです。defaultdictをいつも使ってしまう(便利なのは使えよ)

</details>

<details><summary>標準入力の関数</summary>

```py
# 一行に一つのstring
def s():
    return sys.stdin.readline().rstrip()


# 一行に複数のstring
def sl():
    return s().split()


# 一つのint
def ii():
    return int(s())


# 一行に複数のint
def il(add_num: int = 0):
    return list(map(lambda i: int(i) + add_num, sl()))


# 複数行の入力をサポート
def li(n: int, func, *args):
    return [func(*args) for _ in [0] * n]
```

特に普通というですが、複数行入力の関数はこだわりました。
例
input data 
```text
1 1 1
2 2 2
3 3 3
```

この場合、リスト内包表記使って、一行に複数のint型の入力の関数を回すと思うのですが、
liを使えば下のようにスムーズに、書けます

```py
[il() for _ in [0]*3]
```

```py 
li(3,il)
```

li使ったほうがスマートですよね。
おすすめです
なんと行数を指定して、使う関数をいれるだけで、複数行の入力が、可能になります
あと引数もサポートしているため便利です。

ツッコミ: おいstrをlistにしてinputするときはどうするんだ
僕: ・・・・
ツッコミ: 察し

</details>

<details><summary>数学系の関数</summary>

```py
def is_prime(n):
    def f(a, t, n):
        x = pow(a, t, n)
        nt = n - 1
        while t != nt and x != 1 and x != nt:
            x = pow(x, 2, n)
            t <<= 1

        return t & 1 or x == nt

    if n == 2:
        return True
    elif n % 2 == 0:
        return False

    d = n - 1
    d >>= 1

    while d & 1 == 0:
        d >>= 1

    checklist = (
        [2, 7, 61] if 2**32 > n else [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
    )

    for i in checklist:
        if i >= n:
            break
        if not f(i, d, n):
            return False

    return True


def eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0], primes[1] = False, False
    i = 2
    while i**2 <= n:
        if primes[i]:
            for k in range(i * 2, n + 1, i):
                primes[k] = False

        i += 1

    return [i for i, p in enumerate(primes) if p]


def calc_divisors(N):
    # 約数全列挙
    result = []

    for i in range(1, N + 1):
        if i * i > N:
            break

        if N % i != 0:
            continue

        heapq.heappush(result, i)
        if N // i != i:
            heapq.heappush(result, N // i)

    return result


def factorization(n):
    # 素因数分解
    result = []
    tmp = n
    for i in range(2, int(-(-(n**0.5) // 1)) + 1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            result.append([i, cnt])

    if tmp != 1:
        result.append([tmp, 1])

    if result == []:
        result.append([n, 1])

    return result
```

まあ普通に
* 素数判定
* エラトステネスの篩
* 約数全列挙
* 素因数分解
みたいな感じです。

素数判定は、$\log n$で判定できる、ミラー・ラビンの素数判定法にしました
あとは素因数分解の関数を高速化させたいです

</details>

<details><summary>配列生成の関数</summary>

```py
def create_array2(a: int, b: int, default: Any = 0) -> List[List[Any]]:
    """
    ２次元配列を初期化する関数
    """
    return [[default] * b for _ in [0] * a]


def create_array3(a: int, b: int, c: int, default: Any = 0) -> List[List[List[Any]]]:
    """
    ３次元配列を初期化する関数
    """
    return [[[default] * c for _ in [0] * b] for _ in [0] * a]
```

どちらもdp配列の準備とか、グラフ探索に使うflag配列の準備に使いやすいです
まあ３次元のやつは、dpでしか使い所ないぐらいですけどね

</details>

<details><summary>グラフ用のデータ構造</summary>

```py
# 無向グラフ
class Graph:
    def __init__(self, N: int, dire: bool = False) -> None:
        self.N = N
        self.dire = dire
        self.grath = [[] for _ in [0] * self.N]
        self.in_deg = [0] * N

    def new_side(self, a: int, b: int):
        # 注意　0-indexedが前提
        self.grath[a].append(b)
        if self.dire:
            self.in_deg[b] += 1

        if not self.dire:
            self.grath[b].append(a)

    def side_input(self):
        # 新しい辺をinput
        a, b = il(-1)
        self.new_side(a, b)

    def input(self, M: int):
        # 複数行の辺のinput
        for _ in [0] * M:
            self.side_input()

    def get(self, a: int):
        # 頂点aの隣接点を出力
        return self.grath[a]

    def all(self):
        # グラフの内容をすべて出力
        return self.grath

    def topological(self, unique: bool = False):
        if not self.dire:
            raise ValueError("グラフが有向グラフでは有りません (╥﹏╥)")

        in_deg = self.in_deg[:]

        S: deque[int] = deque([])
        order: List[int] = []

        for i in range(self.N):
            if in_deg[i] == 0:
                S.append(i)

        while S:
            if unique and len(S) != 1:
                return [-1]

            cur = S.pop()
            order.append(cur)

            for nxt in self.get(cur):
                in_deg[nxt] -= 1

                if in_deg[nxt] == 0:
                    S.append(nxt)

        if sum(in_deg) > 0:
            return [-1]
        else:
            return [x for x in order]


# 重み付きグラフ
class GraphW:
    def __init__(self, N: int, dire: bool = False) -> None:
        self.N = N
        self.dire = dire
        self.grath = [[] for _ in [0] * self.N]

    def new_side(self, a: int, b: int, w: int):
        # 注意　0-indexedが前提
        self.grath[a].append((b, w))
        if not self.dire:
            self.grath[b].append((a, w))

    def side_input(self):
        # 新しい辺をinput
        a, b, w = il(-1)
        self.new_side(a, b, w)

    def input(self, M: int):
        # 複数行の辺のinput
        for _ in [0] * M:
            self.side_input()

    def get(self, a: int):
        # 頂点aの隣接点を出力
        return self.grath[a]

    def all(self):
        # グラフの内容をすべて出力
        return self.grath
```

見苦しくてすいません
グラフ系のinputってめんどいので、いっそのことclassにまとめちゃいました。
無向グラフの方には、トポロジカルソートのライブラリを追加したり、色々しました。

</details>

# 今後できるようになりたいこと
* 最大フロー
~~最大風呂ーとtypoしそうになりました~~
たまに出る印象があるので鍛えたい
あと二分マッチング問題でも、フローアルゴリズムを使うので、できるように、なりたいです。
* シグマ系の問題を鍛えたい
最近のE問題で頻出のシグマを、もう少しできるようになりたいです。
そしていつも、解法が違うのでわかりにくいです

* 応用力を高めたい
難しいDFSとかBFSとかの問題で戸惑ってしたりするので応用力を、高めたいです。

# 進捗写真
![スクリーンショット 2024-12-17 121822.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3889080/2bb1a8cf-f74f-745c-0083-67c8995c661d.png)
![スクリーンショット 2024-12-17 121858.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3889080/4c84495e-1c6f-e367-ab61-d4b6311a7c68.png)
下半分は全然ですね

# 最後に
なんか卒業文集みたいですいません
入水目指して頑張ります。
まあ最初は落茶を避けたいです。

# 追記
githubに上げているコードのライセンスが、GPLライセンスになっておりコピーレフトが必須の状態になっていました。
ライセンスをMITライセンスに変えたため、今はコピーレフトの条件は外れています
申し訳ございません