Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2010-02-18

SingleRoundMatch462@TopCoder 14:15 SingleRoundMatch462@TopCoder - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - SingleRoundMatch462@TopCoder - nodchipのTopCoder日記 SingleRoundMatch462@TopCoder - nodchipのTopCoder日記 のブックマークコメント

Easy 250 AgeEncoding

  • 答えの値で二分探索するだけじゃね
  • ageが1の解きだけちょっと細工して・・・
  • 書けた
  • submit

結果: Failed System Test

1,"11"の際は0.0となるのですが、答えはpositiveでなければならないため-1.0が答えとなるそうです。かなりの人が同じ間違いをしていました。以下は修正後のソースコードです。

class AgeEncoding {
public:
	double getRadix(int age, string candlesLine) {
        if (find(candlesLine.begin(), candlesLine.end(), '1') == candlesLine.end()) {
            return -1;
        }

        if (find(candlesLine.begin(), candlesLine.end(), '1') == candlesLine.end() - 1) {
            if (age == 1) {
                return -2;
            } else {
                return -1;
            }
        }

        double l = 0.0;
        double r = 1e10;
        for (int loop = 0; loop < 200; ++loop) {
            double m = (l + r) * 0.5;
            double mul = 1;
            double value = 0.0;
            for (int i = candlesLine.size() - 1; i >= 0; --i) {
                value += (candlesLine[i] - '0') * mul;
                mul *= m;
            }

            if (value < age) {
                l = m;
            } else {
                r = m;
            }
        }

		double result = (l + r) * 0.5;

		if (result < EPS) {
			result = -1;
		}

		return result;
	}
}

Middle 450 CandyBox

  • うわ・・・出ました確率と期待値の問題orz
  • とりあえず考えてみる
  • 期待値=確率×平均値 とかだから、とりあえず確率を考えてみる
  • ある箱について入れ替えに関する確率
    • その箱から二つ取り出して入れ替える確率P_{a}=\frac{C(C-1)}{CN(CN-1)}
    • その箱と他の箱から取り出して入れ替える確率P_{b}=\frac{2C^{2}(N-1)}{CN(CN-1)}
    • それ以外の箱から取り出して入れ替える確率P_{b}=\frac{C(N-1){C(N-1)-1}}{CN(CN-1)}
  • ある入れ替えに関する平均値
    • P_{a}P_{c}の場合は平均値は変わらない
    • P_{b}の場合は一個分平均値が減って他から入ってきた分が増えるからscore_{n}\frac{C-1}{C}+(\sum_{i=0}^{N-1}score_{i}-score_{n})\frac{1}{C}\frac{1}{N-1}
  • 書いてみた
  • |score|=1の時にNaNが出る・・・これは撃墜フェイズにとっておこう
  • 修正した
  • submit

結果 : Passed System Test

class CandyBox {
public:
	vector <double> expectedScore(int C, vector <int> score, int S) {
        const int N = score.size();
        vector<double> current(score.begin(), score.end());
        if (N == 1) {
            return current;
        }

        const double NCNC1 = (double)N * C * (N * C - 1);
        const double Pa = C * (C - 1) / NCNC1;
        const double Pb = 2 * C * C * (N - 1) / NCNC1;
        const double Pc = (N - 1) * C * ((N - 1) * C - 1) / NCNC1;

        for (int s = 0; s < S; ++s) {
            vector<double> next;
            double sum = 0;
            for (int i = 0; i < N; ++i) {
                sum += current[i];
            }

            for (int i = 0; i < N; ++i) {
                const double p = (Pa + Pc) * current[i] + Pb * (current[i] * (C - 1) / C + (sum - current[i]) / C / (N - 1));
                next.push_back(p);
            }

            swap(current, next);
        }

		return current;
	}
};

Hard 1000 WarTransportation

  • 各エッジについてそこのエッジの手前まで行ってそこから迂回するルートとかやればいいんじゃね?
  • 書いてみた
  • サンプル合わない・・・
  • たぶん根本的に考え方が間違ってる
  • 時間切れ

Challenge Phase

  • 今回は撃墜祭りになるに違いない
  • 450は"/(N-1)"やっている人に{100,{100},10000}を投げることにしよう
  • 250は{1,"0"}をかたっぱしから投げてみよう
  • 撃墜祭りではなくて撃墜失敗祭りでした

System Test

x o x -125 152.06 1958->1945 450が合ってなかったら最下位でした・・・

感想

どこでfoldするかを見極めなさいってことですね・・・orz

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