394.1

まだまだ解ける問題の出てる時代。

250

文字列が与えられる。K文字までならば削除して良いので、登場回数が一番多い文字と一番少ない文字の登場回数の差分の最小値を求めよ、という問題。

一番多い登場回数と一番少ない登場回数を決めて、その範囲にないものを削除することを考える。そのときに必要な削除回数がK以下であれば、そのような登場回数にすることが可能なので、後は全パターン試すだけ。

600

直線がいくつか与えられる。ある点を中心として点対称に移動させたときに、元の直線群と同一になるような点がいくつあるか答えよ、という問題。

自分自身と重なるためには自分自身の上の任意の点で良い。交差する直線と重なることはできない。平行な直線と重なるためには、相手との距離がちょうど半分になるような直線上の任意の点で良い。

以上を踏まえてめんどくさい幾何をやるだけのように見える。

900

木が与えられる。それぞれの枝にK以下の非負整数の距離をランダムに割り当てるとき、任意の二点間の距離がM以下になる確率を求めよ、という問題。

やるだけ。適当な点を始点としてそれぞれの子に対して、一番遠い点の距離とその確率を問い合わせる。全部の子について問い合わせが終わったら、それらをマージしてやる。このプロセスは再帰的にやる。当然二つの子について、一番遠い点の距離の合計値がMより大きくなってはいけない。そうでなければ、より遠い方を覚えておいて、親に返してやる。実際に親に返すときには、親と自分との間にK以下のコストが発生するので、それを加算してやる。