競技プログラミング用コピペコード集（C#）

主にAtcoderでやる競技プログラミングで再利用するために、C#で書いたコードたちを載せてみる。どれも既知のアルゴリズムなのでコピペとかして構わないけど、もし間違っていても責任はとらない。

また何かあれば追加するかも。

公約数／公倍数

最大公約数

static long Gcd(long m, long n) {
    if (m < n) {var t=m; m=n; n=t;}

    while (true) {
        var mod = m % n;
        if (mod == 0) return n;
        m = n;
        n = mod;
    }
}

ユークリッド互除法の実装。

最小公倍数

※2020/5/13 計算途中でのオーバーフローに対策

static long Lcm(long m, long n) {
    var x1 = Math.Max(m, n);
    var x2 = Math.Min(m, n);

    var gcd = Gcd(x1, x2);
    return x1 / gcd * x2;
}

上のGcdが必要。最大公約数から最小公倍数を求める公式。

演算

累乗

※2020/5/31 2^32でOFしてたのに対応

static long Pow(long x, long n) {
    long ans = 1;
    while (n > 0) {
        if (n % 2 == 1) {
            ans = ans * x;
        }
        n /= 2;
        if(n == 0) break;
        x = x * x;
    }
    return ans;
}

通常はMath.powを使う累乗の手書き実装。n<0には対応しない。単純ループするとO(n)だが、2乗を入れ子にするアルゴリズムで実装してO(log n)。いわゆる繰り返し二乗法。

x^20 = (((x^2)^2)^2)^2 * (x^2)^2

累乗（Mod）

※2020/5/31 2^32でOFしてたのに対応

static long ModPow(long x1, long x2){
    long ans = 1;
    while (x2 > 0) {
        if (x2 % 2 == 1) {
            ans = (ans * x1) % Mod;
        }
        x2 /= 2;
        if(x2 == 0) break;
        x1 = (x1 * x1) % Mod;
    }
    return ans % Mod;
}

前述も累乗にModを差し込んだだけだがこの後で再利用するため載せる。Modは定数が定義されているものとする。

除算（Mod）

static long ModDiv(long x1, long x2) {
    long bb = ModPow(x2, Mod - 2);
    return (x1 * bb) % Mod;
}

フェルマーの小定理を用いてModにおける除算を行う。この記事に簡単な解説を載せてある。

連続する数の処理

連番の加算

※2020/4/20 最小値を1固定から引数に変更

static long Total(long n, long m) {
    var c = (n > m) ? n - m : m - n;
    return (n + m) * (c + 1) / 2;
}

n～mの総和をO(1)で求める。小学生向けの算数パズル問題とかでよく出る。

1+2+3+...+1000 = (1+1000)+(2+999)+....+(500+501) = 1001×500

連番の乗算（階乗）

static long Factorial(long n) {
    long ans = 1;
    for (long i = n; i > 0; i--) {
        ans *= i;
    }
    return ans;
}

n!
実装は特に工夫もないループだが、名前がついた算術なので一応。

連番の排他的論理和

static long XorAll(long a, long b) {
    if(a == 0) {
        var c = ((b+1) / 2) % 2;
        return (b % 2 == 0) ? (c ^ b) : c;
    }
    //F(a,b) = F(0,a-1)^F(0,b)
    return XorAll(0, a - 1) ^ XorAll(0, b);
}

a～bまでのすべての数を排他的論理和した結果を求める。XORは二回繰り返すと元に戻るため（0～bの排他的論理和）と（0～a-1の排他的論理）の排他的論理和を取ることで（a～bの排他的論理和）が得られる。0～nの排他的論理和に関しては以下の通り。

0 xor 1 xor 2 xor 3 xor ...
= (0 xor 1) xor (2 xor 3) xor ...
= 1 xor 1 oxr ...
nが偶数のとき：(ペアの個数) % 2 oxr n
nが奇数のとき：(ペアの個数) % 2

確率統計

順列

static long Permutation(long m, long n) {
    long ret = 1;
    for (long i = 0; i < n; i++) {
        ret = (ret) * (m - i);
    }
    return ret;
}

mPn
高校数学で出てくるパーミテーション。m個の集合からn個を選ぶ方法の数で、選んだ順番が異なるものを別々にカウントする。公式の手計算を再現したコード。

mPn = m! / (m-n)! = (m)×(m-1)×...×(m-n+1)

組み合わせ

static long Combination(long m, long n) {
    if (m == n || n == 0) return 1;

    long ans = 1;
    for (long i = 1; i <= n; i++) {
        ans = ans * (m - i + 1) / i;
    }
    return ans;
}

mCn
高校数学で出てくるコンビネーション。m個の集合からn個を選ぶ方法の数で、選んだ順番は区別しない。公式の手計算を再現したコード。

mCn = mPn / n! = (m×(m-1)×...×(m-n+1)) / (n×(n-1)×...×1)

ただしこれは間に割り算が入っているためmodを入れ込めない。それで以下が出てくる。

組み合わせ（Mod）

※2020/2/23 O(m)からO(n)となるように改版
※2020/4/27 ModPow, ModDivを共通化

static long CombinationMod(long m, long n) {
    var a = 1L;
    var b = 1L;
    for(long i=1; i<=n; i++) {
        a = (a * (m - i + 1)) % Mod;
        b = (b * i) % Mod;
    }

    return ModDiv(a, b) % Mod;
}

分子と分母を別々に求めた後に、前述の除算（Mod）を用いて割る。割とよく出る。

素数

素数判定

static bool IsPrimeNumber(long n) {
    if (n <= 3) return true;
    if (n % 2 == 0) return false;

    var r = (long)Math.Sqrt((double)n);
    
    for(int i=3; i<=r; i+=2) {
        if (n % i == 0) return false;
    }
    return true;
}

ある数が素数か否かを判定する。ある数nを因数分解した場合は必ず√n以下の項が存在することから、√n以下の全ての素数で割り切れるかどうかを判定する。素数を列挙することはできないので最低限2の倍数だけ省いている。O(√n)

素因数分解

static List<long> PrimeFact(long n) {
    var list = new List<long>();

    for (long i = 2; i <= Math.Sqrt(n); i++) {
        if (n % i == 0) {
            list.Add(i);
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    if (n > 1) list.Add(n);
    return list;
}

ある数の素因数を列挙する。√nまでの素数を全て判定する。例によって素数を列挙できないので、同時に倍数を取り除いていく。√nより大きい素数は最後に余りとして現れる。O(√n)

素数列挙

static List<int> GetPrimeNumbers(int n) {
    var tbl = new int[n + 1];

    for (int i = 2; i <= Math.Sqrt(n);) {
        if (tbl[i] == 0) {
            var x = i * 2;
            while (x <= n) {
                tbl[x] = 1;
                x += i;
            }
        }
        i += (i < 3 ? 1 : 2);
    }

    var ret = new List<int>();
    ret.Add(2);
    for (int i = 3; i <= n; i += 2) {
        if (tbl[i] == 0) ret.Add(i);
    }

    return ret;
}

n以下の素数をすべて取得する。考え方はエラトステネスの篩だけど、実行効率は改善の余地がありそう。ただ10^7ぐらいまでは許容範囲。

Search

夕立進行会報