Hatena::Grouptopcoder

yehara のTopCoder日記

 | 

2009-06-24

SRM443 Div1

12:11 |  SRM443 Div1 - yehara のTopCoder日記 を含むブックマーク はてなブックマーク -  SRM443 Div1 - yehara のTopCoder日記

Level 1 (300)

地域の境界がすべて円の国で、ある地点からある地点まで移動するのに、最低いくつの境界を通過しなければいけないかを求める問題。境界線は交差することはない。

それぞれの境界について、始点と終点が境界の別サイドにあるかどうかを判定して、別サイドであればカウント+1。それぞれ独立に計算できる。

300 点ということでちょっとビビったが、簡単だった(272.36)。

public class CirclesCountry {
    public int leastBorders(int[] X, int[] Y, int[] R, int x1, int y1, int x2, int y2) {
        int n = X.length;
        int res = 0;
        for(int i=0; i<n; i++){
            boolean b1 = include(X[i],Y[i],R[i],x1,y1);
            boolean b2 = include(X[i],Y[i],R[i],x2,y2);
            if(b1!=b2) res++;
        }
        return res;
    }

    boolean include(int x, int y, int r, int xx, int yy){
       return Math.hypot((long)x-xx, (long)y-yy) < (long) r;
    }
}

long へのキャストは全く意味がないのだが、ご愛嬌。安全めに double へキャストしておこうと思って書き間違い。動作に影響ないので放置した。

Level 2 (600)

コインで考えると、厳密に K 枚のコインを裏返すという操作を 1 ステップとする。初期状態が与えられたとき、すべてのコインを表の状態にするのに最低何ステップ必要かを求める問題。

ダイクストラでいけるかなと思って実装し、テストケースは通ったので submit するも、大きいケースで TLE となることが判明。いろいろと刈り込みを試みるも結局間に合わず。

どうするのが良いのだろうか?

Level 3 (1000)

開くこともできず。

まとめ

今回こそ Level2 クリアと思ったんだが・・・。600 点はダテではなかった。堅調に黄色をキープ(1542->1619)。

ゲスト



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