三度目の正直。
250
整数配列が与えられるので、K個の要素を選んで平均値に置き換える、という操作を要素が一つになるまで繰り返すとき、最終的にできる値の最大値を答えよ、という問題。
小さい方から二個ずつやれば良いそうです。
500
色々なさいころが与えられるので、全部投げたときの合計値のうち、発生確率が一番大きい目の最小値を答えよ、という問題。
同じ確率になる範囲を覚えておいて、中央値からどれくらい離れているか、というのを計算すれば良さそうです。
1000
mod2の状況下でN次多項式をM乗することを考える。このときK乗の項の係数を答えよ、という問題。
二乗すると係数1の項の次数が倍になる(他の項との積は二倍されてmod2で0になる)という性質を使うと、元の多項式の係数が1の部分の数と同じだけしか1の部分はない。なので、係数が1になる次数をすべて覚えておいて、Mを二進数表現した値を作って、可能なパターンを全探索する。さすがに重たいので適当に枝を刈りつつメモしておけば通る。(綺麗にDPするのが想定解らしいですが...。)
