yukicoder No.140 みんなで旅行

問題文: No.140 みんなで旅行 - yukicoder

Writer 解説: yukicoder : No.140 みんなで旅行 - kmjp's blog

問題概要

$ N (\leq 555)$組の夫婦 $ 2N $ をグループ分けする．各グループに最低1組以上は夫婦の両方がいるという条件でグループ分けをするとき，ありうるわけかたのパターン数を$ 10^9+7$で割ったあまりを求めよ．

解法概要

夫と妻が同じグループに入るような夫婦 $ x $ 組と，夫と妻が別のグループに入るような夫婦 $ (N-x) $ 組を分けて考える．同じグループになる $ x $ 組の夫婦の選び方は $ _{N} C_{x}$ 通りある．

まず，夫婦が同じグループになる $ x $ 組について考える． $ x $ 組の夫婦で $ y $ 個のグループを作るときの分け方を $ S(x, y) $ 通りとすると，

$ S(x, y) = S(x-1, y-1) + y S(x-1, y) $

という漸化式ができるので，これを前処理として DP で求めておけばあとは定数時間で呼び出せる. （このように， $ x $ 個のものを $ y $ グループに分けるときの分け方の数を第二種スターリング数というらしい．)

次に，夫婦が別のグループになる $ (N-x) $ 組について考える．

夫婦が同じグループになる場合と同様に， $ y $ 個のグループを作るとすると，この2人を別々のグループに入れる入れ方は $ y(y-1) $ 通りである．これを $ (N-x) $ 組分考えるので，$ (y(y-1))^{(N-x)} $ 通りとなる．

以上から，求めるべき分け方の個数は $ \sum_{x=1}^{N} \sum_{y=1}^{x} {}_{N} C_{x} \times S(x, y) \times (y(y-1))^{(N-x)} $ 通りである．

ソースコード

#include <iostream>

using namespace std;

using ll =  long long;

constexpr ll MOD = 1000000007;
constexpr int N_MAX = 556;

ll fact[N_MAX], rfact[N_MAX];

ll perm(ll n, ll r){
    return (fact[n] * rfact[r]) % MOD;
}

ll comb(ll n, ll r){
    return (perm(n, r) * rfact[n-r]) % MOD;
}

void init(ll n){
    fact[0] = fact[1] = 1;
    rfact[0] = rfact[1] = 1;
    for(int i=2;i<=n;++i) {
        fact[i] = (fact[i-1] * (ll)i) % MOD;
        rfact[i] = 1;
        ll k = MOD-2;
        ll a = fact[i];
        while(k > 0){
            if(k & 1){
                rfact[i] *= a;
                rfact[i] %= MOD;
            }
            a *= a;
            a %= MOD;
            k  >>= 1;
        }
    }
}

class Stirling {
    public:
    int n, m; // ボールの個数，グループ数
    ll s[2*N_MAX][N_MAX];
    Stirling(int n, int m, bool is_the_second_kind=true): n(n), m(m) {
        if(is_the_second_kind) {
            for(int i=0;i<=n;++i) {
                s[i][0] = (i == 0)?1:0;
                if(i == 0) continue;
                for(int j=1;j<=m;++j) {
                    s[i][j] = (s[i-1][j-1] + (s[i-1][j]*j) % MOD) % MOD;
                }
            }
        }
    }

    ll get(int i, int j) {
        return s[i][j];
    }
};

ll modpow(ll a, ll t) {
    ll ret = 1LL;
    while(t){
        if(t & 1LL){
            ret *= a;
            ret %= MOD;
        }
        a *= a;
        a %= MOD;
        t >>= 1;
    }
    return ret;
}

int main() {
    ll n;
    cin >> n;
    init(n);
    Stirling s = Stirling(n, n);

    ll ans = 0LL;
    for(ll x=1;x<=n;++x) {
        for(ll y=1;y<=x;++y) {
            ans += (((comb(n, x) * s.get(x, y)) % MOD) * modpow((y * (y-1)) % MOD, n-x)) % MOD;
            ans %= MOD;
        }
    }
    cout << ans << endl;
}

所感

第二種スターリング数を学んだ． 漸化式を立てて DP に落とし込むやり方は汎用性が高そうなので使えるようになっておきたい．

Codeforces Round #563 (Div. 2) D. Ehab and the Expected XOR Problem

問題: http://codeforces.com/contest/1174/problem/D

公式解説: https://codeforces.com/blog/entry/67388

問題概要

2つの正の整数 $ n (\le 18) $ と $ x (\lt 2^n) $ が与えられる．次の 3 つの条件を満たす数列 $ a $ を構成せよ．

