clion-live-templates-generator をリリースした

TL;DR

競技プログラミングのライブラリから、CLionのスニペット機能である「ライブラリテンプレート」の設定ファイルを生成してくれるパッケージを公開しました。 github.com

使い方

ローカルで使う

既にライブラリテンプレートを設定している場合は、上書きする前にバックアップを取っておいてください。

$ pip install clion-live-templates-generator
$ lt-generate -d <YOUR_LIBRARY_DIR>
$ cp -i C_C__.xml ~/Library/Application\ Support/JetBrains/CLion2020.1/templates/C_C__.xml

最後の行は、OSによって移動先のフォルダを変えてください。詳細はリポジトリのREADME.mdで確認してください。

Github Actions で自動生成する

Workflow file の一例。

name: CI

on: push

jobs:
  verify:
    runs-on: ubuntu-latest

    steps:
    - uses: actions/checkout@v1

    - name: Set up Python
      uses: actions/setup-python@v1

    - name: Install dependencies
      run: pip3 install -U clion-live-templates-generator
    - name: Create Live-templates file
      run: lt-generate -d lib

    - name: Upload Live-templates file
      uses: actions/upload-artifact@master
      with:
        name: C_C__.xml
        path: C_C__.xml
      if: always()

使ってみた

自分のライブラリで試してみます。

GitHub - habara-k/procon-library: 競技プログラミング用のライブラリ

  • ファイル生成
$ pip install clion-live-templates-generator
$ git clone https://github.com/habara-k/procon-library.git
$ lt-generate -d procon-library
$ cp -i C_C__.xml ~/Library/Application\ Support/JetBrains/CLion2020.1/templates/C_C__.xml
  • CLionを再起動
  • cmd-j

f:id:habara_k:20200719200921p:plain

使えるようになりました。

高速フーリエ変換を図で理解する

問題

(n-1)多項式 f(x) := a_0 + a_1x + \ldots + a _ {n-1}x ^{n-1} について、 x = \zeta_n^ i \ (i = 0, 1, \ldots, n-1) での値を計算したい。

(※ ただし\zeta_n := \exp\left(\frac{2\pi\sqrt{-1}}{n}\right) とおいた。)

愚直に計算するとO(n^ 2)かかるが、これをO(n\log n)で計算する方法を考える。

アルゴリズム

簡単のため、以降 n2の冪乗とする。

(n/2-1)多項式 f_0(x), \ f_1(x) を以下で定義する。

  • f_0(x) := a_0 + a_2x + \ldots + a _ {n-2}x^ {n/2 - 1}
  • f_1(x) := a_1 + a_3x + \ldots + a _ {n-1}x^ {n/2 - 1}

すると、f(x) = f_0(x^ 2) + x \ f_1(x^ 2) が成り立つ。

x = \zeta_n^ i \ (0 \leq i \lt n) での f(x)の値を求めたいので、

0 \leq i \lt n について f_0(\zeta_n^ {2i}), \ f_1(\zeta_n^ {2i})の値が求まっていれば良い。

実は

  • \zeta_n^ {2i} = \zeta_ {n/2}^ i \ \ (0 \leq i \lt n)
  • \zeta _ {n/2}^ i = \zeta _ {n/2}^ {i + n/2} \ \ (0 \leq i \lt n/2)

より、\zeta_n^ {2i} = \zeta _ {n/2}^ {i \ \mathrm{mod} \ n/2} \ \ (0 \leq i \lt n) であることがわかる。

つまり 0 \leq i \lt n/2 について f_0(\zeta _ {n/2}^ i), \ f_1(\zeta _ {n/2}^ i) が求まっていれば良い。

(※ 以下にn=8の場合の図を示す。x = \zeta_n^ {2i} は添字が2づつ進んで2周するため、●における f_0(x), \ f_1(x)の値が求まっていれば良いことがわかる。) f:id:habara_k:20200520234237p:plain

