OUPC β A,B,D 解説 - くるのプログラミング記録

OUPC β　解説

Grundy Number (200)
Doubling Step (300)
Product Grid (500)

Grundy Number (200)

writer: ningenMe
URL

https://www.hackerrank.com/contests/oupc-beta/challenges/grundy-number

解説:

与えられる入力をsetや配列に格納し、数字の既出管理を行いましょう。
数列 $A$ の最大値を $A_{max}$ とすると $O(N+A_{max})$ で解くことが出来ます。
writer解

#include <iostream>
#include <vector>

using namespace std;

int main(void) {
    int N; cin >> N;
    vector<int> C(101,1);
    for(int i = 0; i < N; ++i) {
        int A; cin >> A;
        C[A] = 0;
    }
    for(int i = 0; i <= 100; ++i) {
        if(C[i]) {
            cout << i << endl;
            break;
        }
    }    
    return 0;
}

Doubling Step (300)

writer: ningenMe
URL

https://www.hackerrank.com/contests/oupc-beta/challenges/doubling-step

解説:

dpで解きましょう。 $dp_{i}: i$ 番目の球に乗るような場合の数。
1つの球から移動できる選択肢は高々 $O(\log(N))$ 個なので、全体として $O(N\log(N))$ で解くことが出来ます。

writer解

#include <iostream>
#include <vector>

using namespace std;
constexpr long long MOD = 998244353;

int main(void) {
    long long N; cin >> N;
    vector<long long> dp(N+1,0);
    dp[1] = 1;
    for(int i = 1; i < N; ++i) {
        for(int j = 0; (i + (1 << j)) <= N; j++) {
            (dp[i + (1 << j)] += dp[i]) %= MOD;
        }
    }
    cout << dp[N] << endl;
    return 0;
}

Product Grid (500)

writer: ningenMe
URL

https://www.hackerrank.com/contests/oupc-beta/challenges/product-grid

解説:

まず定数 $K$ の値は、入力で与えられる $A_{1,j}\ (1 \leq j \leq W)$ の最小公倍数になります。
ここで $K$ はとても大きくなるため、実装上では $K$ を素因数で管理します。
$K$ の値が分かったので、各列において $A_{1,j}\ (1 \leq j \leq W)$ 以外の残りの数字の積が $K/A_{1,j}$ になれば条件を満たします。
これは $j$ 番目の列を考えたとき、 $K/A_{1,j}$ の各素因数を $A_{2,j}...A_{H,j}$ のいずれかに割り当てることをすればよいです。
よって割り当てる素因数の数を $r$ 個としたとき、重複組み合わせを考えると二項係数 $Comb(H-1+r - 1,r)$ で場合の数を数えることができます。
よって各列においてそれぞれ独立に計算することで求める場合の数を得ることが出来ました。

しかし $A_{max}=100000$ 以下の素数の数は $L=9592$ 個であるため、上記の解法では最悪計算量 $O(WL)$ となりTLEします。
ここで各列において、1行目の値 $A_{1,j}\ (1 \leq j \leq W)$ に含まれる素因数が $K$ に含まれる素因数に比べて比較的少ないことを利用します。
$2*3*5*7*11*13 = 30030 < A_{max} < 510510 = 2*3*5*7*11*13*17$ であることを考えると、 $A_{1,j}\ (1 \leq j \leq W)$ に含まれる素因数の種類の個数は高々6個です。
なので各列において $A_{1,j}=1$ と仮定して $K/A_{1,j} = K$ の各素因数を $A_{2,k}...A_{H,k}$ に振り分けます。この値は全列で同じ値なので $O(L+W)$ で計算できます。
その後各列において、実際の $A_{1,j}$ の値の差分だけ計算すればよく、これは $O(W)$ で計算出来ます。
よって、全体として $O(Wsqrt(A_{max})+H+ L)$ で解くことが出来ます。

writer解

#include <iostream>
#include <vector>
#include <map>

