500.1

500回記念にしてはひどい問題だった。

250

N人から一人を選ぶ投票をする。それぞれの人が投票したい人のリストが与えられる。特に投票したい人がいない場合は、一番票数の少ない人にランダムで順番に(前の人の投票結果は分かる)入れる。この結果で、一番票数の多かった人のグループにのみ投票できるようにして、投票を繰り返す。当選する可能性のある人の数を答えよ、という問題。

最初の投票で2票以上入る人がいないと、全員1票で並ぶため、いつまでやっても終わらない。それ以外のときは、最多得票数の人の人数をKとして、K人でN票を分けることが延々と続く。なので次はN%K人になり、N%(N%K)人になり...、となる。これが最後の一人に収束するならば、最初のK人すべてが当選し得る。KがNを割り切る場合は、そのK人での投票が延々と続くので終わらない。

500

見てない。

1000

各桁の数字の和がSで各桁の数字の積が2^(p2)*3^(p3)*5^(p5)*7^(p7)になるものの合計値を求めよ、という問題。

条件を満たす数字を作る方法を考えるとき、1から9までの数字が何回ずつ登場するか考えれば良い。5と7は既に与えられたp5回とp7回で、8はp2/3回以内、9はp3/2回以内、といった感じに、各桁の登場回数を決める。後はそのような登場回数を満たすもののグループの総和を求める。

各グループについて、たとえば2はすべての桁に等しい回数登場し、グループの数の種類を桁数で割ったものに、2を使う回数をかけたものになる。後は1111....1をかければ、2が合計に寄与する値が分かる。これを1から9まで計算してやるだけ。