physharpと申します。Qiita初投稿です！
Pythonでプログラミングを初めて2年、AtCoderを初めて1年4ヶ月ほどで青になりました。
（次のコンテストで、早速、水に舞い戻るやもしれないので、急いで書いてます！）
「このRate帯では、このくらいのアルゴリズムやデータ構造の知識が必要」みたいのは、
他の方が多くまとめられているので、本記事では一味違った『僕ならでは』の勝ち戦略を、
ライブラリの実装コード等も交えながら、お伝えできればと思います。
主に、PythonでRate帯1000-1500くらいの人に参考になればなぁと思ってますが、
Python以外の言語の人や、対象Rate帯以外の人にも『競プロで勝つ』って意味で、
面白く読んでいただけたら、嬉しいです。（特に「3.1.強い武器」の話あたり！）
3完早解きに成功！初黄パフォで入青です！
— physharp (@physharp) May 16, 2021
「一部上場のIT企業でも、一人もいないことが結構あるレベル」です(≧▽≦)
physharpのARC119での成績：237位
パフォーマンス：2159相当
レーティング：1537→1617 (+80) :)
Highestを更新し、2 級になりました！#AtCoder #ARC119 https://t.co/27z8eEAHme
#目次
#1. バックグラウンド
- 非エンジニア
- Pythonでプログラミングを始めて2年
- AtCoder純粋培養（Codeforcesもyukicoderもやってないです）
- 高校数学までは得意（昔、東大数学で8割取りました）
- 既婚子持ち（4人家族）
- データサイエンスに興味あり（そのうちKaggleにも出たい！）
#2. 競プロで勝つための戦略
##2-1. 『競プロで勝つ』とは
###長期的な目線でいうと
上のスクショは、直近のコンテスト成績です。
1500に到達してから、1ヶ月ほどで一気に青になることができました。
その間にもABCで過去最大の冷えを2回経験してますが、翌日のARCで2回とも挽回しました。
要するに、多少冷えることがあっても、それ以上に勝てば長期的にはRateは上がる訳です。
なので「冷えを無くして安定させる」よりも「ドカンと勝つ」ことを意識して書いてます。
「冷えを無くして安定させる」には、何よりも問題をたくさん解くことにつきます。
僕自身も安定感を上げるために、1200問以上AtCoderの問題を解いてきました。
ですが、安定感出すって意味だとこの記事「いっぱい解きましょう」で終わっちゃうし、
わざわざ書く意味も無いと思うんですよね><
「ドカン」と勝ちたくないですか？
###１回１回のコンテストでいうと
まずAtCoderのコンテストのルールを確認してみましょう。
- コンテスト中に問題に正解すると点数を獲得できます。
- 順位は総合得点で決定します。
- 同点の場合は提出時間の早い人が上の順位になります。
- 誤答を提出するたびにペナルティが加算されます。ペナルティは5分です。
つまり、「配点の高い問題を解くこと」、「正確に早解きすること」が求められていて、
「配点の高い問題を解くこと」の方がより重要ってことですね。
（実際には、「難しい問題を解く」時間を十分に確保するために、簡単な問題を「正確に早解きしておく」必要があります。）
前置きはこのくらいにして、僕なりの勝つための差別化戦略の話、聞いてください！
##2-2. 勝ちパターンの分析・具体例
ここでは、過去パフォBest3の勝因を自分なりに分析してお伝えしたいと思います。
1stは早解き、2nd, 3rdは高難度の典型問題で勝利した回になります。
早解きで稼いだRateも嬉しいのですが、早解きでのRateってその次の問題のdiffに大きく左右されるので、あまり本質的ではないですね。
1ランク上の問題を解き切ることが、Rateを継続的に上げる鍵になります。
そのときに、自分ならではの強い武器を持っていることが、重要です。
それぞれ、具体的に見てみましょう！
###1st. ARCで早解き大成功 (Performance=2159)
記念すべき、青になった回ですね！
この回のARCは、D問題以降がかなり難しく、A～C問題までの早解き勝負となりました。
（ARCは中級者向けのコンテストで、自分のRateと配点の相性によって、早解き勝負となる可能性が高くなる場合があり、ギャンブルになります。そのため、僕は配点を見た上で出場するか決めています。）
そしてラッキーなことに、僕は3問を30分弱で早解きすることに成功しました。
ここでは、後ほど4章で解説する『早解きの技術』が役に立ちました！
ただ、先ほどご説明したとおり、早解きで稼いだRateは水物ですw
あまり手放しでは喜んでいられないですね。。
###2nd. 行列累乗ライブラリで大勝利 (Performance=1941)
D,Eが青diffで解けず、A～Cの3完を覚悟しましたが、F問題をぐっと見たら、行列累乗が見えました！
"EDPC-R - Walk"で、行列累乗をライブラリ化してたので、実装も20分ほどで間に合いました。
残り10分切っての大逆転で、思わず部屋で雄叫びを上げてしまい、妻にびっくりされましたw
黄diffがACできたのは唯一この回だけで、『高難度を倒して勝つ』のはマジで最高でした！
記念に、行列累乗ライブラリを貼っておきます。比較的、シンプルですね。
modを取れれば便利そうですが、ModIntライブラリは別途作ったので併せ使いで戦いました。
####行列累乗ライブラリ
行列累乗ライブラリの実装コードを見る
def dot(A1,A2,n):
# n:行列のサイズ
A = [[0]*n for _ in range(n)]
for i in range(n):
for j in range(n):
for k in range(n):
A[i][j] += A1[i][k]*A2[k][j]
return A
def pow_mat(A,k,n):
# A:累乗する行列, k:累乗数, n:行列Aのサイズ
P = [[0]*n for _ in range(n)]
for i in range(n): P[i][i] = 1
while k:
if k&1: P = dot(P,A,n)
A = dot(A,A,n)
k >>= 1
return P
####ModIntライブラリ
ModIntライブラリの実装コードを見る
MOD = 10**9+7
class ModInt:
# 計算で使う際には、ModInt型の宣言が必要
def __init__(self, x):
self.x = int(x) % MOD
def __repr__(self):
return str(self.x)
def __int__(self):
return self.x
def __mod__(self, mod):
return self.x % mod
def __add__(self, other):
return ModInt(self.x + other)
__radd__ = __add__
def __sub__(self, other):
return ModInt(self.x - other)
def __rsub__(self, other):
return ModInt(other - self.x)
def __mul__(self, other):
return ModInt(self.x * other)
__rmul__ = __mul__
def __floordiv__(self, other):
return ModInt(self.x * pow(other, MOD-2, MOD))
__truediv__ = __floordiv__
def __rfloordiv__(self, other):
return ModInt(other * pow(self.x, MOD-2, MOD))
__rtruediv__ = __rfloordiv__
def __pow__(self, exp, mod=MOD):
return ModInt(pow(self.x, exp, mod))
"ABC199F - Graph Smoothing" <最終提出コード>
###3nd. 拡張ユークリッドの互除法で頑張る (Performance=1899)
この回もかなり苦しんだ末に、残り3分で大逆転した思い出深い回ですね、、！
拡張ユークリッドの互除法は、数学が活かせる相性の良い問題でした。
（"ABC186E - Throne"でも勝ちました！）
要は、整数の組 (a, b) に対して、ax+by=1 となる整数の組 (x, y) を求めるだけです。
しかし、拡張ユークリッドの互除法は用意していたものの、中国剰余定理まで作っておらず、
バグらせまくって死にかけました。
ACLにも入ってるしで反省を活かして、中国剰余定理も含め、ライブラリを再整備しました。
今回は特別に大放出です！！（執筆が深夜帯に入り、テンションがおかしくなってきたw）
####extGCD/CRTライブラリ
extGCD/CRTライブラリの実装コードを見る
INF = float('inf')
# extgcd & crt
def extgcd(a,b):
'''
a*x+b*y==1を満たす整数(x,y)を求める
abs(g)!=1の場合、解なし
'''
if b:
y,x,g = extgcd(b,a%b)
y -= a//b*x
return x,y,g
return 1,0,a
def extgcd_min_xy(a,b,c):
'''
a*mx+b*my==cを満たす最小の非負整数(mx,my)を求める
解がない場合、INFを返す
'''
x,y,g = extgcd(a,b)
if g<0: x,y,g = -x,-y,-g
q,r = divmod(c,g)
if r: return INF,INF
mx = (x*q) % (b//g)
my = (y*q) % (a//g)
return mx,my
def crt(lr,ld,m=0):
'''
以下n個の条件を満たす、最小のy(m以上)を求める
x == lr[i] (mod ld[i]) i:[0,n)
答えがある場合 : 以下を満たす(y,z)を返す
x == y (mod z), 0 <= y < z == lcm(ld[i])
答えがない場合 : (INF,0)を返す
入力がない場合 : (0,1)を返す
'''
ra,a = 0,1
for rb,b in zip(lr,ld):
x,y,g = extgcd(a,-b)
if g<0: x,y,g = -x,-y,-g
q,r = divmod(rb-ra,g)
if r: return INF,0
l = a*b//g
ra,a = (a*x*q+ra-m)%l+m,l
return ra,a
"ABC193E - Oversleeping" <最終提出コード>
#3. 高難度を倒して勝つ
先ほどの「2nd 行列累乗」や、「3rd 拡張ユークリッドの互除法」の話は、
やってきたことの歯車がようやく嚙み合って、Rateにつながった例ですが、
こういう勝ち方を増やしていくのが、最も重要だと思います。
##3-1. 自分に合った強い武器を
手段として『高難度典型をライブラリ化して使いこなせるようにしとこう』って話です。
Pythonでやる以上、ACL関連のライブラリは、使えるように整備しておく必要がありますし、
本番中に貼るだけの典型は、出題頻度が低くとも持っていれば「勝ち」に近づきます。
水色の間に作って、「これで勝ちたい」と思ってライブラリ化したものを上げておきます。
少し背伸びしたアルゴリズムが1つ2つでも使えると、ハマった時に大勝できるので是非！
細かいスニペット（詳細は４章で）も含めると、100件弱を召喚できるようにしてあります。
簡単にご紹介しますが、気になるものは是非調べてみてください。
###【僕の✝高難度典型✝ライブラリ】
- データ構造
- 削除可能Heapq（疑似的に削除して、heappopで取り出さないようにする）
- 一般化BIT（xorとか掛け算でも使えたり、二分探索も出来るBIT）
- 数学
- 高速素因数分解（エラトステネスの篩の応用）
- 内積・行列累乗（線形代数の知識がいるので、使いこなすのが難しい）
- グラフアルゴリズム
- トポロジカルソート（DAGの頂点に順序関係を与える）
- 木DP / 全方位木DP（概念は意外と難しくないけど、実装が難しい）
- その他アルゴリズム
- 三分探索（凸関数の、最大値or最小値を求める）
- bitDP（ライブラリではないけど、TSP以外でもbitでの集合管理に慣れておくと強い）
※ 一般的なアルゴリズムやデータ構造については、他に良い記事があるので割愛します。
競プロ典型90問もやってるE869120さんの以下の記事が、とても参考になりました。
<参考> レッドコーダーが教える、競プロ・AtCoder上達のガイドライン
###削除可能Heapqライブラリ
ここで、Pythonistaの皆さんのために特別に、『削除可能Heapq』のライブラリをご紹介します。
C++では標準で使える、順序付き集合setの代わりに使えたりします。
中身としては、削除予約のためのheapqをもう1本用意して、処理していく感じです。
水diffの問題でも、これが無いとPythonでは苦労する場合もあるので、是非この機会に！
削除可能Heapqライブラリの実装コードを見る
from heapq import *
class Heapq:
'''
Heapq() : 本体qと削除用pの2本のheapqを用意する
build(a) : 配列aからプライオリティキューqを構築する
push(x) : プライオリティキューにxを追加
erase(x) : プライオリティーキューからxを(疑似的に)削除
clean() : 削除予定でトップに来た要素をq,pからpop
pop((exc)) : トップの要素をqからpop (qが空の場合、excを返す)
top((exc)) : トップの要素の値を取得 (qが空の場合、excを返す)
'''
def __init__(self):
self.q = []
self.p = []
def build(self, a):
self.q = a
heapify(self.q)
def push(self, x):
heappush(self.q, x)
def erase(self, x):
heappush(self.p, x)
self.clean()
def clean(self):
while self.p and self.q[0]==self.p[0]:
heappop(self.q)
heappop(self.p)
def pop(self, exc=None):
self.clean()
if self.q:
return heappop(self.q)
return exc
def top(self, exc=None):
self.clean()
if self.q:
return self.q[0]
return exc
【演習問題】"ABC170E - Smart Infants"
（水diffですが、Pythonistaにはなかなか実装がしんどいです）
#4. 正確な早解きで勝つ
『正確に早解き』する観点でも、僕なりの観点でまとめてみました。
（「4.2.コードゴルフ」は、半分ギャグですが半分マジですw）
(5/25 追記)
またもやE869120さんので（C++ですが）綺麗にまとまってる記事がありました！
<参考> [実装力で戦える！～競プロにおける実装テクニック14選～] (https://qiita.com/e869120/items/920a6e63435bf6efe539)
##4-1. VSCodeによる環境整備
始めて半年くらいは、恥ずかしながらコードを提出欄に直打ちしてたのですが、レートが3桁になった頃に、VSCodeを使うようになりました。
圧倒的に早く正確にコードを書けるので、環境を整えるのは少し大変ですがおススメです。
（丸一日くらい、環境を整えるのに奮闘してました。）
何といってもスニペットでライブラリを呼び出せるのが最強なので、是非使ってください！
###【VSCodeを利用するメリット】
- シンタックスハイライトがある
- コードを自動補完してくれる
- スニペットでライブラリを呼び出せる
###コーディング環境整備
"ABC200A - Century"の例でご説明します。
- 「Source Code」のところに、提出コードを記述します。
- 「Sample Input」のところに、入力例を貼り付けます。
- ターミナルで実行すると、実行結果と実行時間(xx ms)が出力されます
import sys, io, time
# Sample Input
Input = '''\
2021
'''
sys.stdin = io.StringIO(Input)
Start = time.time()
# Source Code
n = int(input())
print((n+99)//100)
# Exec Time
End = time.time()
Exec = End - Start
print(f'{int(Exec * 1000)} ms')
21
0 ms
###スニペット整備
よく使う処理やライブラリは、スニペット登録しておくのがおススメです！
Ctrl+Shift+Pで、コマンドパレットを表示して、検索に「snippets」と入力すると、
「基本設定: ユーザー スニペットの構成(Preferences: Configure User Snippets)」が出ます。
スクロールして、新しいスニペットからpython.jsonを作成しましょう。
スニペットの中身は以下のように記載すると、コーディング時にgraph_list_cpと入力すると、
下のコードが生成されます。（グラフや木の入力の受け取りで、よく使うやつですね。）
####スニペット本体
"graph_list_cp": {
"prefix": "graph_list_cp",
"body": [
"${1:f} = lambda:map(int,input().split())",
"${2:n},${3:m} = $1()",
"${4:g} = [[] for _ in range($2)]",
"for _ in range($3):",
" ${5:a},${6:b} = $1()",
" $4[$5${7:-1}] += [$6$7]",
" $4[$6$7] += [$5$7]"
]
}
####スニペットから呼び出した結果
f = lambda:map(int,input().split())
n,m = f()
g = [[] for _ in range(n)]
for _ in range(m):
a,b = f()
g[a-1] += [b-1]
g[b-1] += [a-1]
##4-2. シンプルなコーディング
上のスクショは、青になったARC119での僕の提出です。
3問合計で、わずか517Byteで黄パフォですよ？！ 凄くないですか？！
日頃のコードゴルフの特訓の成果が、この早解きに現れました！
（コードゴルフとは、「可能な限りもっとも短いソースコードで記述する」ことです。）
pep8とか無視したコーディングしてますが、開発では無いし自分で読みやすければ十分。
一文字変数とかも、添え字の問題とか良く言われますが、自分なりにどんなシーンでどの文字使うかを体系化できていればそんなに困りませんし、むしろ変数名を悩まなくて済みます。
（というのは嘘で、よく変数の競合が発生して悩んでますが、、）
どんな感じで体系化してるかをこの記事で解説しようかと思ったのですが、割愛します。
（例えば、c: count or cost, d: dict or distanse or direction、みたいな。もう競合してますが、）
ans, dp, resなどは、さすがにバグらせないの優先で、本番中は略さずに書いてます。
まぁ一文字変数の是非はさておき、コードゴルフは楽しいし、シンプルにコードを書くにはどうするかを考えるには良い材料です。純粋にハマるし「勝ち」にも繋がるので、モチベーション維持にも役立ちます。皆さんも是非！
#5. おまけ（いわゆる入青記事）
どうしてもどこかで読んだことのあるような内容になるので、後ろに回しちゃいましたが、
普通の入青記事っぽい内容も書いておきます。実は、結構良いこと書いてる気がする←
##5-1. 精進の記録
水から青にかけて、重点的に取り組んだのは以下のとおりです。
- ABC-D： 試験管以外
- ABC-E： 全埋め
- ABC-F： 青diff以下を中心に半分ちょっと
- ARC-B： 全埋め
- AGC-A： 全埋め
- EDPC ： 22/26(Vまで)
- ACLPC： DSU, BIT, FFT, SCC, セグ木, 遅延セグ木
- 競プロ典型90問： ★7以外
明日100点を解くと、Streak Sumが300日、RPSが28万（いわゆる赤パフォ精進）になります。
Shortestは、全盛期で4問とかですね。
コードゴルフのこと書いてる割にショボすぎ（kotatsugameさん強すぎw）
青diff以上がだいぶ増えてきたのが、成長の証って感じがしますね！
1200ACを記念して、赤diffにしてABC最高難度の"ABC176F - Brave CHAIN"も解説ACしました。
水手前で4ヶ月強の停滞期(1137@6/27→1148@11/1)がありましたが、全然精進してない。。
当時は、十分水にはなれる力があると思ってたのですが、これ見るとそれはそうって感じ。。
精進は良い意味でも悪い意味でも裏切らないですね。
##5-2. 具体的な精進方法
###とにかく令和ABC埋めを
確かevimaさんも言ってましたが、令和ABC（ABC126以降）埋めで青までは十分だと思います。
僕は、CodeforcesもTopCoderもyukicoderもAOJも、他のサービスは全く使わなかったです。
AtCoderはそれだけの開催頻度もあるし、質の高い問題が揃ってると思います。
バチャもいつでもやれる公式バチャで、過去のお気に入りの皆さんと対戦してました。
AtCoder以外だと、有名な「蟻本」は、中級編の途中までやりました。
ABCは、緑まででD問題を中心にやって、水からはE,Fにチャレンジしてた感じです。
今でもほぼ解説ACになっちゃいますが、F問題は新しい学びがあるので楽しいですね！
令和ABC以外だと、「EDPC」と「競プロ典型90問」は、かなり力がつくと思います。
###解説ACは積極的に
多くの問題に触れると同時に、一問一問を深く理解することが上達の近道だと思います。
始めは自力では解けなくても、次に見たらスラスラと解けるようになっているのが理想で、
ついでに類題も含めて、練習しておくと効果的に伸ばせると思います。
AtCoder公式のsnukeさんの「ABC解説放送」は、特におススメです！
考察の仕方から実装の仕方（C++ですが）まで、かなり参考になります。
解けたけど、実装がいまいちだと思う時も、見てコードを書き直すようにしてます。
###Streakは難しめの問題で
2020.11～2021.3まで128日Streakを繋いで、この間に1200から1400くらいまで上昇しました。
少し意識していたことがあって、出来るだけ水or青diffでStreakを繋ぐようにしてました。
（どうしてものときだけ、AGCのA問題とかを慌てて解いて繋いでたりしましたが、、）
いわゆる虚無埋めもウォーミングアップには良いですが、それで繋いじゃうと微妙ですね。。
少し余裕があるときは、過去のABCバチャをやると早解き・実装力もキープできて良いかと！
##5-3. 今後やりたいこと
精進量をキープするのが難しいので、これ以上を目指すのはなかなか厳しいですが、
もし上を目指すなら、以下のようなことやってくかなー、って感じです。
PyPyの再帰弱いし、他はACLとかC++の標準機能なので、ガチるならC++始めた方が良いかな？！
（実は、APG4bを1章だけやってたりします。）
- DFS全探索・メモ化再帰の習熟
- 最大流・最小費用流
- 2-SAT
- 平衡二分探索木
- 形式的べき級数
- Euler Tour
- Wavelet Matrix
ちなみに、下の２つは、"ABC202E - Count Descendants"で話題になってたので、急遽追加しましたw
#6. おわりに
子育ても大変な中で応援してくれる妻や、唯一のリア友にしてライバルがいて、ここまでモチベーション高くやってこれました。本当に感謝です。
twitterでも少しずつ競プロ仲間や先輩方との絡みも出てきて、入青tweetにも多くのLikeをいただき、ますます楽しくなってきました。
冷えてめちゃ萎えることもありますが、皆さんおっしゃるとおり、モチベーション高くコンテストに出続けることが一番だと思います。
ここまで紹介してきたことは、あくまで僕のやり方ですが、この記事が少しでも皆さまのお役に立てば幸いです。
最後まで読んでいただき、ありがとうございました！
(5/26 追伸)
AtCoder Clansに掲載していただきました！（hiro_hiroさん、ありがとうございます！）
こちらも『競プロで勝つ』ために、有用なツールやスクリプト、ライブラリなど盛り沢山です。
最近できたRecommendationページも良いですね。是非、ご覧くださいー♪