Loading...
AGC 手筋まとめ(
AGCの多くの問題のネタバレを含みます)
コメント
純頭 : 純粋な地頭、解きたければ転生を検討
頭速度 : 頭の処理速度ゲー、ゆっくりでいいなら解けるもの、高速に解きたければ転生を検討
eps(~900) : 頭が必要ない
1000 ~ 1900: 頭が必要、900の内訳は 頭 + 道筋の長さ + 頭系実装量 で
2000 ~ : 非常識なステップがある
Codeforces系実装量は考慮しません
基本的に自分が解けたら点数が低くて解けなかったら点数が高いです(そ(そ))
高度典型たち
Codeforces系
[
O
(
N
2
)
O(N^2)
O
(
N
2
)
の辺を貼りたい時
O
(
N
p
o
l
y
l
o
g
(
N
)
)
O(N \textrm{polylog}(N))
O
(
N
polylog
(
N
)
)
辺でなんとかする]
よくわからないならARC 069 F - Flagsを見てください
[インライン
DP]
実家、説明は略
[永続UnionFind]
本当に永続しなくてもなんか辺に重み的なアレを持たせるだけみたいなやつ、詳しくはググって
[数列を差分でみる]
数列の変化点が少ない
区間に一様な操作をする
とかの時に有効
単調増加な数列をset<pair(増加点, 増加量)>でみるとかもこれの一種
[pair<int, int>を2次元にプロット]
とりあえずやってみると良い、OI系で頻出、かなり強力なツールだけど必要以上の量の考察になってしまうことがままあるのが弱点
数え上げ系
[
C
(
n
,
k
)
C(n, k)
C
(
n
,
k
)
を経路数として見る,
C
(
n
+
i
,
i
)
C(n+i, i)
C
(
n
+
i
,
i
)
(or
C
(
n
+
i
,
n
)
C(n+i, n)
C
(
n
+
i
,
n
)
)を纏める]
C
(
n
,
k
)
C(n, k)
C
(
n
,
k
)
が出てきたらとにかく経路数としてみるというテク、困ったらやるとよい
C
(
n
+
i
,
i
)
C(n+i, i)
C
(
n
+
i
,
i
)
は経路数としてみるとグリッド状の一直線になり、これの総和はまとめられる、というのが頻出
同様に長方形もまとめられる
また、斜め線に注目するテクもある(斜め線を1動かすと総和は大体2倍になるので、端っこだけ足し引きして辻褄を合わせるテク)
[
C
(
n
,
k
)
C(n, k)
C
(
n
,
k
)
を母関数としてみる]
C
(
n
,
k
)
C(n, k)
C
(
n
,
k
)
が出てきたらとにかく母関数としてみるというテク、ごく稀にハマるがほとんど見たことがない(もしくは気づいていない)
基本的にLucasの定理系と相性がいい？
[Xを数える→Xの判定関数を考える]
あなたはある(簡単な)条件にそってYを列挙します、これにある操作をしてXにします、Xとしてあり得るものは何通り？という問題が出てきたら、Yを列挙して、それに従ってXを作っていくという数え上げ方をやりたくなりがち、で、これをやったら重複が処理できなくて死ぬ時のテク
Please turn on JavaScript to use Paper in all of its awesomeness. ^_^
高度典型たち
Codeforces系
数え上げ系