9/3 PKU - Algorithmer’s note

3181 Dollar Dayz

1ドルからKドルまでの品物がある。あなたはNドル持っている。Nドル丁度使って品物を買う方法（同じ品物をいくら買ってもよい）は何通りあるか？という問題。

多倍長+DP。

2838 Graph Connectivity

無向グラフに対して、「辺の連結」「辺の削除」「2点が辺で結ばれてるか？」というクエリが与えられるから答えよ、という問題。

辺をリストで管理しておくと、辺の連結、削除がO(1)でできる。連結判定はDFSでO(E)でできる。Eは高々Qなので、計算量は高々O(Q^2)で解ける。

2625 Coupons

N種類のクーポンうちどれか1つが入ってるシリアルの箱がある。全種類集めるために必要な箱の個数の期待値はいくつ？という問題。

数学ゲー。期待値E = N/N + N/(N-1) + … + N/2 + N/1を計算するだけ。表示が面倒。

2296 Map Labeler

地図にいくつかラベルを張る。ラベルはすべて同じ大きさの長方形。決められた点があって、すべての点に対して、「上または下の辺の中央にその点が位置する」ようなラベルがないといけない。当然ラベルは重なってはいけない。どれくらい大きいラベルを貼れるか？という問題。

ラベルの大きさに対して二分探索＋2-SAT。2-SATはwarshall-floydで書くとTLEする。

2044 Weather Forecast

風の神が4*4のマス目状の地域に雨を降らせる計画を立てようとしている。
雨雲は2*2のマス目を占領する。雨雲があるところには必ず雨が降る。雨雲は最初は中央4マスにいて、次の日以降は日の初めに南北か東西に1,2マスだけ動かせる。
それぞれのマス目では何日かマーケットやお祭りがある日があり、その日はその地域に雨を降らせたくない。
また、雨が降らない日が7日以上連続してはいけない。ちなみに最初の日の前に全地域に雨が降ったとしてよい。
マーケット、お祭りの計画が与えられたとき、適切に雨を降らせられるか？という問題。

どの角のマスも「7日以上連続して雨が降らないことがない」なら、すべてのマスに対して「7日以上連続して雨が降らないことがない」と言える。
これを用いて、「角4マスのそれぞれについて最後に雨が降ってから何日経ったか」と「今の位置」でDP。また、マーケットをやっているところに雨雲がある場合を排除。実装が面倒。

3614 Sunscreen

C頭の牛が日焼けしようとしている。それぞれの牛は最大、最小のSPF数値を持っていて、その範囲に収まらない日焼け止めを使うと焼け過ぎたり逆に全く焼けなかったりしてしまう。
日焼け止めのボトルがL本ある。それぞれはあるSPF数値を持っている。また、何頭の牛に対して使えるかという数値も持っている。
最大何頭の牛が適切に日焼けできるか？という問題。

貪欲法。まず牛と日焼け止めを、牛は最小のSPF、日焼け止めはそのSPFでソートする。SPFが同じときは、日焼け止めが後に来るようにする。
下から順に見ていって、牛が来たら昇順priority_queueに最大のSPFを投げ込む。
日焼け止めが来たら、priority_queueの下から見ていって、日焼け止めのSPF以上ならその牛に対して使う、ということを繰り返す。queueが空になるか、日焼け止めがなくなるかするまでやる。
計算量はO( (C+L)log(C+L) )で、余裕。
ちなみに、一見してものすごく最大マッチングをやりたくなるけど恐らくTLEしそう。