326.1

普通に解き方が全く分からないセット...。

250

文字列配列が複数与えられる。文字列配列から一つ選び、要素を任意の順番で提示していく、という作業を行うことを考えるとき、元の配列が特定できるか、特定できないことが分かるまでに提示する要素数の最大値を答えよ、という問題。

要は二つの文字列配列の共通部分集合の最大値を答えよ、という問題なので、やるだけ。

550

円弧の上に3点を取り、三角形を作ることを考える。取っていい領域が指定されるので、面積の最大値を答えよ、という問題。

2点選択したら、残りの1点は、その2点間を結ぶ線分の垂直二等分線上になるか、任意の区間の端点になる。2点の選択の仕方は区間の端点からで、収束するまで、残りの1点を選択する方法を、3点のうち2点を選んで繰り返す。

1000

N個の箱にB個のものを1個以上9個以下入れることを考える。K人の人が、それぞれFi番目の箱、Fi+Pi番目の箱Fi+Pi*2番目の箱...と開けていき、開けた箱の平均値から、全部の箱に入っている合計値を推定し、K人の平均値を取る。このとき、箱の数は自由に決めて良いとして、平均値の最大値を答えよ、という問題。

箱の数が決まれば、K人について、(箱の総数/チェックする箱の総数)を計算して、それぞれの箱について重み付けしていく。後は重みの大きい箱から順に詰めていけば良い。箱の数と平均値の関係はチェックする箱の数が変動するところで微分不可能になるので、探索系だとうまくいかない...。

箱の重みを再計算して、ソートし直して、とやると破綻するので、重みの重ね合わせ部分だけを考慮してやる。(2,5,8,...と3,5,7,...という二人なら、5,11,17,...の方が重たいので、というような考え方をする。)というのを実装すれば通りそう。