srm426

黄色くなって初めてのsrm!

div1:250

読んでも読んでも問題の意味する所が分からなかったが、こんだけ分かりづらかったらみんなもスコア低くなるだろ。。。と思って特に焦らず読む。10分ほど読んでようやく手計算と結果が一致したので注意深く組んで提出。部屋で3番手だったからやっぱりな〜と思ってちょっと安心。
passed system test 186.16

div1:500

ネズミを囲う事の出来る最小の範囲Lを求めれば良くて、Lが最小となるのは（きっと）あるネズミのペアの距離が最も近くなった時で、ネズミ同士の距離は下に凸な二次方程式で表せるので、微分または平方完成して時刻を全列挙して調べれば良い。と思って式を打ち込んだんだけど微妙に合わない。数パーセントの誤差がどうしても出てしまう。今考えるとこれが罠で、どっかでdoubleをintにキャストしてるのかな〜とか式写し間違えたかな〜とか思って調べてる間に時間切れになってしまった。で、今考えるに「きっと」の部分がおかしくて、範囲は円ではなく四角形なので距離が最小の時にLが最小になるとは限らない。うぁぁぁ。。。。そらそーだ！
opened

div1:1000

読まず。いや開かず。

500は三分探索だったかー。距離で考えてたから時間に関するLのグラフが奇麗に下に凸にならず凸凹になる気がして、局所解で止まる可能性を考えて止めてしまった。三分探索にしても初期条件の最大値をどれくらいで押さえれば良いのかとかそれほど自明でないのでちょっと難しい。

結局250をなんとも微妙な点数で通せただけだったので絶対レーティング下がるーと思って凹んでたら微増して嬉しい。1691から1728に37up。次回は実装ゲーな500を…お願いします…さいころダンジョンBFSとか…

（追記）
500はどう考えても三分探索がベストだ。

vector<int> xp, yp, xv, yv;

double getl(double t) {
  double maxx = -1e50, minx = 1e50, maxy = -1e50, miny = 1e50;
  for (int i = 0; i < xp.size(); ++i) {
    double x = xp[i] + xv[i] * t, y = yp[i] + yv[i] * t;
    maxx >?= x, minx <?= x, maxy >?= y, miny <?= y;
  }
  return (maxx - minx) >? (maxy - miny);
}

class CatchTheMice {
public:
double largestCage(vector <int> xp, vector <int> yp, vector <int> xv, vector <int> yv) {
  ::xp = xp, ::yp = yp, ::xv = xv, ::yv = yv;
  double minT = 0, maxT = 10000;
  for (int i = 0; i < 200; ++i) {
    double d = (maxT - minT) / 3, aT = minT + d, bT = maxT - d;
    if (getl(aT) < getl(bT)) maxT = bT;
    else minT = aT;
  }
  return getl(minT);
}