Hatena::Grouptopcoder

yehara のTopCoder日記

 | 

2009-07-23

SRM445 Div1

02:29 |  SRM445 Div1 - yehara のTopCoder日記 を含むブックマーク はてなブックマーク -  SRM445 Div1 - yehara のTopCoder日記

Level 1 (275)

格子点上に配置された点からの距離 top-k を最小化する問題。

解となるポイントは 0.5 幅のグリッド上にあるはずなので、すべての点について計算して最小値を求めるだけ。わりとありがちなパターンかな。

厳密にやろうとすると整数化して計算すべきなんだろうけど、これくらい大丈夫だろうと思って double のまま計算した。よく考えると解の初期値や探索範囲にマージンがまったく無く、場合によっては誤差死していたかもしれない。助かった(236.60)。

public class TheNewHouseDivOne {
    public double distance(int[] x, int[] y, int k) {
        double res = 100d;
        int n = x.length;
        double[] l = new double[n];
        for (double xx = -50d; xx <= 50; xx += 0.5d) {
            for (double yy = -50d; yy <= 50; yy += 0.5d) {
                for (int i = 0; i < n; i++) {
                    l[i] = Math.abs(x[i] - xx) + Math.abs(y[i] - yy);
                }
                Arrays.sort(l);
                res = Math.min(l[k - 1], res);
            }
        }
        return res;
    }
}

Level 2 (550)

1時間以上時間があったのに、方針もたてられなかった。

Level 3 (1000)

開くこともできず。

まとめ

実は前回も参加していたが 0 点で萎えてしまって日記を書いていなかった。なんとか黄色をキープしていたが、次はない状態だった。

今回は1問クリアで、ほぼ前回の失点を取り戻した(1621->1526->1624)。あいからわず Level2 が壁である。

トラックバック - http://topcoder.g.hatena.ne.jp/yehara/20090723
 |