Regionals 2011 :: Europe - Southwestern
5819 - Alphabet Soup
5820 - Coin Collecting
5821 - Cybercrime Donut Investigation
5822 - Distributing Ballot Boxes
問題
町がN個あり、各町は人口がa[i]人である。
B個の投票箱があり、それを各町に割り当てる。
各町における１つの投票箱に割り当てられる人数の最大値を最小化せよ。
制約
1<=N<=500000
N<=B<=2000000
解法
二分探索。
人数の最大値が分かってるとき、各町に何個投票箱を置けばいいか分かり、その和がBを超えていないかで二分探索できる。
5823 - Game, Set and Match
問題
テニスの試合で1点決める確率が与えれるので、Game、Set、Matchを取る確率を求めよ。
Gameは、得点が4回先に点を決めると勝つ。ただしデュースがある。
Setは、6回先にGameを決めると勝つ。ただしデュースがある。さらに6-6になるとタイブレークが起きる。
タイブレークは、7回先に点を決めると勝つ。ただしデュースがある。
Matchは、2回先にSetを決めると勝つ。デュースなし。
制約
0<=p<=1
解法
DP。
デュースについては、2点差になってる時に答えに足していく。ある程度DPを進めると確率が十分小さくなるので途中で終わればいい。
Setで7-5で勝利もあることに注意。
5824 - Guess the Numbers
問題
n個の文字を含む式（数字は含まない）、n個の文字に割り当てるべき値v[i]、目標の値mが与えられる。
このとき、式の値がmになるような文字へのv[i]の割り当て方はあるかを求めよ。
制約
1<=n<=5
0<=v[i]<=50
0<=m<=1000
文字は小文字1文字
解法
構文解析+前探索(5!)
5825 - Non-negative Partial Sums
問題
n個の要素を持つ数列a[i]が与えられる。
全てのcyclic shiftの中で、全てのiについて0~i番目までの和が正であるようなものの数を求めよ。
制約
1<=n<=10^6
- 1000<=a[i]<=1000
解法
以下の4つの配列を作る。
A[i] = 0~iまでの和
B[i] = i~n-1までの和
C[i] = A[0]~A[i]までの最小
D[i] = min(i~kまでの和) (k
かつ
B[i]>=C[i] (後半部で0未満にならない条件)
を満たすかどうかで調べることが出来る。
D[i]は最大部分列和を求めるのと同じような考え方で求めることが出来る。
5826 - Peer Review
問題
N人の著者が1つずつ論文を発表し、K個の論文をレビューする。
N人の著者について、
属する学会の名前、レビューする予定の論文の番号（入力順の番号）
が与えられる。
このとき、各論文がちょうどK人にレビューされ、K人とも著者と違う学会に属していれば良い。
この条件を満たさないものが何個あるかを調べよ。
制約
2<=K<=5
1<=N<=1000
解法
読解ゲー。
各論文に対してレビューする人のsetを作り、条件が満たされているか調べる。
出力形式に注意。
5827 - Regular Convex Polygon
問題
3点が与えられるので、その３点を頂点の一部とする正多角形のうち頂点数が最小のものを求めよ。
制約
- 10^4<=x[i],y[i]<=10^4
各座標は正確な座標より多くとも10^-6しか離れていない。
多角形の頂点数は1000以下
解法
正多角形の頂点となっているということは、同一円周上にある。
円周角の定理より、中心角は各内角の角度の2倍。
正n角形なら中心角は360/n度の倍数になっているはずである。
nを3~1000まで順に試して、始めに３つの中心角がともに360/nの倍数になっているものが答え。
倍数の判定は、割って整数に十分近いかで調べた。
このとき、EPSを1e-8ではWAで、1e-6なら通った。
5828 - Remoteland
問題
n以下の異なる整数の積のうち、整数の2乗になってる最大の数をmod10^9+7で求めよ。
制約
1<=n<=10000000
解法
各素数ごとに、n!に含まれる数を計算し、偶数個出来るだけ使う。
これでいい理由がまだ分かっていない。
