プログラミングコンテストチャレンジブック 4-4 その2

4-4 「厳選! 頻出テクニック(2)」の続きです。

• 個数制約付きナップサック - 品目につき個数の上限がある場合
  • DP の漸化式を j mode w[i] = 0 の場合に注目して式展開してスライド最小値の手法を適用
• K-Anonymous Sequence - 単調非減少数列について、1つの項の数を1減らす操作を何回繰り返して同じ値が k 個存在するようにできるか
  • i番目の項について条件を見たすにはそこから k-1 個の項を操作すればいい。これを基にして漸化式を立てる
  • 式変形すると直線群のうち x=i での交点の最小値を求める問題に帰着
    • 傾きが単調非増加なので後の直線でのみ下側エンベロープが更新されうる

思わぬ形に問題が変化していく問題でした。

• 巡回スケジューリング - 一週間に視聴できるアニメの最大数
  • 区間スケジューリングの両端が繋がってループ状になっている問題
  • 視聴する番組をひとつ決めてしまうとその時間と交差しない時間については区間スケジューリング問題に帰着でき、終了時間についての貪欲法で解ける
  • 最初の番組を決めた後の計算で再利用できるところを事前計算して計算量を抑える
  • さらに 2^k 個先の区間を探索するようにして貪欲法で1つずつすすめるかわりに二分探索する

4-4 も終わり、あとは 4-5 の GCJ の問題だけになりました。そろそろ次の本を決めないといけませんね。