はじめに

ABC384で入緑しましたー
えーはい、E問題が比較的簡単で、すぐダイクストラを引き出して、1400台だして、瓦一つすっ飛ばして入緑してしまったんですけどね
こんな感じ

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

プロフィール

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

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

緑になるためにしたこと

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

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

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

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

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

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

やっていないこと

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

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に載せてあるので、よかったら見てください。

アスキーアート

 _____________________
< it's hidehico's code >
 ----------------------
   \
    \
        .--.
       |o_o |
       |:_/ |
      //   \ \
     (|     | )
    /'\_   _/`\
    \___)=(___/

tuxくんかわいい

import系

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をいつも使ってしまう(便利なのは使えよ)

標準入力の関数

# 一行に一つの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

1 1 1
2 2 2
3 3 3

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

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

li(3,il)

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

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

数学系の関数

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$で判定できる、ミラー・ラビンの素数判定法にしました
あとは素因数分解の関数を高速化させたいです

配列生成の関数

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でしか使い所ないぐらいですけどね

グラフ用のデータ構造

# 無向グラフ
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にまとめちゃいました。
無向グラフの方には、トポロジカルソートのライブラリを追加したり、色々しました。

今後できるようになりたいこと

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

進捗写真

下半分は全然ですね

最後に

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

追記

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