na_o_ysのブログ

プログラミングなど

SRM 638 Div1 Med, NarrowPassage2

本番では解けなかったけど, 綺麗な DP 問題だった.

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13295

廊下に N (<= 50) 匹の狼が配置されている. 各狼のサイズは vector<int> size で与えられている. 二匹の狼がすれ違えるのは, サイズの合計が maxSumSize 以下の場合のみである. 狼の並び方の総数を 1000000007 の剰余で答えよ.

方針

最小の狼 m について考える. m がすれ違えない狼は, m 以外のどの狼ともすれ違えないので, 位置は固定.

よって答えは以下の再帰式で表せる.

count(size, maxSumSize) = m が動ける範囲 * count(m を除いた size, maxSumSize)

解答

#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;
using ll = long long;
const ll MOD = 1000000007;

class NarrowPassage2
{
public:
    int count(vector <int> size, int maxSizeSum)
    {
        int N = size.size();
        if (!N) return 1;
        auto m = min_element(size.begin(), size.end());
        int idx = distance(size.begin(), m);
        ll cnt = 1;
        for (int i = idx+1; i < N && size[i]+*m <= maxSizeSum; i++) cnt++;
        for (int i = idx-1; i >= 0 && size[i]+*m <= maxSizeSum; i--) cnt++;
        size.erase(m);
        return (cnt * count(size, maxSizeSum)) % MOD;
    }
};