競プロを頑張るブログ

問題を解いてる時の思考なりをまとめていきます

yukicoder995を解いた

c++ yukicoder 競プロ 競技プログラミング 解法

はじめに (ネタバレ無し)

こんにちは
ひぽたふです。

解きながらの考察、実際の解法をまとめておこうかなと思います。

今回解いた問題はこれです。

No.995 タピオカオイシクナーレ - yukicoder

星2.5の問題です。
タピオカの絵が書きたくなったので解き始めました。

ヘビーでしたがおすすめ問題です。

以下はネタバレがあるので見る際は注意してください。

解きながらの考察 (ネタバレ　方針まで)

ここからはネタバレがあります。 問題を解いている際に考えていたことをまとめておこうかなと思います。











問題概要

タピオカがN粒ある。
i番目のタピオカの美味しさはB_{i}である。

最初、カップにはM粒のタピオカが入っている。

次の操作を考える。
粒毎に独立して\frac{p}{q}の確率でカップの中のタピオカは外に、外のタピオカは中に移動する。

K回操作を行った時に、カップの中にあるタピオカの美味しさの総和の期待値を求めよ。

答えが\frac{x}{y}で表せるので、x \equiv yR (mod 10^{9} + 7)になるようなRを出力する。

考察

それぞれのタピオカは独立に考えられるから、1粒の場合を考えていくよ。

K = 1の場合はカップの中にいる期待値は1 - \frac{p}{q}だね。
この値にBを乗算すれば美味しさの期待値になるね。

K = 2の場合の期待値は、0回移動と2回移動の期待値を足して(1 - \frac{p}{q})^{2} + (\frac{p}{q})^{2}だね。
(この辺りの数式は最終的に使わないから読み飛ばしても大丈夫！)

K = 3の場合は外に出て戻ってくる方法が2通り考えられるからちょっと厄介かな？
0回移動が(1 - \frac{p}{q})^{3}、2回移動が(1 - \frac{p}{q}) \cdot (\frac{p}{q})^{2} \cdot 2だね。

Kを固定せずに考えた時、x回移動する期待値は・・・

(1 - \frac{p}{q})^{K - x} \cdot (\frac{p}{q})^{x} \cdot {}_K C_x かな？
移動しない回数、移動する回数、移動方法って感じだね。

カップの中に居続けるためにはxは、偶数回の移動をKまで考えればいいよね。
最初にカップの外に居た場合は最後に余事象を考えれば良さげかな。

愚直に実装して試してみたら、小さいケースはしっかり合ってるみたい。
ただ、xを全部試すとO(K)かかるから高速化しないとだね。


Kが10^{12}あるから、数学してO(1)か半分ずつ計算してO(log(n))というところかな？

数学するのは大変そうだから、半分ずつ計算できないか試みてみるよ。

K = 10として考えた時に、k = 5の期待値を使って計算できるだろうか？
知りたいのはカップの中にいる期待値だよね。

最初にカップの中にいると考えたときに最後もカップの中にいるには、半分に分割したうちの前半と後半でそれぞれ、

  • 偶数回 → 偶数回 で移動
  • 奇数回 → 奇数回 で移動

する必要があるね。
最初にカップの外にいる場合は、余事象を考えれば大丈夫そうかな。

偶数 → 偶数の期待値はk = 5でカップの中に戻ってくる期待値(E)を使って、E^{2}で求められるね。

奇数 → 奇数は(1 - E)^{2}かな。

k = 5のEはk = 4とk = 1に分割して再度同じように考えてあげれば良さそうだね。
これは繰り返し二乗法の考え方だね。

終端はk = 1の時。
偶数回移動の期待値は1 - \frac{p}{q}だね。

これで欲しい期待値は求められそうだね！
小さいケースで愚直実装と照らし合わせても同じ答えになった！

最後に出力の形についても考える必要がありそうだね。

x \equiv yR (mod 10^{9} + 7))になるRを考えるんだったね。

両辺をyで割ることができればRが分かりそうだね。

素直に割ることはできないから、よく出てくるフェルマーの小定理を使ってyの逆元を考えておこう。

最終的に欲しいのは\frac{x}{y} % 10^{9} + 7みたいだから、期待値を求める時から余りを計算していって大丈夫そうだね。

余剰計算を入れ忘れたり、余事象にし忘れたりしつつも・・・この方針でAC！

あとがき + 解法(ネタバレ全開)











なかなかヘビーな問題でした。

最終的な方針をまとめると、
繰り返し二乗法の要領で操作回数Kを半分にした場合で期待値を考えるという方向で解きました。
ここでいう期待値は具体的に何を指しているかというと、タピオカが偶数回移動する確率になります。（偶数回移動する確率 = タピオカが元いた場所にいる期待値　という感じですね）

