Hatena::Grouptopcoder

cou929のTopCoder日記

2010-12-15

SRM 490 div1 Easy (リハビリ)

00:01

Easy - Starport

ひさびさ. リハビリがてら easy を解いてみました.

宇宙港に M 単位時間ごとに宇宙船がつく. 港では N 単位時間ごとにテレポーテーションが行われる. 港についた船は次のテレポーテーションまで待って, 転送される. 到着時間とテレポーテーション時間が同時刻だった場合, その船は即座に転送される. 船がテレポーテーションを待つ時間の期待値を求めよ.

船の待ち時間を順に書きだすと, ループする数列になること. 1ループ分で計算をすれば期待値が求められること. 1ループの長さは高々 N であること (i 番目の船の待ち時間は N - (i*M % N) なので). ループの最後の時刻は N と M の最小公倍数になることには気が付きました. しかしここまでをストレートに実装したとすると, N, M は [1, 1000000000] の範囲の値をとるので, N = 1000000000, M = 1 のようなケースで TLE してしまいます. 数列の和を求める方法がわかればよかったんですが, 思いつかなかったのでとりあえず実装. 面倒なので lcm は適当.

  double getExpectedTime(int N, int M) {
    double ret = 0;
    long long lcm = N * M;
    long long total = 0;
    long long counter = 0;
    int i;

    for (i=1; i*M<=lcm; i++) {
      total += (i*M % N == 0) ? 0 : (N - i*M % N);
      counter++;
    }

    ret = (double)total / (double)counter;

    return ret;
  }

予想通りワーストケースで TLE でした.

ここで諦めて editorial. 自分が気づけなかった事実は, "数列の1ループの要素数は lcm / M" になるということ. また明らかに数列の要素は等間隔にならんでいます. ここで数列の順序を昇順にソートしたものは単なる等差数列になるので, これを要素数で割れば期待値になります. lcm と gcd の関係 (lcm(a, b) = a / gcd(a, b) * b) も用いると, 次のように求められます.

lcm と gcd の関係より数列1ループの要素数を以下のように表す
lcm(N, M) = N / gcd(N, M) * M
lcm(N, M) / M = N / gcd(N, M) * M / M
(要素数) = N / gcd(N, M)

よって数列の要素の間隔は gcd(N, M) ということになる. 

次のような 初項 0, 公差 gcd(N, M), 
(最後の項は "(N/gcd(N, M) - 1) * gcd(N, M)") 
の等差数列の和を求める. 
(簡略化のため gcd(N, M) = x とする)

[0, 1*x, 2*x, ...,  (N/x-1)*x] = (N/x) * (0 + (N/x-1)*x) / 2 = (N/x) * (N - x) / 2)

これを要素数 N/x で割る.

(N/x) * (N - x) / 2) / N/x = (N - x) / 2

よって答えは N - gcd(N, M) / 2 の1行です. gcd は作りおきしてあるユークリッドの互除法の関数を使い回します.

class Starport {
public:
  int gcd(const int _a, const int _b) {
    int a = max(_a, _b);
    int b = min(_a, _b);

    while (b) {
      int tmp = a % b;
      a = b;
      b = tmp;
    }

    return a;
  }

  double getExpectedTime(int N, int M) {
    return (N - gcd(N, M)) / 2.0;
  }
};