メモ帳がわり

個人的なメモを残します。主に競プロ

【ABC114】D - 756

AtCoder AtCoder Beginner Contest DFS 素因数分解 数学 約数列挙 N重forループ

atcoder.jp

解法

N!の約数を順に列挙していこうとすると、N次第ではN!がとてつもなく大きい数になってしまうため、現実的ではない。
そこで、約数を素因数を組み合わせた結果と考えることにする。
具体的には、1 ~ Nまでの数をそれぞれ素因数分解し、それぞれの素因数が何回登場したかを記録していき、最後に組み合わせ方を全探索する。

約数の個数を奇数にしようとすると、それぞれの素因数を選ばない or 偶数個使用する、の2択になるため、すべてを探索する必要はなかったりする。

実装

n重forループを使って書きたくなる全探索は、DFSによって表現することができる。

// ans: 答え, cnt: 約数の個数, iter: 次にどの素因数を探索するか, fac: N!を素因数分解した結果
void dfs(ll &ans, int cnt, int iter, vector<ll> &fac) {
    if (cnt == 75) {
        ans++;
        return;
    } else if (cnt > 75 || iter >= fac.size()) return;

    // 素因数を選ばない or 偶数個使用する場合だけ探索
    for (int i = 0; i <= fac[iter]; i += 2) {
        dfs(ans, cnt * (i + 1), iter+1, fac);
    }
}

void solve(long long N){
  // N!を素因数分解&集計
    map<ll, ll> fac;
    REP (i, N) {
        auto mp = prime_fac(i + 1);
        for (auto m : mp) fac[m.first] += m.second;
    }

  // 配列に移し替え(DFSをしやすくするため)
    vector<ll> vec;
    for (auto f : fac) vec.push_back(f.second);

    ll ans = 0;
    dfs(ans, 1, 0, vec);
    c(ans)
}

【ABC179】E - Sequence Sum

AtCoder AtCoder Beginner Contest 競技プログラミング 鳩ノ巣原理 ループ

atcoder.jp

解法

愚直に数列を前から順に見ていこうとすると、計算量はO(N)になり、N ≦ 1010の制約では、時間がかかりすぎてしまう。
なので、計算量を落とす方法を考える必要がある。

mod 〇〇で考えられる問題で鳩ノ巣原理が使えるというのは典型。
この問題では、数列を初項から第M+1項まで順にみていった場合、どこかで必ず同じ値を持つ項が出てくる。
この問題の漸化式では、前の項の情報しか参照していないため、「同じ値が出てきた」＝「ループが始まった」と言い換えることができる。
ループするということは、何度も同じ順番で同じ値の項が登場するということであり、無駄な計算を省くことができる。

どこからループするかさえわかれば、あとはO(1)で計算することができるため、全体計算量はO(M)になる。

計算方法

答え ＝ ループ開始までの総和 + ループ1回分の区間の総和 × ループ回数 + 最後のループの始まりから第N項まで

実装

ループの問題は実装でバグらせやすいので気をつけよう。
具体例を考えながら、実装すると考えの整理にもなってよかった。
また、そもそもループする前に第N項に到達するというパターンもあるため、注意が必要。

void solve(long long N, long long X, long long M){
    // times[i]回目にiが登場した(まだ登場していない場合、-1)
    vector<ll> times(M, -1);
    // i回目までの数列の合計値
    vector<ll> rui(M+10, 0);

    ll cur = X; // 数列のi項目
    ll ans = X;
    N--; // 初項の分を引いておく
    times[X] = 1;
    rui[1] = X;

    ll roop_times = 0;
    for (int i = 2; i <= M+1; i++) {
        if (N <= 0) {
            c(ans);
            return;
        }

        cur = cur * cur % M;

        if (times[cur] != -1) {
            // 何項でループしているか
            roop_times = i - times[cur];
            break;
        }
        times[cur] = i;
        ans += cur;
        rui[i] = ans;
        N--;
    }

    // 最後に到達した地点
    ll t = times[cur] + roop_times - 1;
    
    // 1回のループの合計値
    ll roop = rui[t] - rui[times[cur] - 1];
    // N / roop_times => ループ回数
    ans += N / roop_times * roop;

    // ループ後の余り
    N %= roop_times;
    ll amari = rui[times[cur] + N - 1] - rui[times[cur] - 1];
    ans += amari;

    cout << ans << endl;
}

