250.1

全然ダメな日。明日は頑張ろう...。

250

文字列中のアルファベットの出現頻度から、一番類似度の高い文字列を選べ、という問題。

いわゆる精度問題。頻度計算を各文字についてやる時に、割り算を最後に回しましょう、ということ。あるいは簡易分数クラスでも用意しましょう、ということ。後者の方が安全。

500

複数のイベントの開始時刻と終了時刻が与えられる。ある任意の時刻から開始して24時間の間に重なりがないものを選択するとき、最大イベント参加時間を答えよ、という問題。

開始時刻でソートして、最初に選択するイベントを決定した上でDPを回すだけ。イベントの競合判定が面倒なだけ。実際には開始時刻順にソートしているのと、最初に選択したイベントと重複しないようになっているという判定を同時に行うことから、イベントの開始時刻が、別のイベントに含まれないことを判定すれば十分。

1000

二つの凸包の共通部分領域の面積を求めよ、という問題。

片方の凸包に各頂点が含まれるかどうかを判定し、含まれる頂点すべてを覚えておく。含まれる頂点と含まれない頂点とを結ぶ線分すべてについて、交差判定を行って、交点を含まれる頂点に追加する。後は、それからできる凸包の面積を計算するだけ。

線分の交差判定が一番面倒な気がする。