値域が狭い(問題の制約で狭めてある)時や、定義域がやたら広い(部分集合の全体2^2000とか)時に、値域と定義域を交換する問題変換が有効なケースがある
- フェニック木
- 値の集合を添え字が値であるような配列に1が立ってるもので表現する
- 動的計画法
- 値域が定義域より狭い時に、定義域の中で最大の値を見つける代わりに、値域の中で制約を満たす最大の添え字を見つける
- 要素2000個の集合の部分集合にたいするgcd、定義域は2^2000だが、値域は2000個の約数の集合でもっと小さい
値域を定義域にする
定義域より値域が狭い関数