TopCoder SRM 440 Div 1 Medium

Algorithm

本番で解けなかったもの。

以下考え方とソース。


考え方はMatch Editorialsのやつそのまんまだけど。

木の節点上からランダムウォークして根へ辿り着くのにかかる回数の期待値を求めるわけだけど、最初にまずある節点からその親へ行くのにかかる回数の期待値を求めることを考える。

まず、ある節点をrとおいて、rからその親へ行くのにかかる回数の期待値をE(r)と表す。また、子の集合をcで表す。現在rにいるとして、子の数をKとおけば、すぐに親の方へいける確率は 1/(K+1) になる。残りの K/(K+1) の確率で子の方へ行く。

子の方へ行く場合、たとえばi番目の子 c[i] へ行く場合を考えると、c[i]の親はrである。よってE(c[i])はc[i]からrへ行く期待値になる。そうするとc[i]へ行く場合、まずrからc[i]へ行くのに1、c[i]からrへ戻ってくるのにE(c[i])、そしてrからその親へ行くのにE(r)。全ての子に対して同じことが言えて、全ての子はそれぞれ 1/(K+1) の確率で選ばれるから 1/(K+1) * (1+E(c[i])+E(r)) を全てのiに対して計算し総和をとればよい。

すぐに親の方へ行く場合と、子の方へ行く場合のふたつを考えれば E(r) = 1/(K+1) + sum(i=1 to K) (1/(K+1)) * (1+E(c[i])+E(r)) となる。

rが葉の場合 E(r) = 1 は明らかなので深さ優先探索をすることによって計算が可能。

次に、節点rから根まで行くための期待値を計算したい。これはE(r) + E(rの親) + E(rの親の親) ... という風に根まで期待値の和を計算してやればよい。これを効率よく計算するには同じく深さ優先探索を用いる。根から現在の節点rまでの期待値の総和sを保持しながら、根までの期待値の総和を計算できる。

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;
using System.Collections.Generic;

public class MazeWandering {
    string[] mz;
    double[,] ex;
    int N, M;

    static int[] dx = { 1, -1, 0, 0 }, dy = { 0, 0, 1, -1 };

    private void dfs1(int x, int y, int px, int py)
    {
        double sum = 0.0;
        int nx, ny;
        for (int i = 0; i < 4; ++i)
        {
            nx = x + dx[i];
            ny = y + dy[i];
            if (nx == px && ny == py) continue;
            if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
            if (mz[ny][nx] == 'X') continue;
            dfs1(nx, ny, x, y);
            sum += ex[ny, nx] + 1;
        }
        ex[y, x] = sum + 1;
    }

    double exsum;
    int ct;

    private void dfs2(int x, int y, int px, int py, double sum)
    {
        int nx, ny;
        ct++;
        sum += ex[y, x];
        exsum += sum;
        for (int i = 0; i < 4; ++i)
        {
            nx = x + dx[i];
            ny = y + dy[i];
            if (nx == px && ny == py) continue;
            if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
            if (mz[ny][nx] == 'X') continue;
            dfs2(nx, ny, x, y, sum);
         }
    }

    public double expectedTime(string[] maze)
    {
        mz = maze;
        int sx = -1, sy = -1;
        N = maze.Length;
        M = maze[0].Length;
        ex = new double[N, M];
        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < M; ++j)
            {
                if (maze[i][j] == '*')
                {
                    mz[i].Replace('*', '.');
                    sy = i;
                    sx = j;
                }
                ex[i, j] = 0.0;
            }
        }
        exsum = 0.0;
        ct = 0;
        dfs1(sx, sy, -1, -1);
        dfs2(sx, sy, -1, -1, -ex[sy, sx]);
        return exsum / ct;
    }
}