テンプレ
# A列、B列が与えられるようなとき
AB = [readln() for _ in range(M)]
A = [ab[0] for ab in AB]
B = [ab[1] for ab in AB]
#こういう風にスマートに内包表記を書くよりも
A = []
B = []
for _ in range(M):
a, b = read_ints()
A.append(a)
B.append(b)
#愚直にappendしていったほうがかすかに早い
# 文字の順番を扱うとき
def ord_from_a(char):
return ord(char) - ord('a')
def chr_from_a(n: int):
# nはaから何番あとかを示す
return chr(n + ord('a'))
# グラフ構造が与えられたとき
from collections import defaultdict
node = defaultdict(set) # キーで指定したノードが隣接するノードを記録しておく。
for _ in range(与えられる列数):
u, v, w = read_ints() # assume 2 node idx and edge weight are given
node[v-1].add((u-1, w))
node[u-1].add((v-1, w))
#再帰メモ化
from functools import lru_cache
@lru_cache(maxsize=2**12)
#要素の数え上げ(文字数の数え上げに便利
from collections import Counter
dic = Counter(なんかの配列)
# 最小公倍数を求める
from fractions import gcd
#gcd(0,3)とか3と答える便利な性質がある。3だけの場合の最大公約数(つまり3)を求めることができるということ.
# i番目の要素でソート
# hoge=[(1,4),(2,3),(3,2),(4,1)]みたいなやつを`1`番目の要素でソートしたい
from operator import itemgetter
hoge.sort(key=itemgetter(1))
# [(4, 1), (3, 2), (2, 3), (1, 4)]
# mより小さい最大値 (最小値も似たようにかける)
max(arr, key=lambda x: -INF if x>m else x)
# np.full と同等のpython実装
def full(shape, full_value):
if isinstance(shape, tuple):
sha = shape[::-1]
ret = [full_value] * sha[0]
for s in sha[1:]:
ret = [ret.copy() for i in range(s)] #ここ、pypyだと何故かバグが出る
return ret
else:
return [full_value] * shapeその他コピペで便利そうなアルゴリズムはalgorithm/に保存してある。
-
ビット全探索 ほかにはこれ 1立つidxだけ考慮したりするやつ
- p進数全探索 テンプレート
-
数列系
-
ソート関係
- Counting Sort (出ないかも)
- バブルソートをするとしたら要素の反転数は？ O(n**2)より高速なO(nlogn)
- 最小コストソート...最小コストで要素をswapさせてソートしたい
-
DP関係
-
グラフ関係
-
計算幾何
-
整数論
-
誤差関係
- Decimalを利用した誤差なし四捨五入 ■
-
文字列関連
- 耳DPの習得 (これはよく使いそう？)
- scipy_csgraph.pyの整備 (最短全域木とか)
- 木構造クラスの整備(共通ルート高速取得とかまだ)
- 挿入などが高速に行えるデータ構造の履修(Treapとか)
-
ABC018 C 菱形カウント ... 多点からの最小マンハッタン距離を求めるDP
-
ABC044 C 高橋くんとカード ... 典型的なDPっぽい
-
住友銀行 E colorful hat 2 ... 通りの数を独立に扱いたい。考慮できる情報はわからないか？
-
diverta C AB Substrings ... コーナーケース見落とし
-
AGC036 A Triangle ... 天才パズルすぎる.(外積、剰余計算)
-
ABC150 D Semi Common Multiple ... 必要条件見落とさない！
-
ABC113 D Number of Amidakuji ... 面白いDP。実装が重め。もう一度解きたい(今度はすばやく実装したい)
-
ABC074 D Restoring Road Network ... ちょっと変わったグラフの問題。水diffだけど難しい。
-
ABC 081 D Non-debreasing ... 何食べたらこんなの思いつくんですか
-
ABC 101 C Minimization ... クソ簡単かと思いきやクソムズ
-
ABC 095 D Static Sushi ... 場合分けと独立に式を展開、そして累積maxを用いた高速化
-
ABC 034 D 食塩水 ... 嘘貪欲で通してしまった。次解くときはちゃんと解き方を考えてみよう
-
ABC 110 D Factorization ... 解けるはず！
-
ABC 164 F Multiple of 2019 ... (i,j)の組の数求めろ系のメタ的な戦略も思い出しながら解いてみよう
水色diffは解き直してみてもいいかもしれない。
- AGC 013 A Sorted Arrays ... 茶diffなのにめちゃくちゃ苦手なやつ。スマートに解ける日が来てほしい。
- ABC045_C問題 ... ビット全探索。考え方は難しくないが、ビット全探索という操作の書き方はなれておくと便利そう。また文字列をpythonスクリプトとして実行することもしたので必要になったときは見るべし。
- D問題 ... 木構造の探索の問題。実装では深さ優先探索を採用した。
- C問題 ... 長方形にたいして長方形を使ってなるべく三等分する問題。パターンの見落としがないかが勝負の分かれ目
- D問題 ... 数列から数を抜いて、前半と後半の差を大きくする問題。まず、全探索から一つのループで探索できないかアイデアが出るかの勝負。また、その後の実装も気をつけないと難しい。forの中ではlogNの最小のものが取り出せるheapqを使うっていう選択肢が取れるか。また、コストの管理にsumとか使うとfor合わせてN^2で破綻するので、forの中で定数時間で書き換えられる処理はないか気を配る必要がある。
- D問題 ... まず問題文を読んで場合分け及び解法を思いつくことができるかが分かれ目。その次にいかに計算量を削減できるかも重要。むしろ後者のほうが難しくて無限に時間を溶かした（C++なら平気だった？）
- D問題 ... 初めてのビット演算。各桁が独立に決定できることを見抜けるかが決め手の第一歩。その次にアイデアを実装できるか。条件を満たしながら探索できるか。等学ぶことの多い問題。pythonでビットの処理や桁DPができるように練習を積む必要を感じた。
-
C問題 ... 全探索にすぐ気づいたにもかかわらず、時間切れで解けなかった悔しい問題。どう探索したらバグが少なく済みそうか、楽に実装できそうか考えないで実装し始めて時間内にバグ取りが終わらないなんてほんとアホだよお前は。コンテストへの汎化能力を得るためにC_correct.pyでは深さ優先探索を用いている。深さ優先探索の際には参考になるだろう。
-
D問題 ... 正直C問題より簡単だが、初めて二分探索を使ったのでコンテストで類問が出たときに使えるようにしておこう。 pythonではbisectを使うと良い。また大量に入力があるときはsys.stdin.readlineを用いると若干高速化される。
- D問題 ... DP力不足。小さい状態から大きい状態が決まる系の問題はDPを疑う癖をつけよう。補集合とO(1)解法にこだわっていたのも良くない。D_correctは初期化がテクニカルでDPも多次元だが、よく考えればそんなに難しくはないので復習しよう。
- D問題 ... 全探索の計算量をいかに削減するかが重要な問題。制約条件から気が付きたい。またPriorityQueueを使う爆速なやり方もあり、これを使う場合は確認しておくたい。上位k位が気になるというのはだいたいPriorityQueueを使えば良いことが多い。(本番で一瞬頭にちらついたのに…)
- D問題 ... データ構造を工夫して、累積和かしゃくとり法を使う問題。解法までわかったのに実装のバグが取れずに非常に悔しい思いをした(そして今もバグが取れていない)。解き方の大枠だけでなく、データ構造を工夫する(連長圧縮というらしい)ことで楽に実装できないかまでちゃんと考えよう。(でもいままでD問題は見当すらつかなかったのに最近は解法まで思いついているのは圧倒的成長だよ自分)
- A問題 ... きちんと想定解法を思い浮かんだのにTLEが取れなかった悔しい問題(Pythonが遅いからってのもあるが)。何かが存在する（しない）を確かめるときは、その何かの数を持っておいて更新していく方式の方が圧倒的に早い。