典型問題かつ、バグらせやすいから、ライブラリかスニペットにしてもいいかもしれない、と思った。

【ABC174】C - Repsept

AtCoder AtCoder Beginner Contest 鳩ノ巣原理 modint

atcoder.jp

解法

Kの倍数かどうかがわかればよいので、 7, 77, 777... は mod Kで考えてよい。
さらに、 7, 77, 777... という数列を順に調べることをK+1回繰り返せば、鳩ノ巣原理で必ずループが始まる。
そのため、 7, 77, 777... という数列を順に調べることをK回繰り返して、その中にKの倍数があれば何回目かを出力、なければ-1を出力すればよい。

実装

10iを計算するときは、繰り返し2乗法を使わないと間に合わない。

long long modpow(long long a, long long n, long long k) {
    if (n == 0) return 1;
        auto t = modpow(a, n / 2, k) % k;
        t = t * t % k;
        if (n & 1) t = t * a % k;
        return t;
}

void solve(long long K){
    vector<long long> k(K+1, 0);
    REP (i, K) {
        k[i+1] = (k[i] + modpow(10LL, i, K) * 7) % K;
        if (!k[i+1]) {
            cout << i+1 << endl;
            return;
        }
    }
    cout << -1 << endl;
}

【ABC126】E - 1 or 2

AtCoder AtCoder Beginner Contest UnionFind

atcoder.jp

解法

偶奇にしか興味がないため、mod 2で考えてよい。

次のように場合分けして考える。

  • Z_i ≡ 0　(mod　2) のとき

A_{X_i} と A_{Y_i} のどちらもが偶数、または奇数であることがわかる。
そのため、どちらかの偶奇が決定されると、もう片方の偶奇も自動的に判明する。

  • Z_i ≡ 1　(mod　2) のとき

A_{X_i} と A_{Y_i} の片方が偶数で、もう片方が奇数であることがわかる。
こちらも、どちらかの偶奇が決定されると、もう片方の偶奇も自動的に判明する。

以上より、 A_{X_i} と A_{Y_i} の片方の数が判明すれば、もう片方の数もわかるため、連鎖的に数を特定していくことができる。
よって、UnionFindなどを使って連結成分数を数えれば、それが答えになる。

実装

// UnionFind構造体
struct UnionFind {
    vector<long long> par, siz;

    UnionFind(long long n) : par(n, -1) , siz(n, 1) { }

    // 根を求める
    long long root(long long x) {
        if (par[x] == -1) return x;
        else return par[x] = root(par[x]);
    }

    // x と y が同じグループに属するかどうか (根が一致するかどうか)
    bool issame(long long x, long long y) {
        return root(x) == root(y);
    }

    // x を含むグループと y を含むグループとを併合する
    bool unite(long long x, long long y) {
        x = root(x), y = root(y);
        if (x == y) return false; 
        if (siz[x] < siz[y]) swap(x, y);
        par[y] = x;
        siz[x] += siz[y];
        return true;
    }

    // x を含むグループのサイズ
    long long size(long long x) {
        return siz[root(x)];
    }
};

void solve(long long N, long long M, std::vector<long long> X, std::vector<long long> Y, std::vector<long long> Z){
    UnionFind Uf(N);
    REP (i, M) Uf.unite(X[i]-1, Y[i]-1);

    set<ll> st;
    REP (i, N) st.insert(Uf.root(i));

    c(st.size())
}

【ABC135】D - Digits Parade

AtCoder AtCoder Beginner Contest 桁DP DP 競技プログラミング

atcoder.jp

解法

制約的にも桁DPがしたくなる。
そこで次のDPを考える。

dp[i][j] ← 下からi桁目までみた時、13で割った数がjであるような場合は何通りあるか

上からi桁目としてもいいが、計算が楽なので下から見ていくことにした。

次のように遷移する。
ここで、0 ≦ i < |S|, 0 ≦ j < 13, 0 ≦ k < 10 とする。

  • S[i]が？のとき
    • dp[i + 1][(j + 10i * k) MOD 13] += dp[i][j]
  • S[i]が？でないとき
    • dp[i + 1][(j + 10i * S[i]) MOD 13] += dp[i][j]

答えは、dp[|S|][5]になる。

実装

10iを計算するときは、愚直に実装するとO(|S|)になってしまうので、繰り返し二乗法を利用する。
modintを使用できると実装が楽になる。
下の実装のmintはmod 109 + 7、mint13はmod 13 で計算している。

