SRM638D1Med NarrowPassage2
苦手だけどこういうのは好き
問題概要(原文)
$N$ 匹の狼が一列に並んでいる．左から $i$ 番目の狼の大きさは $A_{i}$ である．ある隣り合う狼について $A_{i} + A_{i+1} \leq X$ ならスワップができる． はじめの数列を $(1,2, \ldots , N)$ として，最終的な並べ方は何通りあるか？
考察
$i \rightarrow j$ という関係がいっぱい与えられているときのトポロジカルソートの結果が何通りあるか？という問題である． これは難しい問題なので，もう少し考えよう． 大きさの数列が $B$ で表される狼達ののvalidな並べ方を $f(B)$ とする．
$B$ について， $max(B) + min(B) \leq X$ ならば最小値はどこにでも移動できる．よって， $f(B) = |B| f(B^{\prime})$ ($B^{\prime}$ は最小値を一つ取り除いた数列)となる．
また， $max(B) + min(B) \geq X$ ならば最大値はどこにも移動できない．よって $f(B) = f(B_l^{\prime}) f(B_r^{\prime})$ ($B_l^{\prime}$ は最大値で分割された数列の左側， $B_r^{\prime}$ は右側)となる．
この分割はどのように試してもよい．なので分割は最大でも $N-1$ 回試せば良い．計算量は $O(N^2)$
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class NarrowPassage2
{
public int count(int[] size, int maxSizeSum)
{
var n = size.Length;
const long MOD = 1000000007;
Func<List<int>, long> dfs = null;
dfs = a =>
{
if (a.Count <= 1) return 1;
var min = a.Min();
var max = a.Max();
long ret = 0;
if (min + max <= maxSizeSum)
{
var b = new List<int>();
foreach (var x in a)
if (x == min) min = -1; else b.Add(x);
ret = a.Count * dfs(b) % MOD;
}
else
{
var b = new List<int>();
var c = new List<int>();
foreach (var x in a)
{
if (x == max) max = -1;
else
{
if (max >= 0) b.Add(x);
else c.Add(x);
}
}
ret = dfs(b) * dfs(c) % MOD;
}
return ret;
};
var ans = dfs(size.ToList());
return (int)ans;
}
}
コメント
- トポロジカルソートの数え上げに落として考察していて完全にミス
- こういう再帰的に考えていくのがまだ苦手だなぁ