using namespace std;
template <class T> void chmax(T& a, const T b){a=max<T>(a,b);}
constexpr long long MOD = 998244353;

//Prime Factorization O(sqrt(N))
vector<pair<long long,long long>> PrimeFactorization(long long N) {
    vector<pair<long long,long long>> ret;
    for (long long i = 2,M = N; i*i <= M; ++i) {
        if (N%i == 0) {
            long long cnt = 0;
            while (N%i == 0) N /= i, cnt++;
            ret.push_back({i,cnt});
        }
    }
    if (N != 1) ret.push_back({N,1});
    return ret;
}

//Combination Mod
class CombinationMod {
public:
	vector<long long> fac,finv,inv;
	long long mod;

	CombinationMod(int N,long long mod) : fac(N + 1), finv(N + 1), inv(N + 1), mod(mod) {
		fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1;
		for (int i = 2; i <= N; ++i) {
			fac[i] = fac[i - 1] * i % mod;
			inv[i] = mod - inv[mod%i] * (mod / i) % mod;
			finv[i] = finv[i - 1] * inv[i] % mod;
		}
	}
	
	long long num(int n, int k) {
		return ((n < 0 || k < 0 || n < k) ? 0 : fac[n] * (finv[k] * finv[n - k] % mod) % mod);
	}
};

//Pow_Mod O(log(n))
long long PowMod(long long x, long long n, long long mod) {
    long long res = 1;
    for (; n > 0; n >>= 1, (x *= x) %= mod) if (n & 1) (res *= x) %= mod;
    return res;
}

//Inv_Mod O(log(mod))
long long InvMod(long long x, long long mod){
	return PowMod(x,mod-2,mod); 
}

//O(WsqrtA + H + LlogL)解法
int main(void) {
    long long H,W; cin >> H >> W;
    vector<long long> A(W);
    for(int i = 0; i < W; ++i) {
        cin >> A[i];
    }

    //素因数を列挙　O(W*sqrt(A))
    vector<vector<pair<long long,long long>>> P(W);
    for(int i = 0; i < W; ++i) {
        P[i] = PrimeFactorization(A[i]);
    }
    
    //L<=(Kに含まれる素数の個数の最大値)<=(maxA以下の素数の個数)=9592
    //最小のKの素因数分解を構築　O(W + LlogL) 
    map<long long, long long> K;
    for(int i = 0; i < W; ++i) {
        for(auto e: P[i]){
            long long p = e.first;
            long long c = e.second;
            chmax(K[p],c);
        }
    }

    //二項係数 O(H) 2^16 = 65536 < maxA < 131072 = 2^17 < 2^20
    CombinationMod CM(H+20,MOD);
    
    //A=1のときの数え上げを前計算 O(LlogL)
    long long cnt = 1;
    for(auto e:K) {
        long long N = e.second;
        //N個の素因数をH-1個の箱に配る O(1)
        cnt *= CM.num(N+H-2,N);
        cnt %= MOD;
    }

    //全てA=1と仮定して前計算 O(W)
    long long ans = 1;
    for(int i = 0; i < W; ++i) {
        ans *= cnt;
        ans %= MOD;
    }

    //i=0から数え上げ O(W)
    for(int i = 0; i < W; ++i){

        //Aに素因数がある部分だけ数え直しO(1) 2*3*5*7*11*13 = 30030 < maxA < 510510 = 2*3*5*7*11*13*17 なので高々6回
        for(auto e: P[i]){
            long long N = K[e.first];
            //N個の素因数をH-1個の箱に配る数を戻す O(1)
            ans *= InvMod(CM.num(N+H-2,N),MOD);
            ans %= MOD;

            //M個の素因数をH-1個の箱に配る O(1)
            long long M = K[e.first] - e.second;
            ans *= CM.num(M+H-2,M);
            ans %= MOD;
        }
    }

    cout << ans << endl;
     
    return 0;
}