あるタピオカが最初にカップの中にいた場合、偶数回移動する確率 * 美味しさで、美味しさの期待値が求められます。
逆に、カップの外にいた場合は余事象を考えて(1 - 偶数回移動する確率) * 美味しさで、美味しさの期待値が求められます。

繰り返し二乗法と同じようにKが偶数の時と奇数の時で計算を変えます。

  • Kが偶数の時 : (\frac{K}{2}の期待値)2
  • Kが奇数の時 : K - 1の期待値 * K = 1の期待値

で元いた場所にいる期待値ですね。

具体的にどういう移動パターンが存在してその期待値になっているかを考えると、全通りの移動パターンが考慮されていることが分かると思います。

[K = 4]で考えた時の具体例を示しておきます。

f:id:hipotaf:20200611193047p:plain

タピオカが元いた場所にいる期待値が分かれば、後は美味しさを乗算して美味しさの期待値を求めるだけです。
ここで注意するのが、少し上で書いたように最初にカップ内にいるかどうかで余事象を使う点ですね。

次に出力形式について考えます。
x \equiv yR (mod 10^{9} + 7))になるRを出力せよとのことでした。

yの逆元、y^{10^{9} + 7 - 2}を両辺に乗算します。
すると、 xy^{10^{9} + 7 - 2} \equiv R(mod 10^{9} + 7))になります。
つまり、Rはxy^{10^{9} + 7 - 2}の結果になります。

xy^{10^{9} + 7 - 2}は、\frac{x}{y} mod 10^{9} + 7を考えていることになるので、期待値を求める計算過程で随時余剰を計算しておくと答えになっているはずです。

ソースコード

ll MOD = 1000000007;
ll powmod(ll v, ll x) {
  if (x == 0) return 1;
  if (x % 2 == 0) {
    ll tmp = powmod(v, x / 2);
    return (tmp * tmp) % MOD;
  } else {
    return (powmod(v, x - 1) * v) % MOD;
  }
}

// 余事象
ll complementary(ll x) {
  return (1 - x + MOD) % MOD; // 負で乗算しないように気をつける
}

ll P, Q;

// 偶数回移動の期待値を求める
ll e_value(ll k) {
  if (k == 1) {
    // return 1 - P / Q; // ← この余剰が知りたい
    return complementary((P * powmod(Q, MOD - 2)) % MOD);
  }

  if (k % 2 == 0) {
    ll even = e_value(k / 2);
    ll odd = complementary(even);

    return ((even * even) % MOD + (odd * odd) % MOD) % MOD;
  } else {
    ll even_one = e_value(1);
    ll even_other = e_value(k - 1);

    ll odd_one = complementary(even_one);
    ll odd_other = complementary(even_other);

    return ((even_one * even_other) % MOD + (odd_one * odd_other) % MOD) % MOD;
  }
}

int main() {
  ll input(n, m, k, p, q);
  P = p;
  Q = q;
  vector<ll> b(n);
  REP(i, n) cin >> b[i];
}

マクロに関しては別の記事でまとめてあります。

テンプレート - 競プロを頑張るブログ

REPと入出力のみ使用しています。
REPは半開区間となっています。

https://yukicoder.me/submissions/495117

加算タイミングなどでところどころ余剰を計算し忘れて答えが合わない時がありました。
余りを求める系は、出力値を見てもよくわからないのでデバッグが大変ですね・・・。

出てくる演算全部に余剰計算を入れる勢いで行きましょう！

愚直実装のソースコードも貼っておきます。

double combination(ll left, ll right) {
  ll nume = 1;
  FORD(i, left, left - right + 1) {
    nume *= i;
  }
  ll deno = 1;
  FOR(i, 2, right) {
    deno *= i;
  }

  return nume / deno;
}

// k回操作時にx回移動する期待値
double calc(double k, double x, double p, double q) {
  return pow(1 - p / q, k - x) * pow(p / q, x) * combination(k, x);
}

double f(double k, double p, double q) {
  double e = 0;
  REP(i, k / 2 + 1) {
    e += calc(k, i * 2, p, q);
  }
  return e;
}

// f(K, P, Q)などすると偶数回移動する期待値が返ってきます

それでは、またっ！

今回の便利

pythonの話になります。

今回のように分数を扱う時、小数でデバッグするのは大変ですよね。
そんな時、自分はpythonのfractions.Fractionを使いつつデバッグしています。

分数のまま計算してくれる便利な子です。

c++にもそういったクラス、あるのでしょうか・・・。
いまいち知識不足なので知っていきたいところですね！