したがって、以下の再帰的な計算で (n-1)多項式 f(x) = \sum_{i=0}^ {n-1} a_i x^ i に対する f(\zeta_n^ i) \ (0 \leq i \lt n) を求めることができる。

  • n = 1のとき、f(x) = a_0 より f(\zeta_1^ 0) = a_0を返す。
  • そうでないとき、

    1. f_0(x) := \sum _ {i=0}^ {n/2-1} a _ {2i} x^ i, \ f_1(x) := \sum _ {i=0}^ {n/2-1} a _ {2i+1} x^ i を定義する。

    2. (n/2-1)多項式 f_0(x), \ f_1(x) に対する f_0(\zeta _ {n/2}^ i), \ f_1(\zeta _ {n/2}^ i) \ \ (0 \leq i \lt n/2) をそれぞれ再帰的に計算する。

    3. 0 \leq i \lt n について f(\zeta_n^ i) = f_0(\zeta _ {n/2}^ {i \ \mathrm{mod} \ (n/2)}) + \zeta _ n^ i \ f_1(\zeta _ {n/2}^ {i \ \mathrm{mod} \ (n/2)}) を計算して返す。

各呼び出しで扱う多項式は、n=8の場合以下の図のようになる。 ただし、f _ {*} から定義した2つの多項式をそれぞれ f _ {0*}, \ f _ {1*} と表記した。 f:id:habara_k:20200520182929p:plain 再帰の終端において、f _ {*}(x) = a _ {*} になっていることがわかる。 次節の実装ではこれを利用している。

計算量はマージソートと同様の解析で O(n\log n)となる (分割統治法)。

実装

using Complex = std::complex<double>;

struct FFT {

    std::vector<Complex> a_;
    int n;

    FFT(const std::vector<Complex>& a) : a_(a), n(1) {
        // n を2の冪乗にする
        while (n < a.size()) n <<= 1;
        a_.resize(n);
    };

    std::vector<Complex> solve() {
        return fft(0, 0);
    }

    std::vector<Complex> fft(int d, int bit) {
        int sz = n >> d;
        if (sz == 1) return {a_[bit]};

        auto f0 = fft(d+1, bit);
        auto f1 = fft(d+1, bit | 1<<d);

        std::vector<Complex> f(sz);

        for (int i = 0; i < sz; ++i) {
            Complex x = std::polar(1.0, 2*M_PI / sz * i);
            f[i] = f0[i % (sz / 2)] + x * f1[i % (sz / 2)];
        }
        return f;
    }
};

参考

http://compro.tsutajiro.com/archive/fft.pdf

C - 高速フーリエ変換

MacBookのJISキーボードをUSに設定する

概要

MacBookのJIS配列のキーボードをUS配列に設定します.

具体的には,

  • 英数入力時, 記号だけUS配列に対応させる.
  • `~ は対応するキーがないので, deleteの一つ左にあるキーに割り当てる.

環境

手順

1. 入力ソースの設定

システム環境設定 -> キーボード -> 入力ソース に移動して,

  • 日本語の平仮名入力以外をOFFにする.

  • オランダを追加する

入力ソースの設定
入力ソースの設定

これで英数入力時だけ, 記号がUS配列になることを確認してください. このままだと `~ が入力できないので次に進みます.

2. Karabiner-Elements を入れる.

Karabiner-Elements をダウンロード・インストールしてください.

3. `~ を割り当てる.

Karabiner-ElementsのSimple modification を開いて,

  • Add item を押す.

  • From key に international3 を, To key に grave_accent_and_tilde (`) を設定する.

キーの割り当て
キーの割り当て

