Blog

『銀髪赤眼の後輩と学ぶ競技プログラミング2』サポートページ

cover

技術書典7で頒布した「銀髪赤眼の後輩と学ぶ競技プログラミング2」のサポートページです。

誤植 / 1章 / 2章 / 3章

誤植

ページ備考
p.16 解法15行目(less-1)/(100*(i+1))+1(less+100*(i+1)-1)/(100*(i+1))どちらもfloor()です。
p.29 注釈7C++では整数型どうしの割り算はこれに…C++では整数型どうしの正の割り算はこれに…小数部分が切り捨てられる。
p.32この計算、ans の値は最大で1e9+8 になりますこの計算途中の ans の値は最大で1e9+6 になります
p.45 注釈11r → r-ii → r-i
p.53dp[i][j]=max(dp[i-1]][j]+(j以外の活動の幸福度))dp[i][k]=max(dp[i-1]][j]+(j以外の活動kの幸福度))

1章

Otoshidama

Katana Thrower

Synthetic Kadomatsu

DFS
void dfs(int now(探索中の頂点番号)){
    for(int i=0; i<(now から伸びている辺の数); i++){
        next = (次に探索する頂点番号);
        if(nextをまだ探索していなければ) dfs(next);
    }
}

All Green - bit全探索解 / next_permutation解

二分探索
int binary_search(int ok, int ng){
    while (abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;
        if(f(mid)) ok = mid;
        else ng = mid;
    }
    return ok;
}

Widespread

Union-Find
struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1) { }

    // 集合をマージする
    // すでに同じ集合ならfalseが返る
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        // 要素数の少ない方を多い方に繋げる
        if (data[y] < data[x]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return true;
    }

    // ある要素がどの集合に属しているかを答える
    int root(int x) {
        // 根に直接つなぎ直す
        return data[x]<0 ? x : (data[x]=root(data[x]));
    }

    // ある集合の大きさを答える
    int size(int x) {
        return -data[root(x)];
    }
};

Decayed Bridges

Tips - つるかめ算

2章

素数、コンテスト、素数 - 試し割り法解 / エラトステネスの篩解

GCD
LL gcd(LL a, LL b) {
    if(b == 0) return a;
    else return gcd(b, a%b);
}

Anti-Division

Remainder Minimization 2019

Training Camp

拡張ユークリッドの互除法
LL extgcd(LL a, LL b, LL &x, LL &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    LL g = extgcd(b, a % b, x, y);
    LL nextx = y, nexty = x-(a/b)*y;
    x = nextx; y = nexty;
    return g;
}

int main(){
    LL a, p;
    cin >> a >> p;
    LL x, y;
    LL g = extgcd(a, p, x, y);
    while(x < 0) x += p;
    x %= p;
    cout << x << endl;
}

いろはちゃんとマス目 - 拡張ユークリッドの互除法解 / フェルマーの小定理解 / modint

modint構造体
template<int mod>
struct ModInt {
    int x;

    ModInt() : x(0) {}
    ModInt(long long y) : x( y>=0 ? y%mod : (mod - (-y)%mod) % mod ) {}


    ModInt &operator+=(const ModInt &p) {
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator-=(const ModInt &p) {
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator*=(const ModInt &p) {
        x = (int)(1LL * x * p.x % mod);
        return *this;
    }
    ModInt &operator/=(const ModInt &p) {
        *this *= p.inverse();
        return *this;
    }

    ModInt operator-() const { return ModInt(-x); }
    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

    bool operator==(const ModInt &p) const { return x == p.x; }
    bool operator!=(const ModInt &p) const { return x != p.x; }

    ModInt inverse() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) {
            t = a/b;
            a -= t*b;
            swap(a, b);
            u -= t*v;
            swap(u, v);
        }
        return ModInt(u);
    }

    ModInt pow(int e) const {
        long long a = 1, p = x;
        while(e > 0) {
            if(e%2 == 0) {p = (p*p) % mod; e /= 2;}
            else {a = (a*p) % mod; e--;}
        }
        return ModInt(a);
    }
};

3章

スターリング数
const int mod = 1e9 + 7;
using modint = ModInt<mod>;

modint S[1010][1010];

int main(){
    int N, r;
    cin >> N >> r;
    for(int i=1; i<=N; i++){
        S[i][1] = 1;
        S[i][i] = 1;
    }
    for(int i=2; i<=N; i++){
        for(int j=2; j<=r; j++){
            S[i][j] = S[i-1][j-1] + S[i-1][j] * j;
        }
    }

    for(int i=1; i<=N; i++){
        for(int j=1; j<=r; j++){
            cout << S[i][j] << " ";
        }
        cout << endl;
    }
    // 求める解はS[N][r]
}

Frog 1

Vacation

Knapsack 1

Knapsack 2

LCS

Matching