Hatena::Grouptopcoder

Gus@topcoder

topcoderのid:gusmachineの記録です。普段の日記は揺動散逸日記をどうぞ。
 | 

2012-03-06

Codeforces #107 Div. 2

00:12

2/19にやった問題。

はやくDiv. 1に行ってこんなつまらない問題リストからおさらばしたい気分です。

o o o hacked opened: 17th.

A

cout << min(k * l / (nl * n), min(c * d / n, p / (n * np))) << endl;

B

判定が面倒。

C

与えられた数が素因数分解していくつの素数からなるか調べる。

D

m種のアルファベットからなる長さNの文字列のうち、そのどの長さkの部分文字列も回文になっているものの数を答えよ。ただし答えは10^9 + 7で割ってあまりを出す。

ちょっと調べればわかるが、kが偶数なら同じ文字の連続以外ありえず、kが奇数ならababab..baしかありえない。

ただし、k < N とか k == N に注意。k < N はpretestに入っていて、k == N は忘れてhackされる始末。

つーか k < N とか問題の趣旨に照らし合わせてぎりぎりヤバめの入力だと思う。

E

問題を読み解くと、「数列{x_n}と添字列{(a, b)_i}が与えられるので、a_i ≤ c_i ≤ d_i ≤ b_i なる c_i, d_i のなかで ∑_{c_i ≤ k ≤ d_i} x_k を最大化するものを各iで求めよ」となる。数列のサイズと添字の数が両方 10^5 オーダーになるため、安直に行うとTLEる。

数列{x_n}の区間{x_k}(a ≤ k ≤ b)に対し、その区間内の区間での和の最大、左端を含む区間での和の最大、右端を含む区間での和の最大、それから全体の合計、この四つをO(log |x_n|)で求められる区間木がO(|x_n| log |x_n|)で構成できるのでそれで終了。

ただしこの区間木書いたの初めてで適当に書いたらSIGSEGVった。gdb-many-windowsを動員するもよくわからず。

問題が終わった後にデバッグしてみた。

https://twitter.com/#!/gusmachine/status/171593946970071041

ぎゃーなんだこれはー!!! > if (child[i]) {delete child;}

しかしまだ合わない→Get()の部分にバグ(maxをうまくとってない)を発見。

しかしまだ合わない。wrong answer on test 4. データが読めないので良くわからず。


みつけた。

  int Right(int pos) const {
    if (pos == start_) {
      return right_;
    }
    if (pivot_ <= pos) {
      return child[1]->Right(pos);
    }
    int v1 = child[1]->Right(pivot_);
    int v2 = child[1]->Sum() + child[0]->Left(pos); // bug
    return max(v1, v2);

しかしwrong answer on test 6

厳しいなこれ

ああint overflowだ。答えx100が2^32超えてるじゃん。

全部long long に直す。

wrong answer on test 15.

マジでー。

あれ答えx100が2^50近くなんだけど。doubleでエラーしてる?

しかしrelative errorが大きいのはおかしい。

10^9 * 50 > 2^32だった。よって期待値の部分でオーバーフローしていた。ここもllにする。

まだ解けてない。 wrong answer on test 15.

あっ

int Sum() const {return sum_;}

ブッダ!なんでこれエラー出てないんだ。

s/int/LL/

通った。


その他

気がついたら Div 1.に昇進していました。

 |