はじめに
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ライセンスに変えたため、今はコピーレフトの条件は外れています
申し訳ございません