CF356D1D Bear and Chase
errichto感がある
問題概要(原文)
$N$ 頂点 $M$ 本の辺からなる連結グラフが与えられる．
以下のようなゲームをして勝つ確率の最大値を求めよ．
- 敵はある頂点 $x$ をランダムに選んで駒を置く
- 自分はある頂点 $u$ を選ぶ
- 敵は $x$ と $u$ との距離 $d_1$ を教える
- 自分は $x$ がどの頂点か宣言する(しなくてもよいが，した場合はゲームが終了する)
- 敵は $x$ に接続する辺をランダムに選んで，駒を辺をたどって $1$ つ動かす
- 自分はある頂点 $v$ を選ぶ
- 敵は $x$ と $v$ との距離 $d_2$ を教える
- 自分は $x$ がどの頂点か宣言する
自分が宣言した頂点が $x$ であったならば勝ちである．
考察
まず $1$ 回しか頂点を選ばないことにする． すると，頂点 $1,2, \ldots, N$ は距離 $0,1,2, \ldots, N-1$ に振り分けられる．
距離 $d_{1}$ に頂点があるときの正解率 $q_{d_{1}}$ は $\frac{1}{N}$ である(なければ $0$)．$d_{1} = 0,1,2, \ldots N-1$ について求めて和 $\sum_{d_{1} =0}^{N-1} q_{d_{1}}$を取ったとき，最大となるような頂点 $u$ を選ぶのが最適である．
では，$2$ 回目についてのみ考えよう． まず，駒は隣接する頂点に等確率で移動している．すると，以下のような問題になる．
駒 $i$ がある確率分布 $p_i$ が与えられている．$1$ 回だけある頂点 $v$ との距離を教えてもらうことができる．駒の位置を的中させられる確率は？
$v$ 固定して考える．距離 $d_{2}$ が与えられたときに，$d(v,i) = d_{2}$ を満たす頂点 $i$ であって，$p_{i}$ が最大のものを選択する，というのが最適である．これを $r_{d_{2}}$ とする．$\sum_{d_{2} =0}^{N-1}r_{d_{2}}$ が最大となるような $v$ を選ぶのが最適である．これを $r(u,d_{1})$ としたとき結局 $\sum_{d_{1} =0}^{N-1} \max(q_{d_{1}},r(u,d_{1}))$ が最大となる頂点 $u$ を選ぶのが最適であるが適当にやるとこれは $O(N^4)$ かかる．
ここで，以下のようにしていくことで，計算量を $O(N^3)$ に落とすことができる．
- 駒が存在していないことが確定している頂点については確認しない．
- 駒が存在していないことが確定している距離 $d_2$ については確認しない
なぜこれで良いかを示していく． まず，$u,d_1$ を選ぶのに $O(N^2)$ かかる．このとき頂点たちは各距離に分布していて全体で $N$ 個である． 辺を辿っても全体で $O(N(N+M))$ となる． これが，手順 $4$ までの計算量である．
次に $v$ を選ぶのに $O(N)$ かかる． ここで，調べなくてはならない頂点の数は頂点 $v$ から距離 $d_1$ にある頂点に隣接する頂点だけである．これらが移動した先は頂点 $v$ から距離 $d_1 -1, d_1, d_1 + 1$ のどこかにしか移動しない．
これはつまり，$u$ を固定したとき，手順 $5$ 以降のステップで各頂点が調べられる回数は $3$ 回に抑えられる，ということである．
全体として $O(N^3)$ になるが，重い．
ソースコード
using System;
using System.Linq;
using System.Collections.Generic;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
using System.Numerics;
using Point = System.Numerics.Complex;
using Number = System.Int64;
namespace Program
{
public class Solver
{
public void Solve()
{
var n = sc.Integer();
var m = sc.Integer();
var dist = Enumerate(n, x => new int[n]);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
dist[i][j] = dist[j][i] = 10000000;
var G = Enumerate(n, x => new List<int>());
for (int i = 0; i < m; i++)
{
var f = sc.Integer() - 1;
var t = sc.Integer() - 1;
G[f].Add(t);
G[t].Add(f);
dist[f][t] = dist[t][f] = 1;
}
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dist[i][j] = Math.Min(dist[i][j], dist[i][k] + dist[k][j]);
var vs = Enumerate(n, x => Enumerate(n, y => new List<int>()));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
var x = dist[i][j];
vs[i][x].Add(j);
}
var max = 1.0 / n;
//必ず n 個
for (int f = 0; f < n; f++)
{
var psum = 0.0;
//全体でn個
for (int d = 0; d < n; d++)
{
var cnt = vs[f][d].Count;
if (cnt == 0) continue;
var x = 1.0 / n;
var p = new double[n];
//合計で m 個
//ここまででO(N(N+M))
var vv = new List<int>();
foreach (var v in vs[f][d])
foreach (var to in G[v]) { p[to] += 1.0 / (n * G[v].Count); vv.Add(to); }
vv = vv.Distinct().ToList();
psum += Math.Max(x, solve(n, p, vv, dist));
}
max = Math.Max(max, psum);
}
IO.Printer.Out.WriteLine(max);
}
double solve(int n, double[] p, List<int> vs, int[][] d)
{
var ret = 0.0;
var r = new double[n];
for (int f = 0; f < n; f++)
{
var z = 0.0;
foreach (var v in vs)
{
var x = d[f][v];
r[x] = Math.Max(r[x], p[v]);
}
foreach (var v in vs)
{
var x = d[f][v];
z += r[x];
r[x] = 0;
}
ret = Math.Max(ret, z);
}
return ret;
}
public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput());
static T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
}
}
#region main
static class Ex
{
static public string AsString(this IEnumerable<char> ie) { return new string(System.Linq.Enumerable.ToArray(ie)); }
static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") { return string.Join(st, ie); }
static public void Main()
{
var solver = new Program.Solver();
solver.Solve();
Program.IO.Printer.Out.Flush();
}
}
#endregion
#region Ex
namespace Program.IO
{
using System.IO;
using System.Text;
using System.Globalization;
public class Printer: StreamWriter
{
static Printer() { Out = new Printer(Console.OpenStandardOutput()) { AutoFlush = false }; }
public static Printer Out { get; set; }
public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
public Printer(System.IO.Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
public Printer(System.IO.Stream stream, Encoding encoding) : base(stream, encoding) { }
public void Write<T>(string format, T[] source) { base.Write(format, source.OfType<object>().ToArray()); }
public void WriteLine<T>(string format, T[] source) { base.WriteLine(format, source.OfType<object>().ToArray()); }
}
public class StreamScanner
{
public StreamScanner(Stream stream) { str = stream; }
public readonly Stream str;
private readonly byte[] buf = new byte[1024];
private int len, ptr;
public bool isEof = false;
public bool IsEndOfStream { get { return isEof; } }
private byte read()
{
if (isEof) return 0;
if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 1024)) <= 0) { isEof = true; return 0; } }
return buf[ptr++];
}
public char Char() { byte b = 0; do b = read(); while ((b < 33 || 126 < b) && !isEof); return (char)b; }
public string Scan()
{
var sb = new StringBuilder();
for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
sb.Append(b);
return sb.ToString();
}
public string ScanLine()
{
var sb = new StringBuilder();
for (var b = Char(); b != '\n'; b = (char)read())
if (b == 0) break;
else if (b != '\r') sb.Append(b);
return sb.ToString();
}
public long Long()
{
if (isEof) return long.MinValue;
long ret = 0; byte b = 0; var ng = false;
do b = read();
while (b != 0 && b != '-' && (b < '0' || '9' < b));
if (b == 0) return long.MinValue;
if (b == '-') { ng = true; b = read(); }
for (; true; b = read())
{
if (b < '0' || '9' < b)
return ng ? -ret : ret;
else ret = ret * 10 + b - '0';
}
}
public int Integer() { return (isEof) ? int.MinValue : (int)Long(); }
public double Double() { var s = Scan(); return s != "" ? double.Parse(s, CultureInfo.InvariantCulture) : double.NaN; }
private T[] enumerate<T>(int n, Func<T> f)
{
var a = new T[n];
for (int i = 0; i < n; ++i) a[i] = f();
return a;
}
public char[] Char(int n) { return enumerate(n, Char); }
public string[] Scan(int n) { return enumerate(n, Scan); }
public double[] Double(int n) { return enumerate(n, Double); }
public int[] Integer(int n) { return enumerate(n, Integer); }
public long[] Long(int n) { return enumerate(n, Long); }
}
}
#endregion
コメント
- 面白い計算量の落とし方ではある
