Hatena::Grouptopcoder

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

 | 

2009-03-08

2009 TopCoder Open Algorithm Elimination Round 1 12:35 2009 TopCoder Open Algorithm Elimination Round 1 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - 2009 TopCoder Open Algorithm Elimination Round 1 - nodchipのTopCoder日記 2009 TopCoder Open Algorithm Elimination Round 1 - nodchipのTopCoder日記 のブックマークコメント

2009 TopCoder Open Algorithm Elimination Round 1の参加記録です。

Easy 250 SequenceSums

L個以上の連続した非負の整数の並びのうち、和がNとなるものを求めよ。そのような並びが無いか整数の並びの個数が100を超える場合は空の配列を返せ。

Nをl個の数に分解できる場合、ある数kを使って

N=kl+l(l-1)/2

と表現できるため、lをL~100(inclusive)まで回して確かめる。

class SequenceSums {
public:
  vector <int> sequence(int N, int L) {
    vector <int> result;
    for (ll l = L; l <= 100; ++l){
      ll lll = l * (l - 1) / 2;
      ll n = N - lll;
      if (n < 0){
        continue;
      }
      if (n % l == 0){
        result.push_back(n / l);
        for (ll i = 0; i < l - 1; ++i){
          result.push_back(result.back() + 1);
        }
        break;
      }
    }

    return result;
  }
};

Midium 500 KthProbableElement

[lowerBoud,upperBound]よりM個の数字をランダムに選ぶ。このときK番目に小さい数字がNである確率を求めよ。

確率?DP?なにそれ?おいしいの?

orz

Hard 1000 Unicorn

チェスでユニコーンという駒を考える。ユニコーンは3マス以上上下左右に動かした後、動かした方向と直角に2マス以上動かすことができる。盤面上にアルファベットが書かれている。入力で与えられる文字列の順に動かす手順が何通りあるか求めよ。

無理でした。DPなのは分かります。O(90000^2*50)ではTLEなのも分かります。値の更新する際に"全体の数-行けない所の数"とすると大幅に計算量を落とすことができるということまではわかったのですが、肝心の更新の式が分かりませんでした。

撃墜フェーズ

以下に当たりを付けてソースを眺めていったのですが、点数が通過ラインギリギリだった為、何もできませんでした。

  • Easy 境界条件(Lが100付近)
  • Easy intオーバーフロー
  • Hard 1文字だけ
  • Hard TLE狙い

結果

o x x 243.0

通過はしているようです。よく見るとちょっと上にcafelierさんが・・・。

総評

500のDPは気づきたかった。確率とDPの組み合わせでにっちもさっちもいかなくなるのをどうにかしたいです。

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