NISHIO Hirokazu
[Translate]
余事象を引く
求めたい事象の場合の数が直接求めにくい時に、全事象から余事象を引く
問題変換
関連
→
包除原理
Tweet
Related Pages
包除原理
競技プログラミングで解法を思いつくための典型的な考え方
ABC186F
Xであるものの数え上げ→Xならば?
AGC019B
余事象を考える
abc151_e
abc120_d
HHKB2020
ABC172E
問題変換
→
包除原理
→
包除原理 解ける数え上げの範囲を広げよう
→
数え上げ
×
degwer
×
状態をまとめる
×
dpは全探索の高速化
×
arc059f
×
codefestival_2016_final_f
×
aoj2439
×
探索順の変更
×
大きい順に並べる
×
aoj2333
×
順列は挿入dp
×
bit_dp
×
区間は終点でソート
×
条件の言い換え
×
操作は多いが産物は少ない
×
agc013d
×
線形和への分解
×
演算順序の変更
×
ビット演算を桁ごとに分解
×
部分群
×
操作が可逆で全域→部分群
×
ラグランジュの定理
×
再帰的定義→dp
×
arc037d
×
桁dp
×
aoj0570
×
累積和
×
フェニック木
×
高速フーリエ変換
×
ntt
×
高速ゼータ変換
×
and_と_add_の畳み込み
×
二分累乗
×
agc013e
×
行列木定理
×
全域木の個数
×
lgv公式
×
非交叉経路の個数
×
小さい確率を無視する
×
二項係数の公式
×
経路数
×
45度回転
×
xとyにわける
×
カタラン数
×
包除原理
×
agc005d
×
約数系包除
×
arc064f
→
数え上げテクニック集
→
atcoderエントリーポイント
×
atcoder失敗リスト
×
二分探索チェックリスト
×
列に対して決まる値→列の区間でdp
×
最大化を二分探索で
×
実数に対する大小判定
×
値域と定義域の交換
×
最小カットに帰着
×
競技プログラミングで解法を思いつくための典型的な考え方
×
問題変換
→
AtCoderEntrypoint
→
問題変換
×
フェニック木
×
動的計画法
×
dp_e
×
abc191
×
値域を定義域にする
×
定義域より値域が狭い関数
→
値域と定義域の交換
→
問題変換
→
頂点を辺に変換
二次元配列を座標の列にする
黒マスに隣接している白マスを黒にする
符号を揃える
→
連結成分
×
問題変換
→
連結成分ごとに解けば良い
→
僕のatcoderの学び方(〜水色)
×
僕のatcoderの学び方(〜past上級)
×
abc187
×
past過去問練習202012
×
変形テクニックに名前をつける
×
頂点数18の制約
×
辺が10^5の制約
×
行列の半分
×
二項定理
×
足し算の順序の変更
×
辺が10^5ならダイクストラ使える
×
典型力
×
問題変換
×
問題分割
×
認知の解像度
×
概念のハンドル
×
atcoder失敗リスト
×
AtCoderEntrypoint
×
アルゴリズム実技検定
×
第五回_アルゴリズム実技検定
×
最小費用流に帰着
×
帰着訓練
→
僕のatcoderの学び方(〜青)
→
chokudai
×
動的計画法
×
問題変換
→
同じ状態をまとめるのが動的計画法の本質
→
指数時間アルゴリズム
×
岩田_陽一
×
巡回セールスマン問題
×
最大クリーク問題
×
幅
×
グリッドグラフ
×
pathwidth
×
半分全列挙
×
最大独立集合問題
×
fptアルゴリズム
×
最小頂点被覆問題
×
有界探索木
×
カーネライズ
×
シュタイナー木問題
×
包除原理
×
ハミルトンパス
×
グラフ彩色問題
×
彩色数
×
高速ゼータ変換
×
畳込み
×
完全マッチングの個数
×
完全マッチング
×
color_coding
×
k-cycle
×
bandwidth
×
cut_&_count
×
iterative_compression
→
指数時間アルゴリズム入門
→
オイラー路
×
グリッド上の幅優先探索
×
ハンガリアン法
×
二部グラフの最大マッチング
×
二重辺連結成分分解
×
二重頂点連結成分分解
×
全点対間最短路
×
単一始点最短路
×
強連結成分分解
×
彩色数
×
最大クリーク
×
最大流
×
最大独立集合
×
最小全域有向木
×
最小全域木
×
最小流量制限付き最大流
×
最小費用流
×
橋/関節点
×
bit
×
binary-trie
×
convex-hull-trick-add-monotone
×
li-chao-tree
×
link-cut木_部分木クエリ
×
link-cut木
×
ウェーブレット行列
×
スパーステーブル
×
スライド区間の昇順k個の和
×
セグメント木
×
トライ木
×
マージ可能ヒープ
×
列の平方分割
×
平衡二分探索木
×
永続配列
×
素集合データ構造
×
unionfind
×
ローリングハッシュ
×
接尾辞配列
×
最長共通接頭辞
×
最長回文
×
回文
×
複数文字列検索
×
hl分解
×
全方位木dp
×
最小共通祖先
×
木の直径
×
木の重心分解
×
根付き木に変換
×
mod-pow
×
オイラーのφ関数
×
オイラーのφ関数テーブル
×
ベル数
×
ラグランジュ補間
×
二項係数
×
二項係数テーブル
×
任意mod畳み込み
×
分割数
×
分割数テーブル
×
商列挙
×
形式的冪級数
×
形式的べき級数
×
拡張ユークリッドの互除法
×
拡張ユークリッド互除法
×
第2種スターリング数
×
約数列挙
×
素因数分解
×
素数テーブル
×
素数判定
×
組合せ
×
行列演算
×
進数変換
×
階乗
×
離散対数問題
×
高速フーリエ変換
×
divide-and-conquer-optimization
×
monotone-minima
×
スライド最小値
×
一次元累積和
×
二次元累積和
×
個数制限付きナップサック
×
最大長方形
×
最適二分探索木
×
最長増加部分列
×
ダブリング
×
包除原理
×
燃やす埋める問題
×
燃やす埋める
×
牛ゲー
×
mo’s_algorithm
×
offline-dynamic-connectivity
×
座標圧縮
×
アルゴリズム
→
Luzhiled's memo
→
根つき木に変換
×
最小共通祖先
×
問題変換
→
グラフが木なので根つき木に変換
→
ソート済み配列
×
二分探索
×
リンクトリスト
×
フェニック木
×
削除可能集合
×
不等号条件
×
問題変換
→
削除可能集合で不等号条件
→
arc110
×
操作の結果の数え上げ
×
問題変換
→
操作の結果の数え上げ→構成可能判定
→
帰着する力
×
agc022c
×
ゴールから逆算
×
2回やっても意味がない
×
最適な操作の順番が一位
×
コストが2^k→辞書順最小
×
1〜xで足りて1〜x-1で足りない時xは必須
×
問題変換
×
問題分割
×
状態情報の圧縮
→
典型力
→
codefestival_2016_final_c
×
問題変換
→
辺を頂点にして二部グラフ
→
時間軸反転
×
問題変換
→
塗りの時間軸反転
→
コスト0の遷移を付け加える
×
問題変換
→
ゴールを一つにする
→
余事象
×
包除原理
×
頻度表
×
畳み込み
×
繰り返し畳み込み
→
abl_f
→
小さな定数に注目
×
問題変換
→
境界の位置を全探索
→
最大化を二分探索で
×
最小値の最大化
×
max
×
不等号
×
and
×
問題変換
→
maxの不等号は不等号のand
→
競技プログラミングで解法を思いつくための典型的な考え方
×
余事象を考える
×
包除原理
×
最小共通祖先
→
abc152 f
→
古典的メビウス関数
×
整除関係
×
半順序
×
隣接代数
×
ゼータ関数
×
べき集合
×
包除原理
×
差分作用素
×
sum_over_subsets
×
高速ゼータ変換
→
メビウス関数
→
包除原理
×
メビウスの反転公式
×
隣接代数
→
包除原理とメビウスの反転公式
→
問題変換
×
全探索
→
広い判定で全探索
→
acl1
×
削除可能集合で不等号条件
×
連想接続
×
問題変換
→
帰着する力
→
atcoder_library
×
遅延伝搬セグメント木
×
連結成分
×
unionfind
×
セグメント木
×
動的計画法
×
集めるdp
×
範囲縮約
×
平方分割
×
畳み込み
×
包除原理
→
ACL Beginner Contest
"
Engineer's way of creating knowledge
" the English version of my book is now available on
[Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from
[Scrapbox]
at
11/23/2025, 5:35:09 PM
[Edit]