これでdeleteの一つ左のキーに`~ が割りあてられていることを確認すれば完成です.

妥協点

日本語入力のときにもKarabinerのキーマッピングが有効になってしまうので, 全角の \| が打てない.

AtCoder頻出?貼るだけ高速ゼータ・メビウス変換&約数拡張

定義

有限集合 X, (可換な)半群 G について, 写像 f:2^ X\rightarrow G , g:2^ X\rightarrow Gg(S) = \sum_{S \subseteq T} f(T) を満たすときを考える.

(※ g(S) = \sum_{T \subseteq S} f(T) の形をしたものもあるが, \bar{g}(S) := g(2^ X - S)\ , \bar{f}(T) := f(2^ X - T) と定義すれば前者と同じ形になるので割愛する.)

高速ゼータ変換

f から g を求める. O(|X|2^ {|X|})

template<typename T>
vector<T> fast_zeta_transform(const vector<T>& f) {
    int n = f.size();
    vector<T> g = f;
    for (int i = 0; (1 << i) < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (!(j >> i & 1)) {
                g[j] += g[j | (1<<i)];
            }
        }
    }
    return g;
}

例題

atcoder.jp

G := (\mathbb{N},\mathbb{N}),

 (a, b), (c, d) \in G, (a, b) + (c, d) := ((a,b,c,d) の中で一番大きな数, 二番目に大きな数)

と定義する.

f(S) := (A_S, 0)

g(S) := \max \{(A_i, A_j) | i \neq j, i, j \subseteq S \}

と定めると, g(S) = \sum_{T \subseteq S} f(T) が成立する.

包含関係が逆になってることに注意しつつ f から g を求めて, あとは S を1ずつ増やしながら\maxを更新していく.

Submission #11912671 - AtCoder Regular Contest 100

高速メビウス変換

G に逆元があるとき, g から f を求める. O(|X|2^ {|X|})

template<typename T>
vector<T> fast_mobius_transform(const vector<T>& g) {
    int n = g.size();
    vector<T> f = g;
    for (int i = 0; (1 << i) < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (!(j >> i & 1)) {
                f[j] -= f[j | (1<<i)];
            }
        }
    }
    return f;
}

約数に拡張した高速メビウス変換

自然数の集合 M = \{1, 2, \ldots, N\} , (可換な)半群 G について, 写像 f:M \rightarrow G , g:M \rightarrow Gg(d) = \sum_{d | n, n \leq N} f(n) を満たすとき, g から f を求める. O(N\log\log N)

template<typename T>
vector<T> fast_mobius_transform_prime(const vector<T>& g) {
    int n = g.size();
    vector<T> f = g;
    vector<bool> sieve(n, true);
    for (int p = 2; p < n; ++p) {
        if (!sieve[p]) continue;
        for (int i = 1; i * p < n; ++i) {
            sieve[i * p] = false;
            f[i] -= f[i * p];
        }
    }
    return f;
}

例題

atcoder.jp

M := \{1, \ldots , K\}

f(d) := \mathrm{gcd}(A_1, \ldots, A_N)d になる数列の総数

g(d) := \mathrm{gcd}(A_1, \ldots, A_N)d の倍数になる数列の総数

とおくと g(d) = \sum_{d | n, n \leq K} f(n) が成立する. g(d) = \left(\left\lfloor\frac{K}{d}\right\rfloor\right)^ N から f(d) を求めて, \sum_d f(d) \cdot d を計算する.

Submission #11899603 - AtCoder Beginner Contest 162

atcoder.jp

M := \{1, \ldots , \max(A)\}

f(d) := \mathrm{gcd}(A_i, A_j)d になる組の総数

g(d) := \mathrm{gcd}(A_i, A_j)d の倍数になる組の総数

とおくと g(d) = \sum_{d | n, n \leq \max(A)} f(n) が成立する.

C(a) := A_1, \ldots, A_N における a の出現数

を計算しておく.

A_1, \ldots, A_N の中で d の倍数であるものを B_1, \ldots, B_k とおくと


g(d) = \sum_{i < j} B_i B_j = \frac{1}{2} \left\{ \left( \sum_{l=1}^{k}B_l \right)^ 2 - \sum_{l=1}^{k}B_l ^ 2 \right\}

であり, C を用いることで g(d)O(\max(A)\log(\max(A))) で計算できる.

あとは g(d) から f(d) を求めて, \sum_d \frac{f(d)}{d} を計算する.

Submission #11899671 - AtCoder Grand Contest 038

参考

ARC100-E 「Or Plus Max」 (700) 高速ゼータ変換解法 - Mister雑記

高速ゼータ・メビウス変換 - Mister雑記

高速ゼータ変換の約数版 - noshi91のメモ

ゼータ変換・メビウス変換を理解する - Qiita