SRM 667 div1 CatsOnTheCircle - mayoko’s diary

「言われてみるとアタリマエ」みたいな問題解けないの非常に辛い。

問題

解法

三項間漸化式を解く感じになります。

まず, どのようなときに K が勝つのかを考えます。これは, 「K 以外のすべての人にボールが回った時」です。そして, このような状況になるには, 「0 から時計回りに K-1 までボールが回って, かつ 0 から半時計回りに K+1 までボールが回った時」です。

つまり, K が勝つには,
・K-1 に K+1 よりも先にボールが来て, その後 K を介さずに K+1 までボールが行く : 1
・K+1 に K-1 よりも先にボールが来て, その後 K を介さずに K-1 までボールが行く : 2
の 2 通りしかありません。

上記 2 つの確率を求めるために, 次の関数を考えます。

f(L, R) = (L 回分半時計回りするより前に, R 回分時計回りする確率)
これを求められると, 1 の確率は f(N-K-1, K-1) * (1-f(N-2, 1)), 2 の確率は (1-f(N-K-1)) * f(1, N-2) となり, 嬉しいです。ということで, この f(L, R) が求められれば良いです。

さて, f について,
f(0, *) = 0 (残り 0 回の半時計回りがすでに達成されているので, * 回時計回りすることは出来ない)
f(*, 0) = 1 (残り 0 回の時計回りがすでに達成されているので)
が成り立ちます。また, f の漸化式について,

f(L, R) = p*f(L+1, R-1) + (1-p)*f(L-1, R+1)

が成り立ちます(時計回りに 1 個分回れば, 時計回りに回るべき回数は 1 回減り, 半時計回りに回るべき回数は 1 回増える etc)。

この f 関数は, 引数 2 つの和が一定であるという規則(?)があります。ということで, f は 1 つの引数にすることが出来ます。

g(x) = g(L+R-x, x) とすると, 上記の初期条件および漸化式は,
g(L+R) = 0, g(0) = 1, g(x) = p*g(x-1) + (1-p)*g(x+1)
となります。

この漸化式の特性方程式を解くと,
k = p/(1-p), 1
です。よって,
g(x) = a*k^x + b
という形に出来ます(k = p/(1-p) とした)。

初期条件を元に a, b を求めると, a = 1/(1-k^(L+R)), b = 1-a となるので, あとはこれを使ってがんばります。

なお, p = 0.5 のときは k = 1 となりめんどくさいです。よく考えると, この場合は g(x) がすべて等しくなるということなので, 1/(N-1) が答えです。また, p > 0.5 の時は, k が 1 より大きくなり, オーバーフローの危険性があります。これを回避するために, p > 0.5 だったら K を N-K にして p を 1-p にするという工夫をしましょう。

得た知見

行列累乗考えるのもいいけど漸化式を解く発想も持とう
正直行列累乗考えていた時すべての場合をきちんと定式化していたわけではなかったので, もうちょっと定式化できるところはしてから深く考えるようにしよう(きちんと定式化できればきちんとした解法を思いつくきっかけにもなりそう)

const int HALF = 1e9/2;
double p;

double f(int L, int R) {
    double pp = p/(1-p);
    double a = 1/(1-pow(pp, L+R));
    double b = 1-a;
    return a*pow(pp, R) + b;
}

class CatsOnTheCircle {
public:
    double getProb(int N, int K, int ppp) {
        if (ppp == HALF) return 1./(N-1);
        if (ppp > HALF) {
            K = N-K;
            ppp = 1e9-ppp;
        }
        p = ppp/1e9;
        return f(N-K-1, K-1) * (1-f(N-2, 1)) + (1-f(N-K-1, K-1)) * f(1, N-2);
    }
};