• $ a $ の要素 $ a_i $ について， $ 1 \leq a_i \lt 2^n $ が成り立つ．
• $ a $ の空でない部分列について，その部分列に含まれる要素の xor を取ったものが 0 でない，かつ $ x $ でもない．
• 上 2 つの条件を満たす数列のうち最長のものである．

解法概要

$ a $ の累積 xor を考える．$ b_i = a_1 $ から$ a_i $ までの累積 xor となるような数列を $ b $ とする．

$ a $ の $ l $ 番目から$ r $ 番目までの要素を切り出した部分列についての xor を考えるとき，

$ b_{l-1} \oplus a_{l} \oplus a_{l+1} \oplus \cdots \oplus a_{r} = b_{r} $

が成り立つ． つまり

$ a_{l} \oplus a_{l+1} \oplus \cdots \oplus a_{r} = b_{l-1} \oplus b_{r} $ ．

したがって，問題の2番目の条件はこのように言い換えられる．

「 $ b $ に2回以上同じ値が登場せず，かつ，2つの値の xor を取ると $ x $ になるような値の組も登場しない．」

あとはこの条件にしたがって， $ b $ にできるだけ多くの数を詰め込み， $ b $ にしたがって $ a $ を作るだけである．

$ a_1 = b_1 $ を除けば， $ a_i = b_{i-1} \oplus b_i $ で求めることができる．

長さ $ 2^{18} $ の vector を用意しようとしたら Runtime Error を食らったので， set にすでに使った値を入れておいて find メソッドで値 i を使って良いかどうか判定するようにした．

ソースコード

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main() {
    std::ios::sync_with_stdio(0); cin.tie(0);
    int n, x;
    cin >> n >> x;

    vector<int> b;
    set<int> st;
    st.insert(0);
    for(int i=1;i<(1<<n);++i) {
        if(st.find(i) != st.end() || st.find(i^x) != st.end()) continue;
        b.push_back(i);
        st.insert(i);
    }

    int m = b.size();
    cout << m << endl;
    if(m) {
        cout << b[0];
        for(int i=1;i<m;++i){
            cout << " " << (b[i-1]^b[i]);
        }
        cout << endl;
    }
}

所感

結構典型っぽいのに全然わからなかったので反省．

AtCoder Beginner Contest 128 F - Frog Jump

問題: F - Frog Jump

公式解説: https://img.atcoder.jp/abc128/editorial.pdf

問題概要

座標 上を移動する．移動は座標 0 から始めて， だけ正の方向に進むことと， だけ負の方向に進むことを交互に繰り返す． にたどり着いた地点で終了する．同じ座標を2度訪れてはいけない．

座標 0 と 座標 以外の各座標は，訪れると点数がもらえる．負の点数もありうる．

と を適切に定め，もらえる点数の合計を最大化せよ．

解法概要

座標 以降に移動することは考えなくて良いので， にたどり着くことができるとしたら正の方向に進んだときだけである．また， であるような場合も考えなくて良い． したがって，座標の遷移は次のような形になるはずである:

回移動するとする) ．

これの奇数 / 偶数番目を抜き出した数列を考えると，隣接する要素の差が の等差数列となっている:

奇数番目の要素を抜き出した数列:

偶数番目の要素を抜き出した数列．

ここで， とおくと

奇数番目の要素を抜き出した数列:

偶数番目の要素を抜き出した数列．

だいぶスッキリして見える (主観) ．偶数番目の要素について，(0 との差ではなく) N-1 との差に注目して式変形をすると:

奇数番目の要素を抜き出した数列:

偶数番目の要素を抜き出した数列．

したがって，題意の通りに移動したときのスコアは の関数 として表現することができる．

と表現できることから， が決まればスコアは程数時間で求めることができる．

また， でなければならないことから，全体の時間計算量は である．*1

ただし， が の約数であるような場合のみ注意が必要である．このような場合は， となったとき，同じ座標のスコアを 2 回足してしまうことになる．同じ座標を 2 度訪れてはいけないから， が の約数である場合には となった地点でループを抜けなければならない．

ソースコード

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

using namespace std;

typedef long long ll;

int main() {
    int n;
    cin >> n;
    vector<ll> s(n);
    for(int i=0;i<n;++i){
        cin >> s[i];
    }

    ll score = 0LL;
    for(int c=1;c<n/2;++c) {
        ll tmp_score = 0LL;
        if((n-1) % c) {
            for(int x=0;n-1-c*x>=c;++x) {
                tmp_score += s[c*x] + s[n-1-c*x];
                score = max(score, tmp_score);
            }
        } else {
            for(int x=0;c*x<n-1-c*x;++x) {
                tmp_score += s[c*x] + s[n-1-c*x];
                score = max(score, tmp_score);
            }
        }
        
    }

    cout << score << endl;
}

所感

考察難易度 >> 実装難易度な問題は不得意．

*1: より