void solve(std::string S){
    reverse(all(S)); // 逆順にする

    // dpテーブル
    vector<vector<mint>> dp(S.size()+1, vector<mint>(13, 0));
    dp[0][0] = 1;

    REP (i, S.size()) {
        if (S[i] == '?') {
            // ?のときは0~9までの場合を全て試す
            REP (j, 10) {
                mint13 cur = modpow((mint13)10, i) * j;
                REP (k, 13) {
                    dp[i + 1][(cur.val + k) % 13] += dp[i][k];
                }
            }
        } else {
            mint13 cur = modpow((mint13)10, i) * (S[i] - '0');
            REP (k, 13) {
                dp[i + 1][(cur.val + k) % 13] += dp[i][k];
            }
        }
    }

    cout << dp[S.size()][5] << endl;
}```

【ABC147】D - Xor Sum 4

AtCoder AtCoder Beginner Contest 競技プログラミング bitごとに考える 主客転倒 xor bit演算 実装方法

atcoder.jp

解法

問題文通り実装してもO(N2)で間に合わない。

XOR演算を繰り返すため、ビットごとに考えたくなる。
そこで位ごとに、ビットが立っているかどうかをA[i]すべてで調べ、いくつビットが立っているかを計算することにする。
A[i] ≦ 260 なので、60の長さの配列を準備しておけば良い。
この配列をbit_cntと呼ぶことにする。

この計算ができたら、A[i]のjビット目が答えにどれだけ影響を与えるかを計算していく。
具体的には、

  • A[i]のjビット目が立っている場合
    • jビット目が立っていない要素が他にいくつあるかを考える
    • N - bit_cnt[j]がそれに該当するが、既に見た要素も含まれているのでiを引いておく(重複して計算するのを回避するため)
    • つまり、2j * (N - i - bit_cnt[j])を答えに加算する
    • bit_cnt[j]を一つ減らす
  • A[i]のjビット目が立っていない場合
    • jビット目が立っている要素が他にいくつあるかを考える
    • それは、bit_cnt[j]が該当する
    • つまり、2j * bit_cnt[j] を答えに加算する

実装

modintを使うと実装が楽。

bit演算についてはこの記事がとても分かりやすい。

qiita.com

void solve(long long N, std::vector<long long> A){
    vector<int> bit_cnt(60, 0);
    REP (i, N) {
        REP (j, 60) {
            // A[i]のjビット目が立っている場合
            // bit_cnt[j]に加算
            if (A[i] & (1LL << j)) bit_cnt[j]++;
        }
    }

    mint ans = 0;
    REP (i, N) {
        REP (j, 60) {
            mint n = (1LL << j);
            // A[i]のjビット目が立っている場合
            if (A[i] &  (1LL << j)) {
                ans += n * (N - i - bit_cnt[j]);
                bit_cnt[j]--;
            } else {
                ans += n * bit_cnt[j];
            }
        }
    }

    cout << ans << endl;
}```

【ABC144】E - Gluttony

AtCoder AtCoder Beginner Contest 競技プログラミング 二分探索

atcoder.jp

解法

最大値の最小化と聞くと二分探索が思い浮かぶ。
そこで答えで二分探索できないか考えてみることにする。

修行なしでメンバーと食べ物を最適にマッチングするには、食べ物を昇順、メンバーを降順に並び替えて同じ番号を組み合わせれば良い。
この組み合わせごとのコストを、修行で二分探索した値まで減らすことをN回繰り返して、修行回数をK回以内に抑えられることができるかを二分探索の判定に使う。

実装

bool isOK(ll mid, ll N, ll K, vector<ll> &A, vector<ll> &F) {
    REP (i, N) {
        // 修行により減らさないといけない成績
        ll remain = max(0LL, A[i] * F[i] - mid);
        // 修行した数を減らす
        K -= myceil(remain, F[i]);
        // 修行回数が足りなければNG
        if (K < 0) return false;
    }
    return true;
}

void solve(long long N, long long K, std::vector<long long> A, std::vector<long long> F){
    sort(rall(A)); // 降順ソート
    sort(all(F)); // 昇順ソート

    ll ng = -1;
    ll ok = INF64;

    // 二分探索
    while (abs(ok - ng) > 1) {
        ll mid = (ok + ng) / 2;
    
        if (isOK(mid, N, K, A, F)) ok = mid;
        else ng = mid;
    }

    cout << ok << endl;
}