プログラミングコンテストチャレンジブック 3-3
第3章 3-3 頻出テクニックの続きです。
- 弾性衝突
- 同じ質量の球が弾性衝突した時はそのままお互いがすりぬけたように扱えばよい
- 半分全列挙
- 全体の場合の数を計算するのは無理なので半分の組み合わせで計算して残りは制約条件を元に計算
- 巨大ナップサック
- 品物の種類(n)が小さくて容量がとても大きなナップサック問題
- 品物を半分にわけてそれぞれの全通りを列挙する
- 座標圧縮
- 領域の個数の数え上げ
- あらかじめ領域に影響がないように座標を圧縮しておいて計算量を落とす
