SRM614

オーバーフローでSmallを落としたorz

MinimumSquare

正方形の位置とサイズを与えられた点から決めて含まれる点の個数を調べる。サイズを二分探索することで高速化。

#include <string>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class MinimumSquare{public:
long long minArea( vector <int> x, vector <int> y, int K )
{
    int n = (int)x.size();
    long long ans = LLONG_MAX;

    for (int xi=0; xi<n; xi++)
    for (int yi=0; yi<n; yi++)
    {
        long long x0 = x[xi]-1;
        long long y0 = y[yi]-1;
        vector<long long> s;
        for (int i=0; i<n; i++)
        {
            if (x[i]+1>x0)
                s.push_back(x[i]+1-x0);
            if (y[i]+1>y0)
                s.push_back(y[i]+1-y0);
        }
        sort(s.begin(), s.end());

        int l=0;
        int r=(int)s.size()-1;

        auto check = [&](int p) -> bool
        {
            int c = 0;
            for (int i=0; i<n; i++)
                if (x0<x[i] && x[i]<x0+s[p] &&
                    y0<y[i] && y[i]<y0+s[p])
                    c++;
            return c >= K;
        };

        if (!check(r))
            continue;

        while (r-l>1)
        {
            int m = (l+r)/2;
            (check(m)?r:l) = m;
        }
        
        ans = min(ans, s[r]*s[r]);
    }

    return ans;
}};

CycleColoring

小さいサイクルには点線の辺が2本生えている。その2本が同じ色になる場合と異なる色になる場合が何通りあるかを求め、それを使って答えを求める。小さいサイクルも大きいサイクルも、始点と同じ色になる場合と異なる色になる場合を覚えておいて動的計画法。

#include <string>
#include <vector>
using namespace std;

//	a^b mod m
long long powm(long long a, long long b, long long m)
{
    long long r=1,t=a;
    for(;b>0;t=t*t%m,b>>=1)if(b&1)r=r*t%m;
    return r;
}

class CycleColoring{public:
int countColorings( vector <int> vertexCount, vector <int> fromVertex, vector <int> toVertex, int K )
{
    const int M = 1000000007;
    int N = (int)vertexCount.size();
    vector<long long> S(N);	//	fromとtoが同じ色になる場合の数
    vector<long long> D(N);	//	fromとtoが異なる色になる場合の数

    for (int i=0; i<N; i++)
    {
        //	type=0ならS[i]を、type=1ならD[i]を計算する
        for (int type=0; type<2; type++)
        {
            long long s = 1;
            long long d = 0;
            int n = vertexCount[i];
            int dist = (fromVertex[i] - toVertex[(i-1+N)%N] + n) % n;

            if (dist==0 && type==1)
            {
                D[i] = 0;
                continue;
            }

            for (int j=1; j<n; j++)
            {
                long long ps = s;
                long long pd = d;
                s = pd;
                d = (ps*(K-1) + pd*(K-2))%M;
                //	toの位置を0としてfromの位置になったら色が条件を満たすか確認
                if (j==dist)
                    (type==0 ? d : s) = 0;
            }

            (type==0 ? S[i] : D[i]) = d;
        }
    }

    long long s = K;
    long long d = 0;

    long long Ki = powm(K-1,M-2,M);	//	1/(K-1)

    for (int i=0; i<N; i++)
    {
        long long ps = s;
        long long pd = d;

        s = (ps*S[i] + pd*D[i]%M*Ki) % M;
        d = (ps*D[i] + pd*D[i]%M*Ki%M*(K-2)%M + pd*S[i]%M) % M;
    }
    
    return (int)s;
}};