- 2009-03-08 (日) 15:31
- TopCoder
Place: 473
Score: 426.30(Total)=235.16(250)+191.14(500)+Open(1000)
Rating: 1909 → 1915
はまりすぎわろた．どうにか次のラウンドに行けるのでまぁよしとしましょう．
TopCoder Open Round 1, 250, Sequence Sums
Overview
L個以上100個以下の連続した整数の合計がNになる最小個数の連続した整数を返せ．
Comment
簡単．
Solution
個数をL個から100個まで仮定して成立するか確認するだけ．
001: #include <vector>
002: using namespace std;
003:
004: struct SequenceSums {
005: vector<int> sequence(int N, int L) {
006: vector<int> r;
007: for (int i = L; i <= 100; i++) {
008: int d = N - i * (i - 1) / 2;
009: if (0 <= d && d % i == 0) {
010: for (int j = d / i; r.size() < i; j++)
011: r.push_back(j);
012: break;
013: }
014: }
015: return r;
016: }
017: };
002: using namespace std;
003:
004: struct SequenceSums {
005: vector<int> sequence(int N, int L) {
006: vector<int> r;
007: for (int i = L; i <= 100; i++) {
008: int d = N - i * (i - 1) / 2;
009: if (0 <= d && d % i == 0) {
010: for (int j = d / i; r.size() < i; j++)
011: r.push_back(j);
012: break;
013: }
014: }
015: return r;
016: }
017: };
TopCoder Open Round 1, 500, K-th Probable Elements
Overview
L以上U以下の整数を重複も許しM個取る．この時にK番目に小さい数がNである確率を求めよ．
Comment
数値にだまされた．
Solution
N以上の個数とN以下の個数のDP．
001: double A[101][101];
002:
003: struct KthProbableElement {
004: double probability(int M, int L, int U, int N, int K) {
005: U -= L, N -= L; A[0][0] = 1;
006: for (int t = 0; t < M; t++)
007: for (int x = M; 0 <= x; x--)
008: for (int y = M; 0 <= y; y--) {
009: if (0 < x) A[x][y] += A[x - 1][y] * (U - N);
010: if (0 < y) A[x][y] += A[x][y - 1] * N;
011: A[x][y] /= U + 1;
012: }
013: double s = 0;
014: for (int x = 0; x <= M - K; x++)
015: for (int y = 0; y < K; y++) s += A[x][y];
016: return s;
017: }
018: };
002:
003: struct KthProbableElement {
004: double probability(int M, int L, int U, int N, int K) {
005: U -= L, N -= L; A[0][0] = 1;
006: for (int t = 0; t < M; t++)
007: for (int x = M; 0 <= x; x--)
008: for (int y = M; 0 <= y; y--) {
009: if (0 < x) A[x][y] += A[x - 1][y] * (U - N);
010: if (0 < y) A[x][y] += A[x][y - 1] * N;
011: A[x][y] /= U + 1;
012: }
013: double s = 0;
014: for (int x = 0; x <= M - K; x++)
015: for (int y = 0; y < K; y++) s += A[x][y];
016: return s;
017: }
018: };
TopCoder Open Round 1関連リンク
公式サイト
個人ブログ
- TopCoder Open Elimination Round 1 - 歩くような速さで
- 2009 TopCoder Open Algorithm Elimination Round 1 - nodchipの日記 - TopCoder部
- TCO09 Round1 - cafelier@SRM - TopCoder部
- TCO Round 1 - tanakhの日記 - TopCoder部
- TCO09 Algo Round1 - TopCoderの学習のお時間 - TopCoder部
- 2009-03-08 - tsubosakaの日記 - TopCoder部
- 2009-03-08 - なんとなくな日々のコメント
- TCO09 Round1 - てきとーな日記
- ゲームにっき(仮) 2009 TCO Algorithm Round 1
- TopCoder Open 2009 Round1 - chokudai’s Labo blog（仮）
- Newer: Mac mini を買う計画
- Older: Cell Challenge 2009 予選ラウンド
Comments:0
Trackbacks:0
- Trackback URL for this entry
- http://imoz.jp/2009/03/topcoder-open-round-1/trackback/
- Listed below are links to weblogs that reference
- TopCoder Open Round 1 from 超現実いもす(imos)の日記