問題変換
https://gyazo.com/25b6533da9d20f64c553e9091a64d635
ある抽象的な解法Aである具体的な問題Xが解ける
これはAを知っていると自明にわかる
しかし意外な問題YがAで解けることがある
ある問題変換Bが存在して、それが一部の問題を別の問題に写像する
最大流最小カット定理とか
これによって一見Aに含まれないYがAに含まれるY'に写像される
問題変換には他にどんなものがあるだろうか
ベクトルで表現されてる問題を複素数に変換して解くベクトル複素数変換
値域と定義域の交換
数の集合を0/1の列とみなしてフェニック木を使う
座標圧縮して計算可能な範囲の値にする
巨大な整数を桁の列とみなしてDPする桁DP
Project Selection Problemを最小費用流に帰着
数列の問題を形式的べき級数とみなす
双対線形計画問題