えびちゃんの日記

えびちゃん（競プロ）の日記です。

ソースコードを見て計算量を下から抑えるのは怪しいという話

競プロ er はよく計算量の見積もりをします。「これこれの計算量は $O(\dots)$ なので十分高速である」といった具合で上から抑えることが多いです。 また、「これこれの計算量は $\Omega(\dots)$ なので TLE しそう」といった具合で下から抑えることもしばしばあります。

note:「これこれの計算量は $O(2^{2^n})$ なので TLE しそう」といった記号の使い方（$O$ で下から抑えようとする）は、不正確な用法なので気をつけましょう。知らずに使っていた人はちゃんと勉強しましょう。

「下から抑える」について

下から抑えるというのは、見積もりたい値はこれ以上であるという値（下界かかい と呼ばれます）を求めるという意味の言い回しです。 ある $a$ を使って $a\le x$ と書けたら「$x$ は $a$ で下から抑えられる」と言います。 逆に、$x\le b$ は「$x$ は $b$ で上から抑えられる」と言います。

「上（下）から抑える」を「上（下）から評価する」と言ったり、それを求めることを「上（下）からの評価」と呼んだりします。

$O$ は定義から上から抑えるための記法（計算量は $O(f(n))$ ですと言ったら、計算量は $f(n)$ のオーダー以下であるということ）なので、下からの評価をしたい文脈とは相性が悪いです。

今日は、ソースコードを見て「この計算量は何々だから TLE するでしょ」という決めつけが必ずしも正しくないですという話をします。「実際に計算量は $\Theta(n^2)$ だけどアクセスの効率がよくて定数倍がめちゃ小さいので AC できる」という話はしません。

!! おまけ (2) が一番びっくりかもしれません。!!

問題提起

さて、次の C++ コードの計算量はどうなるでしょうか。上からも下からもしっかり見積もるべく、$O$ や $\Omega$ ではなく $\Theta$ を使います。

int sum_n(int n) {
    int res = 0;
    for (int i = 0; i <= n; ++i) res += i;
    return res;
}

disclaimer: 最近話題のツイートに起因して書いているものではありません*1。

多くの人は $\Theta(n)$ と思うのではないでしょうか。ループ中で $n+1$ 回の res += i を行いそうなためです（もちろん i <= n や ++i も考慮は必要です）。 実際 GCC では $\Theta(n)$ 時間ですが、Clang では $\Theta(1)$ 時間となります（どちらも -O2 での最適化は前提としています）。

コンパイラがこのような最適化を行ってくれるケースがあるというのを覚えておくべきでしょう。

解説

機械が実際に実行するのは C++ のソースコードではなく機械語ですから、それと対応しているアセンブリを読んでみましょう。これは上記の GCC や Clang が生成したものです。 手元の環境で様々なコンパイラを用意するのは面倒なので、そういうサービスを使います。

godbolt.org

画面左のウィンドウに先ほどのソースコードを入力し、画面上部の設定には下記を指定します（一度に指定できるのは一つずつのみです）。

言語 コンパイラ オプション
C++ x86-64 gcc 13.2 -O2
C++ x86-64 clang 16.0 -O2

画面右のウィンドウで出力のアセンブリが見られるので、これを見ていきましょう。 アセンブリの読み方に関して、説明を丁寧に書こうかと思ったのですが、途中で面倒になったのでやめてしまいました。記事の末尾に参考になりそうなものを挙げておくので各自勉強してください。

ここでは、上記で得られたアセンブリを読める程度の簡単な説明だけをして済ませることにします。

最初の引数が edi と呼ばれるレジスタ*2に入ります。rdi と edi は下位 32 bits を共有していて、rdi は 64 bits、edi は 32 bits です（下図のイメージ）。返り値は eax と呼ばれるレジスタに入れます。

[ ---------------- ---------------- ]  # <- rdi
                   ^^^^^^^^^^^^^^^^    # <- edi

各行は op arg, ... のような形式をしています（; 以降はコメントです。処理系によっては # だったりするようです）。op が命令の名前、arg が引数です。 命令が実行されるたびに、フラグレジスタと呼ばれるレジスタの値が変わったり変わらなかったりします。 フラグレジスタには、計算結果が 0 だったかどうかとか、オーバーフローしたかどうかとか、負だったか（符号ビットが立っているか）どうかとかの情報が入っています。 test x y という命令は x & y を計算します。js .label の命令ではフラグレジスタの状態（たとえば x & y の計算結果による）によって .label と書かれた位置にジャンプしたりしなかったりします。jxx の xx の部分がフラグレジスタのどのフラグを参照するかに対応します。js では SF（符号フラグ、負だったときに true）を見ます。

xor mov add などの命令は名前から想像できるような処理をします。記法にはいくつか流派があるのですが、ここでは計算結果は左側の引数に入ります。 たとえば add eax 2 であれば eax += 2 のようなものに相当します。

lea はおそらく元々はアドレス計算に関する命令なのですが、何かと都合がよい ので、加算や乗算をしたいときにしばしば登場します。どのような計算をしているかについてはコード中のコメントを参照してください。

コメントを添えていきます。関数に渡された時点での引数を n と置いておきます。 まずは GCC です。edi と rdi は、下位 32 bits を共有している（暗黙に同期されている）特殊な変数であるかのようなイメージで読んでください。eax と rax、edx と rdx などについても同様です。

sum(int):                               ; int sum(int edi) {
        test    edi, edi                ;     if ((edi & edi) < 0)
        js      .L4                     ;         goto L4;
        lea     ecx, [rdi+1]            ;     ecx = rdi + 1;
        xor     eax, eax                ;     eax ^= eax;
        xor     edx, edx                ;     edx ^= edx;
        and     edi, 1                  ;     edi &= 1;
        jne     .L3                     ;     if (edi != 0) goto L3;
        mov     eax, 1                  ;     eax = 1;
        cmp     eax, ecx                ;     if (eax == ecx)
        je      .L1                     ;         goto L1;
.L3:                                    ; L3:
        lea     edx, [rdx+1+rax*2]      ;     edx = rdx + 1 + rax*2;
        add     eax, 2                  ;     eax += 2;
        cmp     eax, ecx                ;     if (eax != ecx)
        jne     .L3                     ;         goto L3;
.L1:                                    ; L1:
        mov     eax, edx                ;     eax = edx;
        ret                             ;     return eax;
.L4:                                    ; L4:
        xor     edx, edx                ;     edx ^= edx;
        mov     eax, edx                ;     eax ^= edx;
        ret                             ;     return eax;
                                        ; }

各レジスタで計算しているものの意図を汲んだような名前をつけてコメントを添えると、次のような感じになります。

int sum(int edi) {
    if ((edi & edi) < 0)
        goto L4;  // if (n < 0) goto L4;
    ecx = rdi + 1;  // limit = n + 1;
    eax ^= eax;  // i = 0;
    edx ^= edx;  // res = 0;
    edi &= 1;
    if (edi != 0) goto L3; // if (n % 2 == 1) goto L3;
    eax = 1;  // i = 1;
    if (eax == ecx)
        goto L1;  // if (i == limit) goto L1;
L3:
    edx = rdx + 1 + rax*2;  // res += 1 + 2 * i
    eax += 2;  // i += 2;
    if (eax != ecx)
        goto L3;  // if (i != limit) goto L3;
L1:
    eax = edx;
    return eax;  // return res;
L4:
    edx ^= edx;
    eax ^= edx;
    return eax;  // return res;
}

境界値がややこしいですが、n が偶数なら (1+2)+(3+4)+...、奇数なら 1+(2+3)+(4+5)+... のように隣り合う要素をまとめて足していくような最適化をしています。 とはいえ、計算量は $\Theta(n)$ です。

次は Clang です。

sum(int):                               ; int sum(int edi) {
        mov     eax, edi                ;     eax = edi;
        lea     ecx, [rdi - 1]          ;     ecx = rdi - 1;
        imul    rcx, rax                ;     rcx *= rax;
        shr     rcx                     ;     rcx >>= 1;
        add     ecx, edi                ;     ecx += edi;
        xor     eax, eax                ;     eax ^= eax;
        test    edi, edi                ;     if ((edi & edi) >= 0)
        cmovns  eax, ecx                ;         eax = ecx;
        ret                             ;     return eax;
                                        ; }

こちらも意図を汲むと次のような感じです。

int sum(int edi) {
    eax = edi;  // tmp = n;
    ecx = rdi - 1;  // sum = n - 1; 
    rcx *= rax;  // sum *= tmp; // i.e. sum *= n
    rcx >>= 1;  // sum /= 2;  // sum == n * (n - 1) / 2;
    ecx += edi;  // sum += n;  // sum == n * (n + 1) / 2;
    eax ^= eax;  // res = 0;
    if ((edi & edi) >= 0)
        eax = ecx;  // if (n >= 0) res = sum;
    return eax;  // return res;
}

$n\ge 0\implies \sum_{i=0}^n i = n(n+1)/2$ を用いて $\Theta(1)$ の処理に最適化されています。

おまけ

Rust でもいろいろ遊べるので遊んでみます。

pub fn sum(n: u32) -> u32 {
    (0..=n).sum()
}

pub fn sum_128(n: u128) -> u128 {
    (0..=n).sum()
}

上記の関数を見てみます。pub にする必要があることに注意してください。つけ忘れると

<No assembly to display (~5 lines filtered)>

のような表示が出ます。オプションは -C opt-level=3 などにしておきます。

次のような感じです。適宜読んでください。

example::sum:                           ; fn sum(edi: u32) -> u32 {
        test    edi, edi                ;     if edi & edi == 0 {
        je      .LBB0_1                 ;         goto 'LBB0_1; }
        lea     eax, [rdi - 1]          ;     eax = rdi - 1;
        lea     ecx, [rdi - 2]          ;     ecx = rdi - 2;
        imul    rcx, rax                ;     rcx *= rax;
        shr     rcx                     ;     rcx >>= 1;  // (n - 1) * (n - 2) / 2
        lea     eax, [rdi + rcx]        ;     eax = rdi + rcx;
        dec     eax                     ;     eax -= 1;
        add     eax, edi                ;     eax += edi;  // (n - 1) * (n - 2) / 2 + n - 1 + n
        ret                             ;     return eax;  // == (n - 1) * n / 2 + n == (n + 1) * n / 2
.LBB0_1:                                ; 'LBB0_1:
        xor     eax, eax                ;     eax ^= eax;
        add     eax, edi                ;     eax += edi;
        ret                             ;     return eax;  // 0
                                        ; }

128-bit 整数の方は長いですが、128-bit 整数同士の演算自体にいくつかの命令が使われているだけで、やりたいこととしては大差ないでしょう。実はちゃんと読んでいません。

example::sum_128:                       ; fn sum_128(rdi:rsi: u128) -> u128 {
        mov     rax, rdi                ;     rax = rdi;
        or      rax, rsi                ;     rax |= rsi;
        je      .LBB2_1                 ;     if rax == 0 { goto 'LBB2_1; }
        push    r14                     ;     tmp_r14 = r14;
        push    rbx                     ;     tmp_rbx = rbx;
        mov     r8, rdi                 ;     r8 = rdi;
        add     r8, -1                  ;     (add, carry) = r8.carrying_add(18446744073709551615);
                                        ;     r8 = add;
        mov     r9, rsi                 ;     r9 = rsi;
        adc     r9, -1                  ;     r9 += 18446744073709551615 + carry 
        mov     rbx, rdi                ;     rbx = rdi;
        add     rbx, -2                 ;     (add, carry) = rbx.carrying_add(18446744073709551614);
                                        ;     rbx = add;
        mov     rcx, rsi                ;     rcx = rsi;
        adc     rcx, -1                 ;     rcx += 18446744073709551615 + carry;
        mov     rax, r9                 ;     rax = r9;
        mul     rbx                     ;     rax *= rbx;
        mov     r10, rdx                ;     r10 = rdx;
        mov     r11, rax                ;     r11 = rax;
        mov     rax, r8                 ;     rax = r8;
        mul     rbx                     ;     rax *= rbx;
        mov     rbx, rax                ;     rbx = rax;
        mov     r14, rdx                ;     r14 = rdx;
        add     r14, r11                ;     (add, carry) = r14.carrying_add(r11);
                                        ;     r14 = add;
        adc     r10d, 0                 ;     r10 += 0 + carry;
        mov     rax, r8                 ;     rax = r8;
        mul     rcx                     ;     rax *= rcx;
        add     rax, r14                ;     (add, carry) = rax .carrying_add(r14);
                                        ;     rax += carry;
        adc     edx, r10d               ;     edx += r10d + carry;
        imul    ecx, r9d                ;     ecx *= r9d;
        add     ecx, edx                ;     ecx += edx;
        shld    rcx, rax, 63            ;     rcx:rax >>= 63;
        shld    rax, rbx, 63            ;     rax:rbx >>= 63;
        add     rax, r8                 ;     (add, carry) = rax.carrying_add(r8);
                                        ; rax = add;
        adc     rcx, r9                 ;     rcx += r9 + carry;
        pop     rbx                     ;     rbx = tmp_rbx;
        pop     r14                     ;     r14 = tmp_r14;
        add     rax, rdi                ;     (add, carry) = rax.carrying_add(rdi);
                                        ;     rax = add;
        adc     rcx, rsi                ;     rcx += rsi + carry;
        mov     rdx, rcx                ;     rdx = rcx;
        ret                             ;     return rax:rdx;
.LBB2_1:                                ; 'LBB2_1:
        xor     eax, eax                ;     eax ^= eax;
        xor     ecx, ecx                ;     ecx ^= ecx;
        add     rax, rdi                ;     (add, carry) = rax.carrying_add(rdi);
                                        ;     rax = add;
        adc     rcx, rsi                ;     rcx += rsi + carry;
        mov     rdx, rcx                ;     rdx = rcx;
        ret                             ;     rax
                                        ; }

pub fn sum_3(n: u32) -> u32 { (0..=n).step_by(3).sum() } のようなものは $\Theta(1)$ にはなってくれませんでした。

おまけ (2)

たぶんここすごいです。

int square_sum(int n) {
    int res = 0;
    for (int i = 0; i <= n; ++i) res += i * i;
    return res;
}

これを Clang にやってもらいます。

square_sum(int):
        test    edi, edi
        js      .LBB0_1
        mov     eax, edi
        lea     ecx, [rdi - 1]
        imul    rcx, rax
        lea     eax, [rdi - 2]
        imul    rax, rcx
        shr     rax
        imul    edx, eax, 1431655766
        shr     rcx
        lea     eax, [rcx + 2*rcx]
        add     eax, edi
        add     eax, edx
        ret
.LBB0_1:
        xor     eax, eax
        ret

慣れていない人は 1431655766 ってな〜んだ？となりそうです。 ちゃんと C++ でコンパイルの通る形で書くと次のようなものになりそうです。

int square_sum(int n) {
  if (n < 0)
    goto LBB0_1;

  {
    unsigned edi = n;
    unsigned eax = edi;
    unsigned ecx = edi - 1;
    unsigned long rcx = (long)ecx * (long)eax;
    eax = edi - 2;
    ecx = rcx;
    unsigned long rax = (long)eax * (long)ecx;
    rax >>= 1;
    eax = rax;
    unsigned edx = eax * 1431655766u;
    rcx >>= 1;
    eax = 3 * rcx;
    eax += edi;
    eax += edx;
    return eax;
  }

LBB0_1:
  return 0;
}

int main() {
  for (int i = -10; i <= 10; ++i) {
    printf("%d%c", square_sum(i), i < 10 ? ' ' : '\n');
  }
  // 0 0 0 0 0 0 0 0 0 0 0 1 5 14 30 55 91 140 204 285 385
}

諸々を整理すると、考えるべきパートは概ね次のような感じです。

    unsigned edx = n * (n - 1) * (n - 2) / 2 * 1431655766u;
    unsigned ecx = n * (n - 1) / 2;
    return 3 * ecx + edx + n;

hint: 1431655766 == 0x55555556.

いくつか例を見てみましょう。32-bit 符号なし整数で考えて、オーバーフローは wrapping（$2^{32}$ を法として考える）とします。

>>> (8000 * 1431655766) % (2**32)
2863316864
>>> (8001 * 1431655766) % (2**32)
5334
>>> (8002 * 1431655766) % (2**32)
1431661100

大胆予想です。 $$ x\equiv 0\pmod{3} \implies (x\times 1431655766)\bmod 2^{32} = \tfrac23 x. $$

種明かしというかなんというか、$1431655766 = (2^{32} + 2)/3$ です。 なので、$x = 3y$ とすると下記のようにできます。 $$ \begin{aligned} 3y\times ((2^{32} + 2)/3) &= y\times (2^{32}+2) \\\ &\equiv y\times 2 = 2y \pmod{2^{32}}. \end{aligned} $$ なるほど〜という感じです。

さて、これを踏まえて計算すれば、$\tfrac16 n(n+1)(2n+1)$ を求めていることがわかるでしょう（$n(n-1)(n-2)/2$ は $3$ の倍数であることに注意）。 計算途中の各値は、必要に応じて 64-bit 整数を使いつつ求めているので、オーバーフローがあった場合も $\tfrac16 n(n+1)(2n+1)\bmod 2^{32}$ になっていそうです。

ところで、適切な範囲において、$\floor{(x\times 1431655766)/2^{32}} = \floor{x/3}$ のような話もありそうです。 $n$ を $2^{32}$ で割った整数部分というのは、n >> 32 だったり上位 dword を持ってきたりすることで高速に計算できますから、除算の高速化に貢献しそうです（実際、コンパイラはそうした類の最適化をしてくれます）。

おあそび

アセンブリを自分で書いて試せる状態になっているとお勉強が捗ると思うので、そういうことをしましょう。

↓ foo.s ↓

        .intel_syntax
        .file "foo.s"
        .text
        .globl foo
        .type foo, @function
foo:
        mov     %eax, %edi
        imul    %eax, %eax
        add     %eax, 2
        ret
        .section .note.GNU-stack,"",@progbits

↓ main.c ↓

#include <stdio.h>

int foo(int);

int main(void) {
    printf("%d\n", foo(5));
}

↓ コンパイル・実行 ↓

% as -o foo.o foo.s
% gcc foo.o main.c -o main
% ./main

あるいは、適当なプログラム prog.c を書いて gcc -S prog.c などをすると prog.s が得られるので、それを読むのもよいかもしれません。

また、M2 Mac などを使っている人は上記のアセンブリでは動かなさそう（怒られました）なので、別途考える必要があります。命令セットとかレジスタの名前とかが違いそうです。

↓ foo.s ↓

        .file   "foo.s"
        .text
        .global _foo
_foo:
        mov     w0, w0
        mul     w0, w0, w0
        add     w0, w0, #2
        ret
        .align  8

また、下記のようなことをすると楽しい気持ちになる人もいるかもしれません。

% objdump -D foo.o

関連資料

例によって日本語の資料はあまり探していません。よしなにしてくれたらうれしいです。

あわせて読みたい

読みたいかどうかは人によるというのはそう。

あとがき

込み入った解説を書かないとあっさりめな記事になるなあという気持ちです。アセンブリに関してなんかいろいろ書こうとしたんですが、「書いて誰が幸せになるんだろう」「各々が調べてくれたらいいや」という気分になって消してしまいました。文献は挙げたので意欲や興味がある人はがんばってほしいです。

それから、コンパイラがオーダーを落としてくれるようなケースは基本的には稀という気がしています。ただ稀だからといって無視していると足を掬われそうです。 未定義動作を利用されて、やばい最適化が起きて定数時間の処理になっていることはしばしばある気もします。

定数による除算なんかは（除算命令は重いので）除算を使わない形に書き換える最適化をしてくれがちです。こうした話に関してもアセンブリを読めると学習が捗るような気がします。

Clang が $\sum_{i=0}^n i^2$ についてもループなしにしてくれた上、除算の部分をよい感じに最適化してくれたので面白かったです。 $\floor{n/3}$ のようなタイプの最適化は知っていたのですが、$\tfrac23 n$ のようなタイプは知らなかったので勉強になりました。 さらに大きい $k$ に対して $\sum_{i=0}^n i^k$ を見てみても面白いかもしれませんね。

おわり

おわりです。

*1:こんな例は 5000 年前から 3 万回は見てきたため。実際、元々 3 週間くらい前に下書きをしていた記事です。

*2:レジスタのことは、edi や ecx など名前のついたメモリだと思ってもらえばいいと思います。どのようなレジスタがあるかは、関連資料に挙げたものを読んでもらえるとよさそうです。

各種 DP を愚直な形で考えてみる

ボリューム大きめ

先日、下記の記事でナップサック問題の DP を愚直に眺めました。

rsk0315.hatenablog.com

今回は、ナップサック問題に限らず様々な DP を愚直に眺める回です。 「○○（何らかの集合）の最大値」のように計算せず、○○の部分について考えていきます。 もちろん DP をする際に○○をそのまま持つと空間計算量がめちゃくちゃになる（ことに伴って時間計算量もめちゃくちゃになる）のですが、典型 DP で暗に構築されている集合を考えておくことで、そうした構造を持つ DP を考える際に理解がスムーズになる気がします。 「何々を全パターン考慮したい」となったときに「こういう漸化式を考えればよいはず」とできるレパートリーが増えそうです。

想定読者は競プロをしていて DP を学び中・苦戦中〜ある程度知っている人で、ある程度数式を読める人です。数式が苦手な人は、数式が得意な人に助けてもらうなどをしてもらえると助かります。具体例も交えつつ説明しているので雰囲気はわかってもらえるかもしれません？ とはいえ目で読むだけではわからない部分もあると思うので、手を動かしつつ考えてもらえるとうれしい気がします。

軽い気持ちで書き始めたところ過去一のボリュームになってしまって困惑しています。 各テーマは概ね難易度順で並んでいる気がしますが、あまり順序にこだわらず気になるところを読みたいときに読んでもらえればよさそうです。

導入

$\gdef\DP{\operatorname{dp}}$ 何らかの集合 $\mathcal{S}$ に対して $\bigodot_{S\in\mathcal{S}} f(S)$ を計算したい問題があったとします。 このような問題で DP を行う場合、$\mathcal{S}$ を構築する漸化式をそのまま DP に流用できることがしばしばあります。 そのため、$\mathcal{S}$ に関する漸化式を考えておくことが有用です。

ここで、$\mathcal{S}$ は一般には空間計算量がかさむもの（部分文字列や部分集合など）の集合で、$f$ はその要素を空間計算量のかさまないもの（整数や boolean など）に写す関数、$\bigodot$ は $f$ で写されたものたちを合わせる操作（$\min$ や $\sum$ など）です。個人的には $f$ を projection (project)、$\bigodot$ を folding (fold) と呼んでいます。

また、下記で挙げるような $\mathcal{S}$ に対して、「$\mathcal{S}$ の各要素を条件 $P$ を満たすかどうかで分類する」「$\mathcal{S}$ の各要素 $S$ を関数 $f(S)$ の値で分類する」などを考慮することで、条件の増えた DP を考えることが可能です。

先日の記事では配る・もらうに関して考えましたが、ここでは数式との相性がよい方法で考えたいので、基本的にはもらう形式での漸化式になっています。とはいえ、適切に考察することで実装上は配る形式にもできるテーマが多めになっています。

rsk0315.hatenablog.com

定義や記法など

おことわり：集合 (set) や列 (sequence)、順列 (permutation) や分割 (partition) や経路 (path) など、頭文字が共通の対象が複数出てきますが、それらごとに別々の文字を使おうとすると逆に混乱しそうでした。各節ごとにスコープが切られているとして、型を明示しつつ $S$ や $P$ などの文字を使うことにします。

$S\cap T=\emptyset$ を満たす集合 $S$ と $T$ に対して、$S\sqcup T=S\cup T$ とします。 たとえば、漸化式を立てる際などに $S_i = S_{i-1}\sqcup S_{i-2}$ のように書き、$S_{i-1}$ と $S_{i-2}$ に重複する要素がないことを示すのに使ったりします。 実際には $S_{i-1}\cap S_{i-2}=\emptyset$ であることを示す必要がありますが、適宜省略します。 $\sum_{x\in S\sqcup T} f(x) = \sum_{x\in S} f(x) + \sum_{x\in T} f(x)$ などが成り立って便利なので、$\cup$ ではなく $\sqcup$ で考えておいた方が使い勝手がよいことが多そうです。

文字集合 $\Sigma$ に対して、$\Sigma$ の要素を（重複してもよく）順に $n$ 個並べたもの $(\sigma_0, \sigma_1, \dots \sigma_{n-1})$ を $\Sigma$ 上の長さ $n$ の列 (sequence over $\Sigma$ of length $n$) といい、これら全体の集合を $\Sigma^n$ と書きます*1。$\Sigma^0 = \{\varepsilon\}$ となる $\varepsilon$ を空列 ((the) empty sequence) と呼びます*2。 曖昧さがないときは $(\sigma_0, \sigma_1, \dots, \sigma_{n-1})$ の代わりに $\sigma_0\sigma_1\dots\sigma_{n-1}$ とも書きます。

また、$\Sigma$ 上の列全体の集合 $\Sigma^\star$ を $$\Sigma^\star \triangleq \Sigma^0 \sqcup \Sigma^1 \sqcup \dots \sqcup \Sigma^n \sqcup \dots $$ で定義します。$\Sigma^\star$ は無限集合ですが、$n$ を固定した $\Sigma^n$ は（$\Sigma$ が有限の前提であれば）有限集合であることに注意しましょう。 $S$ の長さを $|S|$ と書きます。$S\in\Sigma^n$ のとき $|S|=n$ です。

列 $S$ と $T$ を（この順に）連結させたものを $S\concat T$ と書くことにします*3。$|S\concat T| = |S|+|T|$ となります。

長さ $n$ の列 $S = (S_0, \dots, S_{n-1})$ と大きさ $k$ の非負整数の集合 $I=\{i_0, i_1, \dots, i_{k-1}\}$ ($i_0\lt i_1\lt\dots\lt i_{k-1}\lt n$) に対して、$S_I$ を長さ $k$ の列 $(S_{i_0}, S_{i_1}, \dots, S_{i_{k-1}})$ とします。特に、$S_{\emptyset} = \varepsilon$ です。

列 $P$ が集合 $S$ の順列 (permutation of $S$) であるとは、$|P| = |S|$ かつ、任意の $x\in S$ に対して $x$ が $P$ にちょうど一度現れることを言います。 集合 $S$ の順列全体の集合を $S!$ と書くことにします*4。$S!\subseteq S^{|S|}$ です。 たとえば $$ \begin{aligned} \{0, 1, 2\}! &= \{(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)\}, \\ \emptyset! &= \{\}! = \{()\} = \{\varepsilon\} \end{aligned} $$ です。$|\varepsilon| = |\emptyset| = 0$ であり、$\emptyset$ の任意の要素がちょうど一度現れている (vacuously true) ことに注意しましょう。

簡潔さのため、場合分けで定義する際に $$ \begin{aligned} \DP[\angled{i, 0}] &= x, \\ \DP[\angled{0, j}] &= y, \\ \DP[\angled{i, j}] &= z \end{aligned} $$ のように $i$ や $j$ の条件を明示せずに行います。 よくあるプログラミング言語のパターンマッチのように上から順に適用されるとし、たとえば次の略記であると解釈されたいです。 $$ \DP[\angled{i, j}] = \begin{cases} x, & \text{if }j = 0; \\ y, & \text{if }j \ne 0 \wedge i = 0; \\ z, & \text{if }j \ne 0 \wedge i \ne 0. \end{cases} $$

その他、各トピックにおける限定的な定義に関しては、該当箇所で個別に記すことにします。

集合の記法に関して

いろいろ出てくるので書いておきます。

内包的記法においては、概ね次のような気持ちで記述しています（厳密に守られていることを保証するものではないです）。

記法 きもち
$\{x\in S\mid P(x)\}$ s.filter(p)
$\{f(x)\mid x\in S\}$ s.map(f)
$\{f(x)\mid x\in S, P(x)\}$ s.filter(p).map(f)

ここで .filter(p) は p を満たすものに絞る操作で、.map(f) は各要素に f を適用する操作です。 $x, x'\in S$ ($x\ne x'$) に対して $f(x) \ne f(x')$ と限らない場合、$\{f(x)\mid x\in S\}$ の要素数が $S$ より減りうることには注意しましょう（ここではあまりそういう例は出ないですが）。

複数の集合の $\sqcup$ を考えるときの記法です。 $$ \bigsqcup_{i=0}^{n-1} S_i = S_0\sqcup S_1 \sqcup \dots \sqcup S_{n-1} $$ です。下記では集合の集合などを考えたりするので、ややこしくなりますが落ちついて考えましょう。 $$ \begin{aligned} \bigsqcup_{i=0}^{n-1} {\{S_i\}} &= \{S_0\}\sqcup \{S_1\} \sqcup \dots \sqcup \{S_{n-1}\} \\ &= \{S_0, S_1, \dots, S_{n-1}\} \\ &= \{S_i\mid i\in\{0, 1, \dots, n-1\}\}. \end{aligned} $$

集合 $S = \{a_0, \dots, a_{n-1}\}$ に新しく要素 $a_n$ を加えた集合を考えたいときは、$S\sqcup \{a_n\}$ のように書きます。

$S$ の部分集合 $T$ を考えたいとき、「$T\subseteq S$ を考える」ではなく「$T\in 2^S$ を考える」のような記法を使うことが多いです。集合から選んでくることを意識しようとしてこういう書き方をしていますが、意味合いとしては同じです。

肩慣らし

一般的に使えるような構造の話をする前に、単純な DP を考えてみましょう。愚直に考える練習です。

Fibonacci 数列

列 $S=(S_0, S_1, \dots, S_{|S|-1})$ に対して、簡潔さのため $\sum S = \sum_{i=0}^{|S|-1} S_i$ と定義しておきます。

$\Sigma = \{1, 2\}$ 上の列を考え、$S\in\Sigma^{\star}$ であって $\sum S = k$ なるもの全体からなる集合を $\Phi_k$ とおきます。 小さい方から挙げると次のようになります。 $$ \begin{aligned} \Phi_0 &= \{\varepsilon\}, \\ \Phi_1 &= \{(1)\}, \\ \Phi_2 &= \{(1, 1), (2)\}, \\ \Phi_3 &= \{(1, 1, 1), (1, 2), (2, 1)\}, \\ \Phi_4 &= \{(1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2)\}. \end{aligned} $$

$n\gt 0$ のとき、先頭の要素が $1$ か $2$ かで分類することができ、 $$ \Phi_n = \{(1)\concat\phi\mid\phi\in\Phi_{n-1}\}\sqcup\{(2)\concat\phi\mid\phi\in\Phi_{n-2}\} $$ と書くことができます。両辺の要素数を考えれば $|\Phi_n| = |\Phi_{n-1}| + |\Phi_{n-2}|$ となりますね。

Fibonacci 数列を $(1, 1, 2, 3, 5, \dots)$ とだけ考えるよりも、「$3$ と言っているのは $\{(1, 1, 1), (1, 2), (2, 1)\}$ に対応しているんだ」と思える方がイメージの幅が広がるのではないでしょうか。もちろん、イメージの仕方は他にもいろいろあるとは思います。

さて、陽に列を書き出してみると、「$\Phi_n$ に含まれる列の長さの合計はいくつ？」のような疑問も自然に湧いてくるのではないでしょうか。ちょっとやってみましょう。 $$ \begin{aligned} \sum_{\phi\in\Phi_n} |\phi| &= \sum_{\phi\in\Phi_{n-1}} |(1)\concat\phi| + \sum_{\phi\in\Phi_{n-2}} |(2)\concat\phi| \\ &= \sum_{\phi\in\Phi_{n-1}} (1 + |\phi|) + \sum_{\phi\in\Phi_{n-2}} (1 + |\phi|) \\ &= \sum_{\phi\in\Phi_{n-1}} 1 + \sum_{\phi\in\Phi_{n-1}} |\phi| + \sum_{\phi\in\Phi_{n-2}} 1 + \sum_{\phi\in\Phi_{n-2}} |\phi| \\ &= |\Phi_{n-1}| + \sum_{\phi\in\Phi_{n-1}} |\phi| + |\Phi_{n-2}| + \sum_{\phi\in\Phi_{n-2}} |\phi| \end{aligned} $$ 漸化式が立ったので $|\Phi_n|$ の方と合わせて計算することができますね。$(0, 1, 3, 7, 15, 30, 58, \dots)$ と続くようです。

別の解法（おまけ）

形式的冪級数を考えます。 $$ A(x, y) = \sum_{S\in\{1, 2\}^{\star}} x^{\sum S}y^{|S|} $$ とおくと、 $$ \begin{aligned} A(x, y) &= x^{\sum \varepsilon}y^{|\varepsilon|} + \sum_{S\in\{1, 2\}^{\star}} x^{\sum (1)\concat S}y^{|(1)\concat S|} + \sum_{S\in\{1, 2\}^{\star}} x^{\sum (2)\concat S}y^{|(2)\concat S|} \\ &= x^0y^0 + \sum_{S\in\{1, 2\}^{\star}} x^{1 + \sum S}y^{1+|S|} + \sum_{S\in\{1, 2\}^{\star}} x^{2 + \sum S}y^{1+|S|} \\ &= 1 + xy\cdot A(x, y) + x^2 y\cdot A(x, y) \\ &= (1-xy-x^2 y)^{-1} \end{aligned} $$ です。求めたいものは $$ [x^k] \frac{\partial}{\partial y} A(x, 1) = [x^k] \sum_{S\in\{1, 2\}^{\star}} x^{\sum S} \cdot |S|\,1^{|S|-1} $$ なので、 $$ \frac{\partial}{\partial y} A(x, 1) = \frac{x+x^2}{(1-x-x^2)^2} $$ を用いて計算すればよいでしょう。

典型的な構造

下記では、$n$ 未満の非負整数全体からなる集合をよく考えます。そこで $\Lambda_n = \{0, 1, \dots, n-1\}$ とおいておきます。 特に $\Lambda_0 = \{\} = \emptyset$ です。

$\Lambda_n$ から作られるいろいろな構造を考えていきます。 難しそうな場合でも闇雲に漸化式を立てようとするのではなく、まずは構造について考えたり、DP の定義を決めるところから始めましょう。

部分集合

$\Lambda_n$ に対して $2^{\Lambda_n}$ を得る方法を考えてみましょう。

簡単に思いつくものとして、 $$\DP[i] = 2^{\Lambda_i}$$ として、次の漸化式を立てられそうです。 $$ \begin{aligned} \DP[0] &= \{\emptyset\}, \\ \DP[i] &= \big\{S\sqcup\{\}\mid S\in\DP[i-1]\big\} \sqcup \big\{S\sqcup\{i-1\}\mid S\in\DP[i-1]\big\} \\ &= \DP[i-1] \sqcup \big\{S\sqcup\{i-1\}\mid S\in\DP[i-1]\big\} \end{aligned} $$ があります。

二項係数の文脈で、$(1+x)(1+x)(1+x)\cdots$ を展開しようとして順に $( (1+x)\cdot 1 + (1+x)\cdot x)(1+x)\cdots$ とするのと似ていそうです。

$\mathcal{S} = \DP[i]$ の各要素（であるところの集合）$S$ を $\sum_{i\in S} w_i$ ごとに分類して、$f(S) = \sum_{i\in S} v_i$、$\bigodot = \max$ とすることで、ナップサック問題の DP になります。 あるいは、$f(S) = 1$、$\bigodot = \sum$ とすることで、部分和問題の数え上げの DP になります。

ここでは簡単のため $\{0, 1, \dots, n-1\}$ について考えましたが、状況に応じて $\{\sigma_0, \sigma_1, \dots, \sigma_{n-1}\}$ を考えた方がよいケースもあるでしょう。状況に応じて適切にやってください。以下の構造についても同じです。

また、集合を考える代わりに、適当な順で固定した列を考えていると見なすこともできそうです。$S$ の代わりに $x\in S!$ なるいずれかの $x$ を考えているということです。

順列 (exponential)

$\Lambda_n$ に対して $\Lambda_n!$ を得る方法を考えてみましょう。

$T\subseteq S$ に対して $\DP[T] = T!$ とすることで次のような漸化式を立てられそうです。 $$ \begin{aligned} \DP[\emptyset] &= \{\varepsilon\}, \\ \DP[T] &= \bigsqcup_{x\in T} \big\{P \concat (x) \mid P\in \DP[T\smallsetminus\{x\}]\big\}. \end{aligned} $$ 気持ちとしては、「集合 $T$ の順列全体を考えたい。まず末尾に来る要素 $x\in T$ を固定する。列の末尾を取り除いたものは $T\smallsetminus\{x\}$ の順列である。$T\smallsetminus\{x\}$ の順列全体の集合というのは、いま考えたい問題と同様の形式であり、より自明なケースになっている」という感じです。 実際には、漏れや重複がないことを示す必要がありそうです。

任意の $T\subseteq S$ について $\DP[T]$ を考えるので、$\DP$ の添字の個数としては $2^{|S|}$ になります。$2^{|S|} = o(|S|!)$ であることに一応注意しておきましょう。

実装する上では、$\DP[T]$ の部分について少し考慮する必要があります。 素朴には連想配列を用いることになりそうですが、要素数が $2^{|S|}$ かつ比較に最悪 $\Theta(|S|)$ 時間かかることから、 $$\Theta(2^{|S|}\log(2^{|S|})\cdot |S|) = \Theta(|S|^2\, 2^{|S|})$$ 程度の時間を使ってしまいそうです*5。今々は $T!$ の各要素を陽に持っているので、それにかかる時間・空間の方が膨大ではあるのですが、project・fold した場合は各要素のコストが無視できるため、こちらが無視できなくなってしまいます。

よくある実装として、集合を整数にエンコードする方法があり、bit DP などと呼ばれています。 $$\angled{T} = \sum_{x\in T} 2^x$$ で定義します。たとえば $\angled{\emptyset} = 0$、$\angled{\{0, 1, 3\}} = 2^0+2^1+2^3=11$ です。 $\DP[\angled{T}]$ が $O(1)$ 時間でアクセスできるようになる上、連想配列のときのように $T$ を陽に持つ必要がなくなるため、空間も全体で $O(2^{|S|})$ words になります。

ここは気になる読者向けです。 「$|S|$ が大きくなったら多倍長整数が必要になるのでは？」という風なことを言う人がいるかもしれませんが、そもそも $2^{64}$ 個のエントリを埋めるの自体が（時間的に）現実的でないため、そうした心配は不要そうです。あるいは、時間は適当に解決することにして $2^{1024}$ 個のエントリを埋めることになったとします。こうなったとき、メモリ空間上の $2^{1024}$ 個の位置にランダムアクセスできる必要があるため、word 一つあたりのビット数も $1024$ 程度は最低限必要になります。そういうわけで、「集合サイズが大きくなるなら多倍長整数が必要になる」というのは必ずしも「そうですね」とは言えないです。ランダムアクセスの要件がなければ word の下限を保証できないので困りますが、考えている計算モデルによるわけですね。詳しくは transdichotomous model とか word RAM とかで調べるとよさそうです。

さて、よくある例としては巡回セールスマン問題などがあります。 順列 $P$ のコストを $f(P)$、辺 $(u, v)$ の重みを $w(u, v)$ とすると、 $$ f(P' \concat (u, v)) = f(P'\concat(u)) + w(u, v) $$ のように計算できるため、$P$ の末尾の要素で分類することで漸化式を立てられます。 末尾の要素を明示するため、先の漸化式で $P$ としていた部分を $P'\concat(u)$ のようにしています。実装上は $\DP[\angled{T}][v]$ のようなイメージでしょうか。 $\varepsilon = P'\concat(u)$ となるような $P'$ は存在しないので、ベースケースには注意が必要です。

組合せ

集合 $S$ の部分集合のうち要素数が $k$ のものを $(S)_k$ と書くことにします。$|(S)_k| = \binom{|S|}{k}$ に由来する記法です（他ではあまり見ない気がします）。さて、数式で書けば次の通りです。 $$ (S)_k = \{x\in 2^S\mid |x| = k\}. $$

さて、$(\Lambda_n)_k$ について漸化式を考えます。 $$ \begin{aligned} (\Lambda_n)_0 &= \{\emptyset\}, \\ (\Lambda_0)_k &= \emptyset, \\ % (\Lambda_n)_k &= \big( (\Lambda_{n-1})_{k-1}\sqcup\{k-1\}\big)\sqcup(\Lambda_{n-1})_k. (\Lambda_n)_k &= \big( \{T\sqcup\{n-1\}\mid T\in(\Lambda_{n-1})_{k-1}\}\big)\sqcup(\Lambda_{n-1})_k. \end{aligned} $$

いわゆる Pascal の三角形の漸化式に相当します。 $n$ が小さいときは bit DP でもできます。bit DP の基礎練習としてやってみるのもよいでしょう。

また、$\bigsqcup_{k=0}^n (\Lambda_n)_k = 2^{\Lambda_n}$ となるので、部分集合に関する何らかの DP にも使えるかもしれません。

部分列 (1)

$\Sigma$ 上の長さ $n$ の列 $S\in\Sigma^n$ が与えられます。

$S$ の部分列全体の集合 $\gdef\subseq#1{\mathop{\operatorname{subseq}} #1}$ $$ % \subseq{S} = \bigcup \big\{S_I \mid I\in 2^{\Lambda_n}\big\} \subseq{S} = \bigcup_{I\in 2^{\Lambda_n}} \{S_I\} = \{S_I \mid I\in 2^{\Lambda_n}\} $$ を考えます。$\subseq{\varepsilon} = \{\varepsilon\}$ です。

なお、$\bigsqcup$ ではなく $\bigcup$ であることに注意しましょう。 たとえば $\Sigma=\{\mathtt{a}, \mathtt{b}\}$ 上の列 $S = \mathtt{aab}$ に対して $S_{\{0, 2\}} = S_{\{1, 2\}} = \mathtt{ab}$ となります。 $$ \subseq{\mathtt{aab}} = \{\varepsilon, \mathtt{a}, \mathtt{aa}, \mathtt{aab}, \mathtt{ab}, \mathtt{b}\} $$ です。（こうした理由から、部分集合全体の集合のときとは違って $2^S$ のような記法は適さなさそうです。）

そこで、$S_I = S_J$ となるような $I$, $J$ は、これから定める順序 $\preceq$ で最小のものについてのみ考えることにしてみます。 すなわち、任意の $J\ne I$ に対して $I\preceq J$ となるような $I$ を考えるということです。気持ちとしては、“辞書順最小” 的なものを集合に対して考えたいです。 $$ % I\preceq J \stackrel{\vartriangle}{\iff} I = J \vee \min\, (I\smallsetminus J) \lt \min\, (J\smallsetminus I) I\preceq J \stackrel{\vartriangle}{\iff} (I\smallsetminus J) = \emptyset \vee \min\, (I\smallsetminus J) \lt \min\, (J\smallsetminus I). $$ ただし、$\min\emptyset = \infty$ としておきます。

部分列を列挙する代わりに、“辞書順最小” の添字の方を列挙することにします。$\subseq{S}$ も定義し直して、添字たちの集合であるところの $$ \subseq S \triangleq \{ I\in 2^{\Lambda_n}\mid \ForallL{J\in 2^{\Lambda_n}}{S_I=S_J\implies I\preceq J} \} $$ とします。

まず、ある添字 $I\in 2^{\Lambda_n}$ が $I\in\subseq{S}$ であることの必要十分条件を考えてみましょう。 $$ \begin{aligned} % I\notin\subseq{S} \iff \ExistsL{J\in 2^{\Lambda_n}}{S_I=S_J \wedge J \prec I} I\in\subseq{S} \iff \ForallL{J\in 2^{\Lambda_n}}{S_I=S_J\implies I\preceq J} \end{aligned} $$ です。 $\emptyset\in\subseq{S}$ は自明なので、以下では $I = \{i_0, i_1, \dots, i_{k-1}\}$ とします。 ある $0\le j\lt i_0$ が存在して $S_{i_0} = S_j$ のとき、$J = \{j, i_1, \dots, i_{k-1}\}$ に対して $S_I = S_J \wedge I\succ J$ となります。 よって、$i_0 = \min{\{i\in\Lambda_n\mid S_i = S_{i_0}\}}$ が必要です。 同様にして、$i_j = \min{\{i\in\Lambda_n\mid i\gt i_{j-1}\wedge S_i = S_{i_j}\}}$ ($0\lt j\lt k$) が必要です。 逆に、これで十分であることもわかります。

$I = \{i_0, i_1, \dots, i_{k-1}\}$ とし、$I \in\subseq{S}$ とします。このとき、$i_k\gt i_{k-1}$ なる $i_k$ に対して $I\cup\{i_k\}\in\subseq{S}$ となる条件を考えます。 前述の議論と同様にして、 $$\ForallL{i\in\Lambda_n}{i_{k-1}\lt i\lt i_k \implies S_i\ne S_{i_k}}$$ と同値になります。

よって、これを元にして DP を考えます。 $$ \begin{aligned} \DP[0] &= \{\emptyset\}, \\ \DP[i] &= \{I\in\subseq{S}\mid I\ne\emptyset\wedge\max I=i-1\} \end{aligned} $$ を考えます。$\subseq{S} = \bigsqcup_{i=0}^n\DP[i]$ です。

漸化式は、次のようになります。 $\gdef\last{\operatorname{last}}$ $$ \DP[i] = \bigsqcup_{j=\last(i)}^{i-1} \big\{ I \sqcup \{i-1\} \mid I\in\DP[j] \big\} $$ ここで $\last(i)$ は以下で定義される関数です。$S_{i-1}$ と同じ文字が前に現れた位置まで $\sqcup$ をしたいということです。 $$ \last(i) = \max\big(\{j\mid {1\le j \lt i} \wedge {S_{j-1}=S_{i-1}}\}\sqcup\{0\}\big) $$ これは $i$ の昇順に $\DP[i]$ を更新していく過程で、連想配列などを用いて $S_{i-1}\mapsto i$ を管理すれば $O(\log(|\Sigma|))$ 時間などで可能です。

note: $i'\lt \last(i)$ なる $i'$ に対して $I\in\DP[i']$ を考えたとき、 $$ S_{I\sqcup\{i-1\}} = S_{I\sqcup\{\last(i)\}}, \quad I\sqcup\{i-1\}\succ I\sqcup\{\last(i)\} $$ なので、$I\sqcup\{i-1\}\notin\subseq S$です。

実装の際、$i-1$ から降順に $S_{j-1}=S_{i-1}$ になるまでループをしたとしても、各 $j$ は各文字に対して一度ずつしか走査されないため、全体では $O(|S|\cdot|\Sigma|)$ 回程度のループとなります*6。$|\Sigma| = 26 = O(1)$ などのよくある問題設定であれば、$\Theta(|S|^2)$ 時間にはならないので安心できそうです*7。 $|S|\ll|\Sigma|$ のような問題設定だとそうはいきませんが、imos 法を on-the-fly で行ったりセグ木を用いたりすることで高速化することも可能そうです。

また、ここでは辞書順最小を考えましたが、末尾から見ていったりすることで、辞書順最大のものを求めることも可能そうです。

部分列 (2)

部分列 (1) とは別の方針で考えます。

$\gdef\suffix#1#2{#1[#2\ldots]}$ $0\le i\le n$ に対して $\suffix{S}{i} = (S_i, \dots, S_{n-1})$ とします。特に $\suffix{S}{0} = S$, $\suffix{S}{n} = \varepsilon$ です。

$\DP[i] = \subseq \suffix{S}{i}$ ($0\le i\lt n$) としてみましょう。漸化式は次のようになります。 $\gdef\next{\operatorname{next}}$ $$ \begin{aligned} \DP[\infty] &= \emptyset, \\ \DP[i] &= \{\{i\}\}\sqcup\bigsqcup_{\sigma\in\Sigma} {\{\{i\}\sqcup I\mid I\in \DP[\next_{\sigma}(i+1)]\}}. \end{aligned} $$ ここで、$\next_{\sigma}(i) = \min{\{j\mid S_j = \sigma\wedge j\ge i\}}$ です。ただし $\min\emptyset=\infty$ としておきます。

$i'\gt\next_{\sigma}(i+1)$ かつ $S_{i'} = S_i$ なる $i'$ に対して $I\in\DP[i']$ を考えると、先ほど同様の論法で $\{i\}\sqcup I\notin\subseq \suffix{S}{i}$ となることがわかります。逆に、$I\in\DP[\next_{\sigma}(i+1)]$ に対して $\{i\}\sqcup I\in\subseq\suffix{S}{i}$ となることもわかります。

求めたかったものは $\subseq S = {\{\emptyset\}}\sqcup{\bigsqcup_{\sigma\in\Sigma} \DP[\next_{\sigma}(0)]}$ です。

部分列を前から順に決めたい文脈で便利そうです。たとえば、$\Sigma$ に関する辞書順に関する問題と相性がよさそうです。

atcoder.jp

非負整数 (1)

非負整数 $A$ が与えられるので、$A$ 以下の非負整数全体の集合 $\{0, 1, \dots, A-1, A\}$ を得る方法を考えます。 ループすればいいというのはそうなんですが、今まで同様に漸化式を立てましょう。集合を得ること自体ではなく projection や folding をしやすい形式で考えられるようになることが目的なので。

$A$ との大小関係を管理したい関係で、上の桁から決めていくのが自然そうです。 $A$ は $n$ 桁であるとして次のような DP を考えてみます*8。 $$ \DP[i] = \{x\in\N\mid x\cdot 10^{n-i}\le A\}. \qquad (???) $$ しかし、これは厳しいです。例として $A = 271$ で考えてみましょう。$n=3$ です。 $$ \begin{aligned} \DP[0] &= \{x\in\N\mid x\cdot 10^{3-0}\le 271\} = \{0\}, \\ \DP[1] &= \{x\in\N\mid x\cdot 10^{3-1}\le 271\} = \{0, 1, 2\}, \\ \DP[2] &= \{x\in\N\mid x\cdot 10^{3-2}\le 271\} \\ &= \{0, 1, 2, 3, \dots, 9, 10, 11, \dots, 19, 20, 21, \dots, 26, 27\}, \end{aligned} $$ $\DP[2]$ に関して、$10^1$ の位が $0$, $1$ のものは $10^0$ の位が $9$ までありますが、$10^1$ の位が $2$ のものは $7$ までしかありません。 これは、漸化式を立てる上であまりうれしくありません。下位桁をどう決めても $A$ より小さいことが確定しているかどうかで分類したいです。

そこで、$\DP_{\lt}$ と $\DP_{=}$ に分けて考えます。 $$ \begin{aligned} \DP_{\lt}[i] &= \{x\in\N\mid x\cdot 10^{n-i}\lt A\}, \\ \DP_{=}[i] &= \{x\in\N\mid x\cdot 10^{n-i}=A\}. \end{aligned} $$

$A$ の上から $i$ 桁目 (0-indexed) を得る関数を定義しておきます。 $$d(A, i) \triangleq \floor{A/10^{n-i-1}}\bmod 10.$$

漸化式は次のようになります。 $$ \begin{aligned} \DP_{\lt}[0] &= \{\}, \\ \DP_{=}[0] &= \{0\}, \\ \DP_{\lt}[i] &= \{10x+y \mid x \in\DP_{\lt}[i-1], 0\le y\le 9\} \sqcup {} \\ &\phantom{{}={}}\quad \{10x+y\mid x\in\DP_{=}[i-1], 0\le y\lt d(A, i-1)\}, \\ \DP_{=}[i] &= \{10x+y \mid x\in\DP_{=}[i-1], y = d(A, i-1)\}. \end{aligned} $$ 求めたいものは $\DP_{\lt}[n]\sqcup\DP_{=}[n]$ です。$\DP_{=}[n] = \{A\}$ なので、$A$ 未満の非負整数全体の集合を考えたいときは $\DP_{\lt}[n]$ を使えばよいです（わざわざ $A-1$ を計算して上記に帰着させなくてよいということ）。

いわゆる桁 DP です。 $10$ 進法ではなく一般に $b$ 進法の場合はそれに応じて変えましょう。 なにかしらのあまりで分類したい場合や、なにかしらの値の総和を管理したい場合にも便利です。適切に漸化式を立てましょう。

なお、$\sqcup$ の引数の順序に注意することで、非負整数を昇順に列挙することが可能なことから、folding が可換でない場合にも対応することが可能そうに見えます。あまり役立つ状況は思いつきません。

ここは少し発展的な内容かもしれません。 ところで、この DP ではオートマトンを暗に考えています。 読んだ数字（上記の $0\le y\le 9$）に応じて、$(=)$ の状態からは $(=)$ または $(\lt)$ の状態に遷移することができ、$(\lt)$ の状態からは $(\lt)$ にのみ遷移することができます。 より一般に、「こうした条件を満たす集合からはこの集合に遷移できる」といったことを考えて漸化式を立てる場合、オートマトンを考えていることに相当しそうです。 遷移の方向は一方通行とは限りません。たとえば値を $m$ で割ったあまりなどの分類もオートマトンと見なせます。例として $2$ 進法として解釈して $5$ で割ったあまりで分類すると、状態が $5$ つのオートマトン上の遷移になります。

$x\bmod 5$ $(2x+0)\bmod 5$ $(2x+1)\bmod 5$
$0$ $0$ $1$
$1$ $2$ $3$
$2$ $4$ $0$
$3$ $1$ $2$
$4$ $3$ $4$

別の話題として、総和 $\sum_{x\in \DP_{\lt}[i] } x$ を考えてみましょう。 $$ \begin{aligned} \sum_{x\in\DP_{\lt}[i]} x &= \sum_{x\in\DP_{\lt}[i-1], 0\le y\le 9} (10x+y) + \sum_{x\in\DP_{=}[i-1], 0\le y\lt d(A, i-1)} (10x+y) \\ &= 10 \sum_{x\in\DP_{\lt}[i-1]} x \sum_{0\le y\le 9} 1 + \sum_{x\in\DP_{\lt}[i-1]} \sum_{0\le y\le 9} y + {} \\ &\phantom{{}={}} \quad 10 \sum_{x\in\DP_{=}[i-1]} x \sum_{0\le y\lt d(A, i-1)} 1 + \sum_{x\in\DP_{=}[i-1]} \sum_{0\le y\lt d(A, i-1)} y \\ &= 10^2 \sum_{x\in\DP_{\lt}[i-1]} x + |{\DP_{\lt}[i-1]}| \sum_{0\le y\le 9} y + 10d(A, i-1)\sum_{\DP_{=}[i-1]} x + |{\DP_{=}[i-1]}| \sum_{0\le y\lt d(A, i-1)} y \end{aligned} $$

よって、 $$ \begin{aligned} S_{\lt}^0(i) &= \sum_{x\in\DP_{\lt}[i]} x^0 = |{\DP_{\lt}[i]}|, \\ S_{\lt}^1(i) &= \sum_{x\in\DP_{\lt}[i]} x^1 = \sum_{x\in\DP_{\lt}[i]} x, \\ S_{=}^0(i) &= \sum_{x\in\DP_{=}[i]} x^0 = |{\DP_{=}[i]}|, \\ S_{=}^1(i) &= \sum_{x\in\DP_{=}[i]} x^1 = \sum_{x\in\DP_{=}[i]} x \end{aligned} $$ とおくと、 $$ S_{\lt}^1(i) = 10^2\, S_{\lt}^1(i-1) + S_{\lt}^0(i-1)\sum_{y=0}^9 y + 10d(A, i-1)\cdot S_{=}^1(i-1) + S_{=}^0(i-1)\sum_{y=0}^{d(A, i-1)-1} y $$ のような漸化式が立ちます。$S_{=}^1(i)$ についても同様にできます。 $S_{\lt}^0(i)$ については前述の DP から自然に計算できるので、総和についても求めることができました。

$S_{\lt}^2(i) = \sum_{x\in\DP_{\lt}[i]} x^2$ などについても（読者各々が式変形をして）考えてみると、個数・総和ではなく $0$ 乗和・$1$ 乗和・$2$ 乗和のように考える方が自然だと思えるでしょう。

atcoder.jp

atcoder.jp

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3110judge.u-aizu.ac.jp

非負整数 (2)

非負整数 (1) では上の桁から見ていきましたが、下の桁から見ていくことも考えてみましょう。

下位桁が決まっても $A$ との大小関係は定まらないので少し大変そうです。

今回は、$\DP_{\lt}$ と $\DP_{=}$ と $\DP_{\gt}$ に分けて考えます。 $$ \begin{aligned} \DP_{\lt}[i] &= \{x\in\N\mid x\lt A\bmod 10^i\}, \\ \DP_{=}[i] &= \{x\in\N\mid x=A\bmod 10^i\}, \\ \DP_{\gt}[i] &= \{x\in\N\mid x\gt A\bmod 10^i\}. \end{aligned} $$

$A$ の下から $i$ 桁目 (0-indexed) を得る関数を定義しておきます。 $$d(A, i) \triangleq \floor{A/10^{i}}\bmod 10.$$

漸化式は次の通りです。便宜的に、$\DP_{\lesseqgtr}[i] = \DP_{\lt}[i]\sqcup\DP_{=}[i]\sqcup\DP_{\gt}[i]$ とします。 $$ \begin{aligned} \DP_{\lt}[0] &= \DP_{\gt}[0] = \{\}, \\ \DP_{=}[0] &= \{0\}, \\ \DP_{\lt}[i] &= \{10^{i-1}x+y\mid 0\le x\lt d(A, i-1), y\in\DP_{\lesseqgtr}[i-1]\} \sqcup {} \\ &\phantom{{}={}} \quad \{10^{i-1}\cdot d(A, i-1)+y\mid y\in\DP_{\lt}[i-1]\}, \\ \DP_{=}[i] &= \{10^{i-1}\cdot d(A, i-1)+y\mid y\in\DP_{=}[i-1]\}, \\ \DP_{\gt}[i] &= \{10^{i-1}\cdot d(A, i-1)+y\mid y\in\DP_{\gt}[i-1]\} \sqcup {} \\ &\phantom{{}={}} \quad \{10^{i-1}x+y\mid d(A, i-1)\lt x\le 9, y\in\DP_{\lesseqgtr}[i-1]\}. \end{aligned} $$

求めたいものは $\DP_{\lt}[n]\sqcup\DP_{=}[n]$ です。昇順の話や未満の話、総和の話などは非負整数 (1) の節と同じです。 繰り上がりや leading zero などの関係で下の桁から見ていきたいときにはこちらが便利かもしれません。

Excel 進法

Excel の列番号は A, B, ..., Z, AA, AB, ..., AZ, BA, ..., ZZ, AAA, ..., AAAA, ... のように続いていきます。 「与えられた列番号より左の列番号は？」というのも同様の DP で列挙できます。

$\Sigma = \{\text{\texttt{A}}, \text{\texttt{B}}, \dots, \text{\texttt{Z}}\}$ とし、$S, T\in\Sigma^{\star}$ に対して順序 $\preceq$ を Excel の列番号としての前後で定めます。 次のように表すことができます。ただし、$\le$ は辞書順とします。 $$ S\preceq T \iff |S| \lt |T| \vee (|S| = |T| \wedge S\le T). $$

与えられた列番号 $A$ に対して DP を以下で定義します。 $$ \begin{aligned} \DP_{\lt}[i] &= \{S\in\Sigma^{|A|-i}\mid S\prec\suffix{A}{i}\}, \\ \DP_{=}[i] &= \{S\in\Sigma^{|A|-i}\mid S=\suffix{A}{i}\}, \\ \DP_{\gt}[i] &= \{S\in\Sigma^{|A|-i}\mid S\succ\suffix{A}{i}\}. \end{aligned} $$ 長さを固定しているので $\prec$ は $\lt$ と同じですね。

$\DP_{\lesseqgtr}[i] = \DP_{\lt}[i]\sqcup\DP_{=}[i]\sqcup\DP_{\gt}[i]$ とします。 求めたいものは $$ \left(\bigsqcup_{1\le i\lt |A|}\DP_{\lesseqgtr}[i]\right)\sqcup \DP_{\lt}[|A|]\sqcup\DP_{=}[|A|] $$ です。

便宜上 $A[|A|-i] = a_{-i}$ として、漸化式は次のように書けます。 $$ \begin{aligned} \DP_{\lt}[0] &= \DP_{\gt}[0] = \{\}, \\ \DP_{=}[0] &= \{\varepsilon\}, \\ \DP_{\lt}[i] &= \{(x)\concat S\mid \text{\texttt{A}}\le x\lt a_{-i}, S\in\DP_{\lesseqgtr}[i-1]\} \sqcup {} \\ &\phantom{{}={}} \quad \{(a_{-i})\concat S\mid S\in\DP_{\lt}[i-1]\}, \\ \DP_{=}[i] &= \{(a_{-i})\concat S\mid S\in\DP_{=}[i-1]\}, \\ \DP_{\gt}[i] &= \{(a_{-i})\concat S\mid S\in\DP_{\gt}[i-1]\} \sqcup {} \\ &\phantom{{}={}} \quad \{(a_{-i})\concat S\mid a_{-i}\lt x\le \text{\texttt{Z}}, S\in\DP_{\lesseqgtr}[i-1]\}. \end{aligned} $$

Excel 進法で列番号が与えられて、それより左に条件を満たす列がいくつありますか、という問題はあまり出なさそうですね（かなしい）。にぶたんと組み合わせることで逆変換などもできますね。

atcoder.jp

→ 提出 #45508879

分割 (exponential)

$\Lambda_n$ の分割 (partition) を考えます。 集合 $S$ の部分集合族 $P\in 2^{2^S}$ が $S$ の分割であるとは、次の 3 つの条件すべてが成り立つことを言います。

  • $\emptyset\notin P,$
  • $\bigcup P = S,$
  • $\ForallL{A\in P}{\ForallL{B\in P}{A\ne B\implies A\cap B=\emptyset}}.$

$\gdef\partition#1{\mathop{\operatorname{ptn}}{#1}}$ $S$ の分割全体からなる集合を $\partition{S}$ と書くことにします。

小さいケースの例を示します（左半分が $\Lambda_0$ から $\Lambda_3$ の分割で、右半分が $\Lambda_4$ の分割です）。 $$ \begin{aligned} &\partition{\emptyset} = \{ && {} && \partition{\{0, 1, 2, 3\}} = \{ \\ & \qquad \{\}, && {} && \qquad \{\{0, 1, 2, 3\}\}, \\ & \}, && {} && \qquad \{\{0, 2, 3\}, \{1\}\}, \\ &\partition{\{0\}} = \{ && {} && \qquad \{\{0, 1, 3\}, \{2\}\}, \\ & \qquad \{\{0\}\}, && {} && \qquad \{\{0, 3\}, \{1, 2\}\}, \\ & \}, && {} && \qquad \{\{0, 3\}, \{1\}, \{2\}\}, \\ &\partition{\{0, 1\}} = \{ && {} && \qquad \{\{0, 1, 2\}, \{3\}\}, \\ & \qquad \{\{0, 1\}\}, && {} && \qquad \{\{0, 2\}, \{1, 3\}\}, \\ & \qquad \{\{0\}, \{1\}\}, && {} && \qquad \{\{0, 2\}, \{1\}, \{3\}\}, \\ & \}, && {} && \qquad \{\{0, 1\}, \{2, 3\}\}, \\ &\partition{\{0, 1, 2\}} = \{ && {} && \qquad \{\{0, 1\}, \{2\}, \{3\}\}, \\ & \qquad \{\{0, 1, 2\}\}, && {} && \qquad \{\{0\}, \{1, 2, 3\}\}, \\ & \qquad \{\{0, 2\}, \{1\}\}, && {} && \qquad \{\{0\}, \{1, 3\}, \{2\}\}, \\ & \qquad \{\{0, 1\}, \{2\}\}, && {} && \qquad \{\{0\}, \{1, 2\}, \{3\}\}, \\ & \qquad \{\{0\}, \{1, 2\}\}, && {} && \qquad \{\{0\}, \{1\}, \{2, 3\}\}, \\ & \qquad \{\{0\}, \{1\}, \{2\}\}, && {} && \qquad \{\{0\}, \{1\}, \{2\}, \{3\}\}, \\ & \}, && {} && \}. \end{aligned} $$ $\partition{\emptyset} = \{\emptyset\}$ に注意しましょう。$\emptyset\in\emptyset$ ではないので、$\emptyset\notin P$ に反していません。 分割でない例としては、$\{\{0\}, \{0, 1\}\}\notin\partition{\{0, 1\}}$ や $\{\{0, 1\}, \{2\}, \{\}\} \notin \partition{\{0, 1, 2\}}$ などがあります。

$\emptyset\subseteq T\subseteq S=\Lambda_n$ に対して $\DP[T] = \partition{T}$ とすると、漸化式は次のようになります。 $$ \begin{aligned} \DP[\emptyset] &= \{\emptyset\}, \\ \DP[T] &= \bigsqcup_{\emptyset\subseteq T'\subseteq(T\smallsetminus\{\min T\})} \{ P\sqcup (T\smallsetminus T') \mid P\in\DP[T'] \}. \end{aligned} $$

実装に関して、$\emptyset\subseteq T'\subseteq(T\smallsetminus\{\min T\})$ の列挙の際に、「$T'\subseteq S$ を列挙して $T'\subseteq(T\smallsetminus\{\min T\})$ のもののみ使う」のではなく直接 $T\smallsetminus\{\min T\}$ の部分集合を列挙することで、$\Theta(4^{|S|})$ 回ではなく $\Theta(3^{|S|})$ 回のループに減らすことができます。

概略

ここでは $T\smallsetminus \{\min T\}$ ではなく $S$ としていますが定数倍の違いしかないので問題ないでしょう（気になる読者は自分で手を動かしてみよう！）。 $$ \begin{aligned} \sum_{\emptyset\subseteq T\subseteq S} 2^{|T|} &= \sum_{i=0}^{|S|} \sum_{|T|=i, T\subseteq S} 2^{|T|} \\ &= \sum_{i=0}^{|S|} 2^i \cdot |\{T\in 2^S\mid |T| = i\}| \\ &= \sum_{i=0}^{|S|} 2^i \cdot \textstyle\binom{|S|}{i} \\ &= \sum_{i=0}^{|S|} \textstyle\binom{|S|}{i} \cdot 2^i \cdot 1^{|S|-i} \\ &= (2+1)^{|S|} = 3^{|S|}. \qquad\qed \end{aligned} $$ 実装例に関する詳細な説明はここではしません。

ところで、$B_n = |{\partition{\{0, 1, \dots, n-1\}}}|$ で定義される数列は Bell 数と呼ばれています。 上記の DP の漸化式における各 $T'$ のサイズと選び方の通り数を考えることで、Bell 数に関する漸化式が導かれます。 $$ \begin{aligned} B_0 &= 1, \\ B_n &= \sum_{i=0}^{n-1} \textstyle\binom{n}{i} B_i. \end{aligned} $$

分割に関する例題としては次のようなものがあります。この問題は数え上げではなく最適化なので、実装上 $\sqcup$ を気にするのが面倒であれば、$\cup$ になるような実装をしても大丈夫でしょう。

atcoder.jp

正規括弧列

この節では、簡潔さのため $S\concat T$ や $(x)\concat S\concat (y)$ を単に $ST$、$xSy$ などと書くことにします。

$\gdef\openp{\text{\texttt{(}}}$ $\gdef\closep{\text{\texttt{)}}}$ サイズ $n$ の正規括弧列とは、$n$ 個の $\openp$ と $n$ 個の $\closep$ からなる列であって、次のいずれかの条件を満たすものを言います。

  • 空列である
  • ある $0\lt k\lt n$ に対し、サイズ $k$ の正規括弧列 $S$ とサイズ $n-k$ の正規括弧列 $T$ が存在して $ST$ と書ける
  • ある $0\le k\lt n$ に対し、サイズ $k$ の正規括弧列 $S$ が存在して $\openp S \closep$ と書ける

いわゆる「バランスの取れた括弧列」「対応の取れた括弧列」「balanced parentheses」「regular parentheses」「well-formed parentheses」とか呼ばれるものです。短めのよい訳語があれば知りたいです。

サイズ $n$ の正規括弧列全体からなる集合を $P_n$ とすると、次の式が成り立ちます。 $$ \begin{aligned} P_0 &= \{\varepsilon\}, \\ P_n &= \bigsqcup_{i=0}^{n-1} {\{ \openp S \closep T \mid (S, T)\in P_i\times P_{n-i-1} \}}. \end{aligned} $$ 空でないとき先頭の文字は必ず $\openp$ になることに注意します。それに対応する $\closep$ の位置が各 $i$ ごとに異なることから、$\sqcup$ を使って問題ありません。

小さいケースの例は次の通りです。 $$ \begin{aligned} P_0 &= \{\varepsilon\}, \\ P_1 &= \{\openp\closep\}, \\ P_2 &= \{\openp\closep\openp\closep, \openp\openp\closep\closep\}, \\ P_3 &= \{\openp\closep\openp\closep\openp\closep, \openp\closep\openp\openp\closep\closep, \openp\openp\closep\closep\openp\closep, \openp\openp\closep\openp\closep\closep, \openp\openp\openp\closep\closep\closep\}, \\ \end{aligned} $$

さて、それはそれとして、長さ $n$ の列 $a = (a_0, a_1, \dots, a_{n-1})$ と（結合則を満たすとは限らない）適当な二項演算 $\odot$ を考えます。 $a$ の各要素への $\odot$ の適用させ方を列挙してみましょう。$n=4$ とします。

  • $(a_0\odot (a_1\odot (a_2\odot a_3)))$,
  • $(a_0\odot ( (a_1\odot a_2)\odot a_3))$,
  • $( (a_0\odot a_1)\odot (a_2\odot a_3))$,
  • $( (a_0\odot (a_1\odot a_2))\odot a_3)$,
  • $( ( (a_0\odot a_1)\odot a_2)\odot a_3)$.

$($ を $\openp$ に、$\odot$ を $\closep$ に置き換え、それ以外の文字を消すことで $P_3$ の各要素と対応づけられることがわかります*9。 $\odot$ はあくまで形式的な演算子であり、「その計算結果がたまたま同じになったら同一視する」といったようなことは考えないことにします。

$\gdef\paren#1{\mathop{\operatorname{paren}}{#1}}$ というわけで、この括弧のつけ方全体からなる集合を考えます。$a$ への括弧のつけ方全体からなる集合を $\paren{a}$ と書くことにします。次のことが成り立ちます。 $$ \begin{aligned} \paren{(x, y)} &= \{(x\odot y)\}, \\ \paren{a} &= \{(S\odot T)\mid ST = a\}. \end{aligned} $$ $\DP[\angled{l, r}] = \paren{(a_l, a_{l+1}, \dots, a_{r-1})}$ とすると、次のようにできます。 $$ \begin{aligned} \DP[\angled{i, i+1}] &= \{a_i\}, \\ \DP[\angled{l, r}] &= \bigcup_{i=l+1}^{r-1} \big\{ (S\odot T)\mid (S, T)\in \DP[\angled{l, i}]\times\DP[\angled{i, r}] \big\}. \end{aligned} $$

note: $(S\odot T)$ は $\openp S\closep T$ に対応しています。$\paren{a} = \DP[\angled{0, n}]$ です。

いわゆる区間 DP です。括弧列との対応づけを意識せずに覚えている人もいるのかもしれません？と思ったものの、連鎖行列積問題だったりスライムをくっつけるやつだったりが有名問題であることを考えると、全員がそういう認識を持っている気もしてきました。実際のところどうなのでしょうか。

サイズ $n$ の正規括弧列の個数は Catalan 数と呼ばれ、よく $C_n$ と書かれます。 これは $C_n = \Theta(4^n/n^{1.5})$ であることが示せます。 このことから、（要素数 $n$ の集合の部分集合が $\Theta(2^n)$ 個であることを考えると）最初に見たような先頭 $i$ 個目で 2 通りに分岐するような DP では全パターンを網羅できず、正規括弧列全体に関して考えたい問題では不適当であることがすぐにわかりそうです。 あまりこうした指摘をしている解説は見ない気がしますね。

atcoder.jp

この問題は、実際には、固有の性質を用いることで区間 DP を使わず $O(n\log(n))$ 時間で解けることが知られています。

Catalan 数のオーダーについて

導出はここでは行いませんが、下記のように表せます。 $$ C_n = \frac{(2n)!}{n!\,(n+1)!}. $$ また、Stirling の近似公式から、下記が成り立ちます。 $$ n! = \Theta(\sqrt{n}\, (n/e)^n). $$ $(n+1)! = \Theta(n\cdot n!)$ であることに気をつけつつ、あとは手の運動です。 $$ \begin{aligned} C_n &= \Theta{\left(\frac{(2n)!}{n\cdot (n!)^2}\right)} \\ &= \Theta{\left(\frac{\sqrt{2n}\,(2n/e)^{2n}}{n\cdot (\sqrt{n}\,(n/e)^n)^2}\right)} \\ &= \Theta{\left(\frac{\sqrt{2n}\,(2n/e)^{2n}}{n^2 (n/e)^{2n}}\right)} \\ &= \Theta{\left(\frac{\sqrt{2n}\cdot 2^{2n}}{n^2}\right)} \\ &= \Theta(4^n/n^{1.5}). \end{aligned} $$

最後の行では定数倍の $\sqrt{2}$ を無視していることに注意してください。

順列 (polynomial-1)

順列について別のアプローチを考えてみます。 $\Lambda_n!$ について考えたいです。

順列 (exponential) の方では「順列を前から作っていき、どの要素を使ったかで分類する」という戦略に基づいており、集合を管理する必要がありました。 ここでは、順列 $p$ を「$i$ や $p_i$ が小さい方から決めていく」という戦略を考えます。

$\{(0, p_0), (1, p_1), \dots, (n-1, p_{n-1})\}$ ($i\ne j\implies p_i\ne p_j$) なる集合は、$(p_0, p_1, \dots, p_{n-1})\in \Lambda_n!$ に対応します。よって、順列を直接考える代わりにこうした形式の集合を考えてもよいことになります。 そこで、左右の要素が $i$ 未満かつ、左の要素が相異なり、右の要素も相異なる集合を考えます。 $$ S_i = \{S\in \Lambda_i^2\mid \ForallL{(k_l, k_r)\in S}{\ForallL{(k_l', k_r')\in S}{(k_l, k_r)\ne(k_l', k_r')\implies k_l\ne k_l'\wedge k_r\ne k_r'}}\}. $$ 小さい方から挙げると $$ \begin{aligned} S_0 &= \{\emptyset\}, \\ S_1 &= \{\emptyset, \{(0, 0)\}\}, \\ S_2 &= \{\emptyset, \{(0, 0)\}, \{(0, 1)\}, \{(1, 0)\}, \{(1, 1)\}, \{(0, 0), (1, 1)\}, \{(0, 1), (1, 0)\}\} \end{aligned} $$ などです。実際に手で書いてみると「結構すぐ大きくなりそうだな」という感覚を得やすいのでおすすめです。

さて、$\Lambda_n = \{S\in S_n\mid |S| = n\}$ なので、次のような DP を考えてみます。 $$ \DP[\angled{i, j}] = \{S\in S_i\mid |S| = j\}. $$

漸化式は次のようになります。 $$ \begin{aligned} \DP[\angled{i, 0}] &= \{\emptyset\}, \\ \DP[\angled{0, j}] &= \emptyset, \\ \DP[\angled{i, -1}] &= \emptyset, \\ \DP[\angled{i, j}] &= \DP[\angled{i-1, j}] \sqcup {} \\ % &\phantom{{}={}}\quad \bigsqcup_{S\in\DP[\angled{i-1, j-1}]} f_{=}(S, i) \sqcup {} \\ % &\phantom{{}={}}\quad \bigsqcup_{S\in\DP[\angled{i-1, j-1}]} f_{\lt}(S, i) \sqcup {} \\ % &\phantom{{}={}}\quad \bigsqcup_{S\in\DP[\angled{i-1, j-1}]} f_{\gt}(S, i) \sqcup {} \\ &\phantom{{}={}}\quad \bigsqcup_{S\in\DP[\angled{i-1, j-1}]} \big(f_{=}(S, i)\sqcup f_{\lt}(S, i)\sqcup f_{\gt}(S, i)\big) \sqcup {} \\ &\phantom{{}={}}\quad \bigsqcup_{S\in\DP[\angled{i-1, j-2}]} f_{\lessgtr}(S, i) \end{aligned} $$ ここで、各 $f_{\ast}(S, i)$ は次のもの全体からなる集合を返す関数です（数式での定義は後述します）。

  • $f_{=}(S, i)$：集合 $S$ に $(i-1, i-1)$ を追加してできる集合
  • $f_{\lt}(S, i)$：集合 $S$ に $(j, i-1)$ ($j\lt i-1$) を追加してできる集合
    • ただし、左の要素が $j$ である要素は $S$ に含まれていないとする
  • $f_{\gt}(S, i)$：集合 $S$ に $(i-1, j)$ ($j\lt i-1$) を追加してできる集合
    • ただし、右の要素が $j$ である要素は $S$ に含まれていないとする
  • $f_{\lessgtr}(S, i)$：集合 $S$ に $(j_l, i-1)$ と $(i-1, j_r)$ ($j_l, j_r\lt i-1$) を追加してできる集合
    • ただし、左の要素が $j_l$ である要素、右の要素が $j_r$ である要素は $S$ に含まれていないとする

すなわち、次のように書けます。 $$ \begin{aligned} f_{=}(S, i) &= \big\{S\sqcup \{(i-1, i-1)\}\big\}, \\ f_{\lt}(S, i) &= \big\{S\sqcup \{(j, i-1)\}\mid j\in \Lambda_{i-1}, \ForallL{i'\in\Lambda_{i-1}}{(j, i')\notin S}\big\}, \\ f_{\gt}(S, i) &= \big\{S\sqcup \{(i-1, j)\}\mid j\in \Lambda_{i-1}, \ForallL{i'\in\Lambda_{i-1}}{(i', j)\notin S}\big\}, \\ f_{\lessgtr}(S, i) &= \big\{S\sqcup \{(j_l, i-1), (i-1, j_r)\}\\ &\phantom{{}={}} \qquad \mid (j_l, j_r)\in \Lambda_{i-1}^2, \ForallL{i'\in\Lambda_{i-1}}{(i', j_r)\notin S\wedge (j_l, i')\notin S}\big\}. \end{aligned} $$

求めるものは $$ % \Lambda_n! = \bigsqcup_{S\in\DP[\angled{n, n}]}{\{(p_0, p_1, \dots, p_{n-1})\mid \{(i, p_i)\}_{i=0}^{n-1}\in S\}} \Lambda_n! = \big\{(p_0, p_1, \dots, p_{n-1})\mid \{(i, p_i)\}_{i=0}^{n-1}\in \DP[\angled{n, n}]\big\} $$ です。

さて、$f_{\lt}(S, i)$ などの計算に関して補足です。 各順列を陽に列挙したい（つまり、実質的に計算量を度外視できる）文脈であれば愚直にやればいいのですが、計算量を改善するために DP したい文脈ではそうはいきません。 これに関しては projection や folding の性質との兼ね合いになりますが、たとえば要素数に関してであれば次のようにうまくいきます。 $$ \begin{aligned} |f_{=}(S, i)| &= 1, \\ |f_{\lt}(S, i)| &= i-1-|S|, \\ |f_{\gt}(S, i)| &= i-1-|S|, \\ |f_{\lessgtr}(S, i)| &= (i-1-|S|)^2. \end{aligned} $$ ここで $S\in\DP[\angled{i, j}]$ のとき $|S|=j$ であることに注意しましょう。 つまり下記のようになります。 $$ \begin{aligned} |{\DP[\angled{i, 0}]}| &= 1, \\ |{\DP[\angled{0, j}]}| &= 0, \\ |{\DP[\angled{j, -1}]}| &= 0, \\ |{\DP[\angled{i, j}]}| &= |{\DP[\angled{i-1, j}]}| + {} \\ &\phantom{{}={}} \quad |{\DP[\angled{i-1, j-1}]}|\cdot(1 + 2\cdot(i-j)) + {} \\ &\phantom{{}={}} \quad |{\DP[\angled{i-1, j-2}]}|\cdot (i-j-1)^2. \end{aligned} $$

いわゆる箱根駅伝 DP と呼ばれているものになります。よくある「保留」という言い回しを意識しない形で定式化してみました。 名前の由来は AOJ 2439 です。

atcoder.jp

順列 (polynomial-2)

他の方針で順列 $\Lambda_n!$ を列挙してみます。 基本的な方針は「$i$ 回目の更新では $i$ 通りの要素を生成する」です。 空列についてはいつも同じです。 $$\DP[0] = \{\varepsilon\}.$$ $i$ 回目の操作についてはいくつかの方法がありますが、概ね次の形式になるでしょう。 $$ \DP[i] = \bigsqcup_{P\in\DP[i-1]} f_i(P). $$

$f_i$ としては次のようなものが考えられます。$P = (p_0, p_1, \dots, p_{i-2})$ としておきます。 $$ \begin{aligned} % f_i^{\text{insert}}( (p_0, p_1, \dots, p_{i-2})) &= \{ f_i^{\text{insert-x}}(P) &= \{ (p_0, \dots, p_{j-1}, i-1, p_j, \dots, p_{i-2}) \mid j\in\Lambda_i \}, \\ f_i^{\text{swap}}(P) &= \{ (p_0, \dots, p_{j-1}, i-1, p_{j+1}, \dots, p_{i-2}, p_j) \mid j\in\Lambda_{i-1} \} \sqcup {} \\ &\phantom{{}={}}\quad\{P\concat (i-1)\}, \\ f_i^{\text{insert-y}}(P) &= \{ (p_0', \dots, p_{i-2}', i-1) \mid j\in\Lambda_i \}. \end{aligned} $$ ただし、$f_i^{\text{insert-y}}$ における $p_j'$ は次のように定義されるとします。 $$ p_j' = \begin{cases} p_j, & \text{if }p_j \lt i-1; \\ p_j + 1, & \text{if }p_j \ge i-1. \end{cases} $$ たとえば $$ \begin{aligned} &f_4^{\text{insert-x}}( (0, 2, 1)) = \{ \\ &\qquad (3, 0, 2, 1), \\ &\qquad (0, 3, 2, 1), \\ &\qquad (0, 2, 3, 1), \\ &\qquad (0, 2, 1, 3), \\ &\}, \\ &f_4^{\text{swap}}( (0, 2, 1)) = \{ \\ &\qquad (3, 2, 1, 0), \\ &\qquad (0, 3, 1, 2), \\ &\qquad (0, 2, 3, 1), \\ &\qquad (0, 2, 1, 3), \\ &\}, \\ &f_4^{\text{insert-y}}( (0, 2, 1)) = \{ \\ &\qquad (1, 3, 2, 0), \\ &\qquad (0, 3, 2, 1), \\ &\qquad (0, 3, 1, 2), \\ &\qquad (0, 2, 1, 3), \\ &\} \end{aligned} $$ です。

insert-x や insert-y の気持ちは、$(x, y) = (i, p_i)$ なる点をプロットするのに基づいています。 よく挿入 DP などと呼ばれています。

何かしらの個数を固定したときの順列を数え上げたい文脈では、bit DP をせずに $n^{O(1)}$ 個に分類できないか考えてみましょう（bit DP を経由して考察するのも悪くはないと思います）。問題の条件や projection・folding との兼ね合いで、どのような $f_i$ と相性がよいかを考えるとよさそうです。

atcoder.jp

ricky-pon.hatenablog.com

階乗・分割 (polynomial)

集合 $S$ を $k$ 個の円順列に分けたもの全体からなる集合を $[S]_k$、$k$ 個の集合に分けたもの全体からなる集合を $\{S\}_k$ と書くことにしてみます。$|[S]_k| = {|S|\brack k}$, $|\{S\}_k| = {|S|\brace k}$ に由来する記法です。これもあまり見ない気がしますがよいでしょう。 それぞれの要素数は、第一種 Stirling 数、第二種 Stirling 数と呼ばれています。

$a_0\stackrel{p}{\mapsto} a_1, \dots, a_{m-2}\stackrel{p}{\mapsto} a_{m-1}, a_{m-1}\stackrel{p}{\mapsto}a_0$ のような順列 $p$ を円順列といい、$[a_0, a_1, \dots, a_{m-1}]$ と書くことにします。特に、$[a_0]$ は $a_0\stackrel{p}{\mapsto} a_0$ を意味します。

$[S]_k$ や $\{S\}_k$ の例としては次のようになります。 $$ \begin{aligned} & [\Lambda_4]_2 = \{ \\ & \qquad \{[0, 3, 2], [1]\}, \\ & \qquad \{[0, 2, 3], [1]\}, \\ & \qquad \{[0, 2], [1, 3]\}, \\ & \qquad \{[0, 3], [1, 2]\}, \\ & \qquad \{[0], [1, 3, 2]\}, \\ & \qquad \{[0], [1, 2, 3]\}, \\ & \qquad \{[0, 3, 1], [2]\}, \\ & \qquad \{[0, 1, 3], [2]\}, \\ & \qquad \{[0, 1], [2, 3]\}, \\ & \qquad \{[0, 2, 1], [3]\}, \\ & \qquad \{[0, 1, 2], [3]\}, \\ & \}, \\ & \{\Lambda_4\}_2 = \{ \\ & \qquad \{\{0, 2, 3\}, \{1\}\}, \\ & \qquad \{\{0, 2\}, \{1, 3\}\}, \\ & \qquad \{\{0, 3\}, \{1, 2\}\}, \\ & \qquad \{\{0\}, \{1, 2, 3\}\}, \\ & \qquad \{\{0, 1, 3\}, \{2\}\}, \\ & \qquad \{\{0, 1\}, \{2, 3\}\}, \\ & \qquad \{\{0, 1, 2\}, \{3\}\}, \\ & \}. \end{aligned} $$

ここで考えている円順列の集合は、各々の要素に重複がないので、全体で一つの順列と見なすことができることに注意しておきます。 たとえば、$\{[0, 3, 1], [2, 4]\}$ は $(3, 0, 4, 1, 2)$ に相当します。

漸化式を書くにあたって、順列に対する操作に関する記法を導入しておきます。 $p_x$ が定義された $x$ と $p_y$ が定義されていない $y$ に対して、$p\veebar (x\mapsto y)$ は次の対応づけからなる順列とします。

  • $x\mapsto y$,
  • $y\mapsto p_x$,
  • $z\mapsto p_z$ ($z\ne x\wedge z\ne y$).

また、$p_x$ が定義されていない $x$ に対して $p\sqcup [x]$ は次の対応づけからなる順列とします。

  • $x\mapsto x$,
  • $y\mapsto p_y$ ($y\ne x$).

この記法を用いて、漸化式は次のように書けます。 $$ \begin{aligned} [\Lambda_0]_0 &= \{\emptyset\}, \\ [\Lambda_0]_k &= \emptyset, \\ [\Lambda_n]_0 &= \emptyset, \\ [\Lambda_n]_k &= \{p\sqcup [n-1]\mid p\in[\Lambda_{n-1}]_{k-1}\} \sqcup {} \\ &\phantom{{}={}}\quad \bigsqcup_{p\in[\Lambda_{n-1}]_k} {\{ p\veebar (j\mapsto n-1) \mid j\in \Lambda_{n-1} \}}. \end{aligned} $$ 集合への分割の方は次の通りです。 $$ \begin{aligned} \{\Lambda_0\}_0 &= \{\emptyset\}, \\ \{\Lambda_0\}_k &= \emptyset, \\ \{\Lambda_n\}_0 &= \emptyset, \\ \{\Lambda_n\}_k &= \{p\sqcup \{n-1\}\mid p\in\{\Lambda_{n-1}\}_{k-1}\} \sqcup {} \\ &\phantom{{}={}}\quad \bigsqcup_{p\in\{\Lambda_{n-1}\}_k} {\{ (p\smallsetminus S)\sqcup(S\sqcup \{n-1\})\mid S\in p \}}. \end{aligned} $$

これらの漸化式から、Stirling 数に関する漸化式も導かれます。

$$ \begin{aligned} \textstyle{n\brack k} &= \textstyle{n-1\brack k-1} + (n-1)\,\textstyle{n-1\brack k}, \\ \textstyle{n\brace k} &= \textstyle{n-1\brace k-1} + k\,\textstyle{n-1\brace k}. \end{aligned} $$

また、$\bigsqcup_{k=0}^n {[\Lambda_n]_k} = \Lambda_n!$ や $\bigsqcup_{k=0}^n {\{\Lambda_n\}_k} = \partition{\Lambda_n}$ などが成り立ちます。

矩形領域

順列 $p\in\Lambda_n!$ に対して、点群 $S = \{(i, p_i) \mid i\in\Lambda_n\}$ を x-y 平面にプロットすることを考えます。 このとき、ある点 $(x, y)\in \Lambda_n^2$ の左下領域 $$ T_{(x, y)} = \{(x', y')\in S \mid x'\le x\wedge y'\le y\} $$ を考えます。 $p_i = 0$ なる $i$ に対して $T_{(i, p_i)} = \{(i, p_i)\}$ となるのは明らかでしょう。 そこで、$y$ 座標の昇順に漸化式を立てることを考えます*10。

便宜上、$q_{p_i} = i$ なる順列 $q$（すなわち $p$ の逆順列）を定義しておきます。 上記のことは $T_{(q_0, 0)} = \{(q_0, 0)\}$ と言い換えられます。

さて、漸化式は次のようになります。 $$ \begin{aligned} T_{(x, 0)} &= \emptyset && (x\lt q_0), \\ T_{(x, 0)} &= \{(q_0, 0)\} && (x\ge q_0), \\ T_{(x, y)} &= T_{(x, y-1)} && (x\lt q_y), \\ T_{(x, y)} &= T_{(x, y-1)}\sqcup\{(q_y, y)\} && (x\ge q_y). \end{aligned} $$

$y$ を固定したときの処理としては、$q_y$ を境として左側は何もせず、右側は $(q_y, y)$ を追加するだけですので、区間に対する更新ができるデータ構造を用いることで高速に処理が可能です（$y$ ごとに $T$ を使い回すイメージです）。

あるいは、 $$ a_{(x, y)} = \begin{cases} \emptyset, & \text{if }p_x \lt y; \\ \{(x, p_x)\}, & \text{if }p_x \ge y \end{cases} $$ のような配列 $a_{(x, y)}$ を管理することで、区間 fold ができるデータ構造を用いることも可能です。 $T_{(x, y)} = \bigsqcup_{x'\le x} a_{(x', y)}$ ということです。

このように、いずれかの座標の昇順（や降順）に処理を進めることで、条件の不等式を処理順に言い換えるテクは平面走査と呼ばれています。元々は計算幾何学側の用語のはずで、英語だと sweeping と呼ばれていたと思います。処理順に沿って動く線（今回の例であれば、$x$ 座標に対して平行な、$y$ 軸正方向に動く線）を走査線と呼びます。走査線は座標軸に平行とは限らず、たとえば初めは半直線 $OX$ から開始して反時計回りに回転するようなケースもあります。また、今回は $x'\le x$ のように片側が閉じていない区間でしたが、$x_l\le x'\le x_r$ のような処理を行う問題も頻出です（DP だと認識することは少ないかもしれません）。

このテクで解ける頻出問題としては、LIS や転倒数などがあります。

atcoder.jp

atcoder.jp

部分集合 + 区間

$[0, n)$ に含まれる非空な区間全体からなる集合 $A_n$ を考えます（境界は整数とします）。 $$ A_n = \{[l, r) \mid (l, r)\in\Lambda_n, l\lt r\}. $$ これの部分集合 $S \in 2^{A_n}$ が与えられるとして、それに関する問題を考えます。

$I\in 2^{\Lambda_n}$ に対して以下のような集合を返す関数を考えます。 $$ f_S(I) = \{x\in S\mid \ExistsL{i\in I}{i\in x}\}. $$

直感的な説明としては、選んだいくつかの座標で区間を串刺しにするとき、実際に串が刺さる区間を返すものです。 以下に図も示します。[---) が区間、^ が串です。

  0  1  2  3  4  5  6  7  8
  ^  ^                 ^         # S = {
  [--------)           ^         #   [0, 3),
  ^  ^  [--------------)         #   [2, 7),
  ^  [-----------)     ^         #   [1, 5),
  ^  ^              [-----)      #   [6, 8),
  ^  ^                 ^         # }
  ^  ^                 ^         # I = {0, 1, 7}

$S = \{[0, 3), [2, 7), [1, 5), [6, 8)\}$ と $I = \{0, 1, 7\}$ です。$f_S(I) = \{[0, 3), [1, 5), [6, 8)\}$ となります。

さて、次の集合を考えたいです。すなわち、全部の刺し方における区間の選ばれ方を列挙したいです。 $$ % \{ f_S(I) \mid I\in 2^{\Lambda_n} \}. \bigcup_{I\in 2^{\Lambda_n}} f_S(I). $$

次のような DP を考えてみましょう。 $$ \begin{aligned} % % \DP[\angled{i, j}] &= \big\{f_{\{[l, r)\in S\mid r\le i\}}(I) \\ % \DP[\angled{i, j}] &= \big\{f_{S\cap A_i}(I) \\ % &\phantom{{}={}} \qquad \mid I\in 2^{\Lambda_i}, \max {(\{i+1\mid i\in I\}\sqcup \{0\})} = j\big\}. \DP[\angled{i, j}] &= \big\{f_{S\cap A_i}(I) \mid I\in 2^{\Lambda_i}, \max {(\{i+1\mid i\in I\}\sqcup \{0\})} = j\big\}. \end{aligned} $$ 区間は右端が $i$ 以下のもの、刺し方は最大値が $j-1$（$j=0$ のときは刺さない）のもので絞っています*11。 欲しいのは $\bigcup_{j=0}^n {\DP[\angled{n, j}]}$ です。$\sqcup$ は難しかったです。 また、$j$ の範囲は $0\le j\le i$ とします。

さて、漸化式は次のようになります。簡潔さのため、$S_i = \{[l, r) \in S\mid r = i\}$ と定義しておきます。 $$ \begin{aligned} \DP[\angled{0, 0}] &= \{\emptyset\}, \\ \DP[\angled{i, i}] &= \bigcup_{j=0}^{i-1}{\{T\sqcup S_i\mid T\in\DP[\angled{i-1, j}]\}}, \\ \DP[\angled{i, j}] &= \{ T\sqcup\{[l, r)\in S_i\mid l\lt j\} \mid T\in\DP[\angled{i-1, j}] \}. \end{aligned} $$ $\DP[\angled{i, \ast}]$ では、$\DP[\angled{i-1, \ast}]$ と比べて「右端が $i$ の区間の集合」と「座標 $i-1$ で串を刺すかどうかの分岐」の考慮が増えます。 $i-1$ で串を刺す場合は、新しく増えた（右端が $i$ の）区間たちは選ばれます。 一方、$i-1$ で串を刺さない場合は、新しく増えた区間のうち $j-1$ で刺されるもの（すなわち $l\lt j$ のもの）だけが選ばれます。

ここからは projection・folding を行うことを前提とした話になります。 さらに、$\DP[\angled{i-1, \ast}]$ と $\DP[\angled{i, \ast}]$ の違いについて注目しましょう。 まず、$\DP[\angled{i, i}]$ に関しては $\DP[\angled{i-1, 0}], \dots, \DP[\angled{i-1, i-1}]$ のそれぞれに $S_i$ を合わせたものになります。projection・folding の文脈で言えば、 $$ \bigodot_{j=0}^{i-1} {\{f(T\sqcup S_i)\mid T\in\DP[\angled{i-1, j}]\}} $$ を高速に計算できればうれしいです。 $\DP[\angled{i, j}]$ に関しては次の通りです。

  • $\DP[\angled{i, j}]$ に $\DP[\angled{i-1, j}]$ をコピーする。
  • $[l, r)\in S_i$ なる各区間に対して次の更新を行う。
    • $l\lt j\lt i$ なる各 $\DP[\angled{i, j}]$ に対して、$[l, r)$ を追加したときの値で計算し直す。

これも projection・folding との兼ね合いですが、そういうデータ構造を用いることで可能な状況が多そうです。 $\DP[\angled{i, i}]$ の方の更新もまとめて $l\lt j\le i$ の区間を更新する方が実装が簡潔になるかもしれません。

ところで、$\DP[\angled{i-1, \ast}]$ を $\DP[\angled{i, \ast}]$ にコピーする部分に関しては、（後から $\DP[\angled{n, \ast}]$ 以外を使いたい状況でなければ）$\DP[\ast]$ だけの一次元の配列だということにして使い回すことで、何もせずに済みます。 これにより、$O(n)$ 回の区間 fold と $O(|S|)$ 回の区間更新で達成できます。 ただし、$\bigodot {\{f(T\sqcup S_i)\}} = (\bigodot f(T))\odot f(S_i)$ などのよい性質があって、$S_i$ を追加したときの値が容易に計算できることが前提となっています。

このような前提の下で、DP 配列を使い回して in-place に更新を行うテクは、インライン DP とか in-place DP とか実家とか呼ばれています。このテク自体はこの節で考えたようなテーマに固有のものではありません。平面走査のところでも使いましたね。

topcoder-g-hatena-ne-jp.jag-icpc.org

atcoder.jp

その他

グリッドの左上から右下に、右または下への移動を繰り返す経路の総数を考える問題があります。 これは、各マスに到達する経路の集合を持っていると見なせます。

EDPC Z のような、いくつかのマスを経由してゴールに到達するまでのコストの最小値を求める問題があります。 これは、経由するマスの部分集合を考えていると見なせます。マス $j$ から $i$ への移動のコストが $j$ 以前の経路によらないことから同一視して状態数を減らしています。EDPC Z ではさらに CHT などで高速化をします。

いくつか問題を挙げるので考えてみるとよいでしょう。解説をしながら挙げたものも含みます。

実装例

Rust での実装例です。計算量度外視の回なので、競プロ用に直接役立つことは少ないかもしれません。 記事中の記述が正しいことの verify 用としての役割程度のものです。

関連資料

下記の記事で挙げられているようなものについても考えてみるとよいかもしれません。

degwer.hatenablog.com

この記事を書くにあたって調べていた過程で見つけたものも貼ります。記事中では触れていないテーマですが面白そうです。

hackmd.io

あとがき

つかれました。

初心者の頃、数え上げ DP をするときに具体的な対象がイメージできておらずに MECE になっていない漸化式を立てたりしていた記憶が蘇ってきたので、陽に列挙することで意識してみようという企画でした。 最近始めて DP に悩んでいる人たちはどのようにイメージして考察・実装しているのでしょうね。

正規括弧列の節でも述べましたが、考えようとしている対象の個数と DP で列挙できる個数に乖離がないかを意識してみるのも大事そうです。たとえば、Fibonacci 数列の節では $\{1, 2\}^{\star}$ の列で総和が $n$ のものを考えましたが、$\{1, 2, \dots, n\}^{\star}$ の列で総和が $n$ のものはどの程度の個数になるかイメージがつくでしょうか？

この記事の内容は、その手の構造で DP をしたいとき用の「ライブラリ」のような立ち位置であるものの直接 #include use import などで使い回しにくいような内容になっているような気がします（できなくもないものもあるかとは思いますが）。 とはいえ考察の引き出しとしては有用だと思うので、何らかの方法で整理しておくといいのかなと思います。

また数式多めの記事になってしまった気がする（それ自体は別に悪いことではなくて、ある種当然だとも思います）ので、数式が苦手な人が数式を得意になってくれるような解説も書けたらいいなと思いつつ、えびちゃん向きではないという気もします。 苦手な人というのはワンパターンではないと思うので、「この記事読んでね」でうまくいきにくいような気がしていて、一対多でやりにくい気がしているんですよね。 競プロで出てくる文脈の数式っていわゆる中学・高校数学は必ずしも前提としないので、「数式多めの競プロ解説を読めるようになる」とかを目標にした教育コンテンツというのもありかもしれません？

当初の予定ではもっと軽く書く予定だったんですが、気づいたらボリューム多めになってしまいました。 $\KaTeX$ の数式の記述も含めると 5 万文字を超えてしまっています。 ボリューム多めの記事がお好みの方は下記もおすすめです。

rsk0315.hatenablog.com

もうこれ 2 年前の記事らしいです。気が向いたらまたなにか書こうと思います。

おわり

おわりです。おつかれさまでした。

*1:文字集合はアルファベットとも呼ばれます。形式言語理論や文字列界隈の用語です。たまたま集合として一致することはありますが、いわゆる [A-Za-z] を指す用語ではないので注意しましょう。

*2:$\lambda$ で表す文献もあると思います。空集合を $\emptyset$ ではなく $\{\}$ と書くように、空列を $()$ で表す状況もありそうです。

*3:Haskell などの関数型言語だったり、純粋関数型データ構造界隈だったりで使われている記法という印象があります。

*4:たぶんこれは一般的な記法ではないですが、$2^{|S|}$ のような記法同様に $|S!| = |S|!$ が成り立つことから、あまり非直感的な記法でもないでしょう。

*5:最悪時 $\Theta(n^2)$ 時間になるハッシュテーブルではどうなるか？ こちらは読者に任せます。

*6:実際には $|\Sigma|$ ではなく、$\Sigma$ のうち $S$ に含まれる要素の種類数で抑えられそうです。

*7:アルファベットサイズ $|\Sigma|$ は常に定数と見なせるわけではありません。「26 は比較的大きめだから定数ではない」のような主張はナンセンスで、値の大小自体は定数性とは無関係です。あくまで問題設定などによります。

*8:$A=0$ の場合は $n$ はどうしましょうか。$-\infty$ 桁と見なす宗派の人もおられそうです。

*9:逆向きの対応づけはちょっと考える必要がありますが、適切に行うことで可能です。

*10:$x$ 座標の昇順などでもよいです。好みの問題であることが多い気がします。

*11:$[0, i)$ に含まれているような区間だけを考えたいので右端を $i$ 以下としています。このような状況では、各区間を右端の昇順でソートしておくとよいことが多そうです。

配る DP・もらう DP の特徴づけに関して

典型的な DP の実装の属性の一つとして、配る DP・もらう DP と呼ばれているものがあります。 もらう DP を集める DP と呼ぶ派閥もあった気がしますが、ここでは名称についての議論はしません。

導入

初心者向けの解説の多くでは、ナップサック問題の DP などを例に出して、

for i in 0..n {
    for j in 0..=cap {
        dp[i + 1][j] = dp[i + 1][j].max(dp[i][j]);
    }
    for j in 0..=cap - w[i] {
        dp[i + 1][j + w[i]] = dp[i + 1][j + w[i]].max(dp[i][j] + v[i]);
    }
}

で更新するのが配る DP で、

for i in 1..=n {
    for i in 0..=cap {
        dp[i][j] = dp[i][j].max(dp[i - 1][j]);
    }
    for j in w[i - 1]..=cap {
        dp[i][j] = dp[i][j].max(dp[i - 1][j - w[i - 1]] + v[i - 1]);
    }
}

で更新するのがもらう DP ですーと説明されることが多そうな気がします。

よく「dp[i][j] が右辺にあるか左辺だけにあるか」とかで説明されがちな気がしますが、あまり本質的でない気がします。 ループの範囲を変えるだけで見かけ上は変わってしまうためです。

for i in 1..=n {
    for j in 0..=cap {
        dp[i][j] = dp[i][j].max(dp[i - 1][j]);
    }
    for j in 0..=cap - w[i - 1] {
        dp[i][j + w[i - 1]] = dp[i][j + w[i - 1]].max(dp[i - 1][j] + v[i - 1]);
    }
}

そもそも、ナップサック問題は単純な計算でできてしまうため、配る・もらうをうまく呼び分けるのが難しいというか、これを例に出して区別しようとするメリットが薄い気がします。 また、この例のせいで「配る・もらうはあくまで実装方針の違いだけで、どんな DP でも双方を行き来することが容易」のような感覚になりやすい気がします。

主張

$\gdef\DP{\operatorname{dp}}$

以下では、$\DP[i]$ のように添字が一つの DP のみを考えます。$\DP[i][j]$ のようなものについては、適宜 $\DP[i\times n+j]$ のように encode するなどして帰着させればよいです。必要に応じて、encode した整数を $\angled{i, j}$ のように表すことにします（$\DP[\angled{i, j}]$ など）。

$\DP[i]$ の計算をするために $\DP[j]$ の値を必要とするとき、$j\to i$ に辺を持つグラフを考えます*1。 DP の定義によっては、必ずしも（整数の意味での大小関係として）$j\lt i$ とは限らないことに注意しておきます。

(* note: 全体を書いてから Introduction to Algorithms を読み直したところ、上記の状況で $i \to j$ の辺を張るグラフが subproblem graph として記載されていました。書き直すのが大変なのでこのままにしておきます。*)

グラフに関して

グラフを知らない人へ： たとえば $y = x^2+1$ のようなグラフの話ではないです。いくつかの丸（頂点と呼ばれます）たちを、いくつかの矢印（辺と呼ばれます）で結んだり結ばなかったりして得られる絵のことだと思ってもらえばよいと思います。詳しく知りたい場合は「グラフ理論」とかでググるとよろしいです。

競プロ初心者で、「グラフ」に苦手意識がある人・グラフ関連のアルゴリズムがわからずに苦しんでいる人へ： ここではそういう話は出てこないので落ちついてください。あくまで頂点の集合と辺の集合を考えたいだけです。

頂点 $i$ に入ってくる辺を持つ頂点の集合を $\delta_-(i)$ と書くことにします。また、頂点 $j$ から出ていく辺を持つ頂点の集合を $\delta_+(j)$ と書くことにします。 つまり、$\DP[i]$ を計算するためには、各 $j\in\delta_-(i)$ に対して $\DP[j]$ が計算されている必要があるということです。 逆に、$\DP[j]$ を計算し終えたら、各 $i\in\delta_+(j)$ に対して $\DP[i]$ の計算に使う情報の一つがわかったことになります。

さて、グラフ自体は（実装によらず）DP の定義と入力ケースから定まりますが、そのグラフを得ることが簡単とは限りません。 すなわち、実装する上では次のことが大事になってきます。

  • $i$ から $\delta_-(i)$ を計算することは容易か？
  • $j$ から $\delta_+(j)$ を計算することは容易か？

ということです。前者が容易なときにそれを利用して求めるのが「もらう DP」、後者が容易なときにそれを利用して求めるのが「配る DP」という特徴づけができると思っています。 後者に基づくときでも、適切な順序で計算するなどして、$\DP[i]$ の計算時には各 $j\in\delta_-(i)$ の計算は終えていることを担保する必要があります（後述）。

もらう DP は $\DP[i] = f(\delta_-(i)) = f(j_1, j_2, \dots)$ のように、等式の形での記述と相性がよさそうです（$\DP[i]$ の計算の際はそれに従えばよい）。 一方、配る DP は $\DP[i] \gets g(\DP[i], \DP[j])$ のような更新を繰り返すため、そうした部分は苦手そうです。

もらう DP は “関数型” っぽくて配る DP は “手続き型” っぽいという見方もできそうです。 手続き型よりも関数型風の方が不変条件や正当性などを考えるときも楽そうなので、アルゴリズムの教科書などではもらう DP っぽい形式のものが多く書かれているような印象があります。気のせいかもしれません。

また、もらう DP では「複数のものからなにかを計算する処理」、配る DP では「複数のものに更新をする処理」が必要になり、$\delta_{\pm}$ の計算だけではなく、それらを実現するデータ構造との相性も重要です。一般に、前者タイプのデータ構造の方が充実している印象があります。

例

ナップサック問題

ナップサック問題の例では、$\DP[i][j]$ を「先頭 $i$ 個の商品のうち、重さが $j$ となる組合せの価値の最大値」とすると $(i, j) \to (i+1, j)$ および $(i, j) \to (i+1, j+w_i)$ の辺が各 $(i, j)$ に張られることになります。 すなわち、下記のように表せます（対象の範囲外になる辺は適宜無視することにします）。 $$ \delta_+(\angled{i, j}) = \{\angled{i+1, j}, \angled{i+1, j+w_i}\}. $$ 一方、逆向きも簡単に求めることができます。 $$ \delta_-(\angled{i, j}) = \{\angled{i-1, j}, \angled{i-1, j-w_{i-1}}\}. $$

よって、どちらに基づいた考えで実装しても大丈夫そうです。

Eratosthenes の篩

これを DP と見做している初心者はあまり多くないのかもしれませんが、DP と見做せます。 $\DP[i]$ の定義は、「$i$ が素数である」を意味する boolean です。

$i$ が合成数のときにふるう必要はないので、$\delta_+(i) = \emptyset$ と言えます。 $i$ が素数のときは、$\delta_+(i) = \{i\cdot j \mid j \gt 1\}$ です。 これらは容易に計算することができます。$\DP[i'] \gets \DP[i'] \wedge \DP[i]$ ($i'\in\delta_+(i)$) で更新するわけですね。

一方、$\delta_-(i)$ を容易に計算することは可能でしょうか。 これが可能であるのなら、そもそも篩なんてものを使わずに高速に素因数分解できてしまうんですよね*2。

よって、これは配る DP とは相性がよいですが、もらう DP とは相性がよくないわけです。 線形篩なども同様です。

回数の期待値・ゲームなど、操作を伴うもの

与えられた状態（盤面と呼んでもよい）から終状態に到達するまでの操作回数の期待値や、二人ゲームの勝敗判定（主に、操作できなくなった人が負け）などの問題は頻出です。 これらの問題設定においては、自明なケースは終状態です（それぞれ「期待値は 0」「その局面は負け状態」などとわかる）。 そのため、操作後の状態から操作前の状態に向かって辺が向かう形になります。 違和感を持つ人もいるようですが、“直感” に振り回されないようにしましょう。

さて、こうした問題設定においては、$\delta_-(s)$ は「盤面 $s$ から操作を一度したときの盤面（たち）」、$\delta_+(s)$ は「操作を一度することで盤面 $s$ にできる盤面（たち）」を指すことになります。 問題設定によってはどちらを考えることも可能でしょうが、操作が問題文で与えられることを考えると前者の方が自然になることが多い気がします。

終状態から $\delta_+$ を繰り返すことで初期状態に辿りつくのは自明ではなかったり、初期状態から到達できない無駄な盤面を計算してしまうことも多いです。 また、初期状態から $\delta_-$ を繰り返せば、初期状態から到達可能な盤面のみに絞ることができてうれしそうです。

$\delta_-$ であればメモ化再帰と相性がよいです。一般に、計算順序が自明でないときはメモ化再帰がよいことが多そうです。DP のグラフを DFS しているのに相当しそうです。 それで言うと BFS でもよさそうな気もしますが、あまりそういう実装をすることは少ないような気がします。

すごろくのような単純な設定では DP のグラフがパスグラフになるため、ゴールマスから順にループする実装の方が単純になることも多いでしょう。 ゲーム系に限らず、ループで簡単に書けるかどうかはグラフの形状によりそうですね。

最短距離

すみません、ここ怪しいです。簡単な例として負辺があるグラフ、トポソ不可能な有向グラフなどを考えるといろいろこわれそうです。ここの節はなかったことにしたいです。

Dijkstra 法も DP と見做せそうです。 DP の更新の順序は動的に決まりますが問題はないでしょう。

グラフの辺がそのまま $\delta_+$・$\delta_-$ になるので、グラフの表現の仕方によりそうですが、普通の隣接リストを持っていれば $\delta_+$ を計算する方が自然になりそうです。 ヒープから $i$ が取り出されれば $j\in\delta_-(i)$ に対して $\DP[j]$ が計算されたことになります（言うほど自明ではないような気がします）。

所感

よく「DP は DAG」などと言われますが、辺の計算の部分に着目しているものはあまり見なかったような気がしました。

See also:

いろいろな見方ができるようになると発想の幅も広がりそうです。

おわり

近いうちにまた DP のお話をする予定です。次は典型的な各種 DP に関するお話です。

*1:グラフの頂点集合は $\N$ の部分集合である必要はないので、$\DP[i][j]$ のようなタイプの DP でも $(i, j)\to(i', j')$ のようなグラフを考えてもよかったですね。あんまりここでの本質ではなさそうです。

*2:篩は素数判定だけでなく素因数分解もできるんですよね。

ABC-E をうめました

より正確には、ABC の A–E をうめました。

自己肯定感が低く、「何々をうめました」というときに「まだうめてなかったのか」という声が自分の中から聞こえてくるタイプの人もそれなりにいるのではないでしょうか。えびちゃんはそういう人です。 他の人がうめていなくても蔑んだりしないのに不思議です。

ふりかえり

E をうめようと思ってから解いた問題を挙げてみます。多少のネタバレを含む場合があります。

  • ABC 163 E - Active Infants
    • 当時は天才発想だと思ったが、落ちついて考えると解けた
    • feasible な解を固定して、隣同士を swap してみると方針が立った
  • ABC 204 E - Rush Hour 2
    • 当時は下手な三分探索をしようとしてこわした記憶がある
    • 待ち時間を全探索するとつらそうなので、手計算したら解の構造がわかった
    • 今見ている頂点から時刻 $t$ で出発しても $t+1$ で出発しても到着時刻が変わらない場合、$t$ で出発しても損しない
    • 解説と off-by-one が異なるケースがありそうだったので計算をがんばって、記事 も書いた
  • ABC 207 E - Mod i
    • 当時は頭のいい DP だと思って、自力だと無理だと思った
    • この手のやつは dp[i 個見て][j ブロックで][総和が k と合同] とかじゃんという先入観があった
    • ブロックとして valid なものだけ考えるような遷移をできるじゃんと思い至るのにだいぶかかった
    • DP の遷移を表すグラフを考えると、(総和 mod ブロック番号) の同値類ごとに完全グラフの有向版みたいな感じがある
    • 辺の最大ケースは $a_i = 0$ になりそうだが、制約を考えると $a_i = \lcm_{1\le j\le 36} j$ とかになりそう
    • 結局は想定解とほぼ同じようであった。配り方はちょっと違うかも
  • ABC 212 E - Safety Journey
    • 行列累乗か？（過学習）と思ったがだめそう
    • $\bar{G}$ 上でなんかをするので、完全グラフと元の疎なグラフをうまいこと合わせてなんかやるんだろうなという感じ
    • 結構悩んだが、一回の遷移でどうなるかを愚直に書いてみてわかったと思う
      • $n\le 3$ とかのケースも考えてみた
  • ABC 213 E - Stronger Takahashi
    • あんまりやる気がしなくて放置していただけ、特に感想なし
  • ABC 227 E - Swap
    • むずかしかった
    • 全部で $3^{30}/10!^3$ 通りあって列挙はつらそう
    • 転倒数は $O(n^2)$ なので操作回数が多いのは見かけ倒し。そういうのしばしばある
    • 先頭から文字を決めていくとして、次に特定の文字を持ってくるまでの操作回数は、使った文字を数えておけばわかる
      • 操作回数で分類すればよさそうで、最短の操作を採用することで重複もなくせる
    • 次を持ってくるまでの操作回数は前計算したが、毎回やっても大丈夫という想定だったらしい
  • ABC 231 E - Minimal payments
    • 愚直にやっちゃだめでしょうという見た目をしているが、慣れていないと愚直にやってしまいそう
    • 特定の硬貨を一つ上の硬貨にしたときに、解がどういう変化をするかを考えた
    • $X$ 円ちょうど払う場合と比べて、（払い手側が）特定の硬貨を 2 枚以上多く使うことはない
    • 硬貨 $i$ を $j$ 枚多く使った、とかで分類した
  • ABC 243 E - Edge Deletion
    • 三角不等式
    • ねむかったので謎のことをして変になった
4 4
1 2 1
2 3 1
3 4 1
1 4 3
  • ABC 249 E - RLE
    • 圧縮前が $i$ 文字で圧縮後が $j$ 文字とかで DP でしょうという感じ
    • とりあえず愚直に遷移を書くが、区間に足す感じにできるので on-the-fly で imos しましょう
  • ABC 260 E - At Least One
    • $(A_i, B_i)$ に辺があるグラフを考える？と一瞬思ったが、区間 $[A_i, B_i]$ を考えるのがよさそうだった
    • 左端で分類して、固定した左端に対して valid になる選び方を考えた
  • ABC 262 E - Red and Blue Graph
    • これが一番しんどかった。いろいろ迷走した
      • 先頭 $i$ 個見て $j$ 個を赤にして、異なる色を結ぶ辺の偶奇を持つ？？そんなんできなくない？？
      • 辺の寄与を考える？ 頂点の制約を考えられなくない？？
    • 結局、解説の先頭一文だけ読んだら残りはわかった
  • ABC 265 E - Warp
    • これが二番目にしんどかった
    • 最初に踏む障害物を固定したら包除みたいにできる？と思ったが、重複がやばそう（包除パートを高速にできなさそう）
    • とりあえず一次元の場合（$B=D=F=0$）とかを考える？と思ったが、あまりうれしくない
    • 操作の個数が一つ、二つの場合（$(A, B)$ だけ、$(A, B)$, $(C, D)$ だけ）を考えたところ、あーとなった
      • 具体的な経路全体の集合がどうなるかを考えた
    • 「$300\times 10^5$ はぎりぎりなんとかなるか？」と最初考えていたが、素直に $300^3$ を考えてみるのが無難そう
      • あまりそういうメタ読みっぽいのは好きではないが、メタ読みをせずに固執するのも賢くなかろうので
  • ABC 309 E - Family and Insurance
    • 当時事情があって忙しくて放置していただけ。特に感想なし
  • ABC 313 E - Duplicate
    • 具体例を挙げて考えた。
    • 2 以上が連続すると発散するのでだめ → `1...1 x 1...1 x ... のような形式になる
    • 1...1, 1...1 x, 1...1 x 1 ... のように、順々に操作回数を考えた
    • 結果的に RLE して実装したが、各数字の答えへの寄与を考えることで、RLE は不要になるらしい
      • そういうのちゃんと考えられるようになるとよさそうね
      • Zero-Sum Ranges で、予め全部の個数を数えるか、on-line で個数を更新しながらやるかの方針の違いみたいな
  • ABC 146 E - Rem of Sum is Num
    • これは昔解いてたけど当時あまりわかってない感があったので解き直し
    • 区間 $[l, r)$ を固定したときの値を実際に書いてみた
      • $(\sum_{i=l}^{r-1} a_i)\bmod k = r-l$
    • $s(n) \triangleq (\sum_{i=0}^{n-1} a_i)\bmod k$ としてみる
      • $s(l) \le s(r)$ なら、$s(r)-s(l) = r-l$
      • $s(l) \gt s(r)$ なら、$s(r)-s(l)+k = r-l$
    • $s(r)-r = s(l)-l$ とか $s(r)-r+k = s(l)-l$ みたいに変数分離
    • 左辺は $k$ 未満なので、古い区間を捨てながら順に見る

考えたい操作だったり解だったりを、適当に固定して探ってみるといいのかなと思いました。 あとは contribution を考えたりとか。 愚直な DP を考えたりそれ以外をすることで、解ける形に帰着できることに気づけたりするかも。 DP するときは、状態がどう分類されるかを意識するとよさそう。

ABC 313 F - Flip Machines も解きました。

  • グラフとして考える
  • 期待値の線形性からいい感じにできる
    • 実際に計算してみると単純な形になると気づく
    • もしかしたら計算する前に気づくべきことなのかも
  • カードを $D_i = B_i-A_i$ に言い換える
    • 自己ループを持つ頂点は予め答えに $D_i$ を足して $D_i \gets -D_i$ で更新しておく
  • $D_i$ の正負で頂点集合を分ける
  • それぞれの頂点集合のサイズを $n_+$, $n_-$ としたとき、$\min(n_+, n_-)\le 20$ とわかる
    • 大きくない方を基準にして別々のアルゴリズムを構築すればよさそう
  • 片方は貪欲でよさそう、もう片方は？？

このあたりまでは自力でできました。フローをがんばる？とか無理じゃん？とかいろいろ考えたあと解説を見ました。 上記の流れがそのまま載っていたのでうれしくなりましたが、残り一歩を思いつけなかったのが悔しいです。

自信のない考察をしているとき、その方針でいいのか不安になって、解説とかに頼って「あってるよ」というのを得ないと進めない癖がありました。 6 問時代の ABC の頃にだいぶ訓練して克服したつもりでいたのですが、今回は負けた気がします。

どうやら difficulty が 3100 だったらしいというのを見て、（ほぼ）自力でできたのでうれしかったです。difficulty 信仰はあまり好きではないつもりだったのですが、人間なんてのは単純なものですね。 とはいえコンテスト中に解き切れる自信はあまりない気がします。

おわり

ABC-F もうめたいです。

平方根と整数除算まわりの性質メモ

ABC 204 E に関連します。

定義

表記 意味 例
$\floor{x}$ $x$ 以下の最大の整数 $\floor{3.1} = 3$, $\floor{2.7} = 2$, $\floor{-2.2} = -3$, $\floor{2} = 2$
$\ceil{x}$ $x$ 以上の最小の整数 $\ceil{3.1} = 4$, $\ceil{2.7} = 3$, $\ceil{-2.2} = -2$, $\ceil{2} = 2$
$\rounded{x}$ $x$ に最も近い整数 $\rounded{3.1} = 3$, $\rounded{2.7} = 3$, $\rounded{-2.2} = -2$, $\rounded{2} = 2$

ただし、ここでは、整数 $n$ に対して $\rounded{n + 0.5}$ は未定義とします。すなわち、以下のスタンスということです。

  • この記事中で $\rounded{x}$ を考えるときは $x - \floor{x} \neq 0.5$ を示す必要がある。
  • $\rounded{n + 0.5} = n$ あるいは $\rounded{n + 0.5} = n + 1$ のように拡張した関数でも、この記事で示した性質は成り立つ。

定理と補題たち

Lemma 1: $\ForallL{n\in\N}{\sqrt{n}-\floor{\sqrt{n}} \neq 1/2}$

Proof

背理法による。 ある非負整数 $n$ に対し、整数 $m$ が存在して $\sqrt{n} = m+1/2$ が成り立つと仮定する。 $$n = (m+1/2)^2 = m^2+m+1/4$$ より、$n\in\Z$ かつ $n\notin\Z$ が成り立つので矛盾。$\qed$

Lemma 2: $$ \ForallL{x\in\R}{x\ge 0\implies -\tfrac12+\sqrt{\tfrac14+x}\le \sqrt{x} \lt \left(-\tfrac12+\sqrt{\tfrac14+x}\right)+\tfrac12} $$

Proof

右側は $\sqrt{x} \lt \sqrt{x+\tfrac14}$ より明らか。以下、左側を示す。 $$ \begin{aligned} -\tfrac12 + \sqrt{\tfrac14 + x} &\le -\tfrac12 + \sqrt{\left(\tfrac12+\sqrt{x}\right)^2} \\ &= -\tfrac12 + \left|\tfrac12 + \sqrt{x}\right| \\ &= \sqrt{x}. \qquad\qed \end{aligned} $$

Theorem 3: $$ \ForallL{n\in\N}{\Ceil{-\tfrac12+\sqrt{\tfrac14+n}} = \rounded{\sqrt{n}}} $$

Proof

任意に固定した $n\in\N$ に対し、$m = \Ceil{-\tfrac12+\sqrt{\tfrac14+n}}$ とする。 このとき、$m-\tfrac12 \lt \sqrt{n} \lt m+\tfrac12$ を示せばよい。

右側は Lemma 2 から従うので、以下では左側を示す。 $n = 0$ のとき明らかに成り立つので、以下 $n \gt 0$ とする。このとき $m \ge 1$ であることに注意する。 $m$ の定義から $m-1 \lt -\tfrac12 + \sqrt{\tfrac14+n}$ なので、 $$ \begin{aligned} m-1 &\lt -\tfrac12 + \sqrt{\tfrac14+n} \\ m - \tfrac12 & \lt \sqrt{\tfrac14+n} \\ n & \gt (m-\tfrac12)^2-\tfrac14 \\ &= m^2-m \end{aligned} $$ となる。整数性より $n\ge m^2-m+1$ なので、 $$ \begin{aligned} n &\ge m^2-m+1 \\ &\gt (m-\tfrac12)^2 \\ m-\tfrac12 &\lt \sqrt{n}.\qquad\qed \end{aligned} $$

Lemma 4: $\ForallL{n\in\N}{n\le \floor{\sqrt{n}}\floor{\sqrt{n}+1} \iff \sqrt{n} \lt \floor{\sqrt{n}}+\tfrac12}$

Proof

$m = \floor{\sqrt{n}}$ とおく。

($\implies$) 対偶を示す。$\sqrt{n}\ge m+\tfrac12 \implies n \gt m(m+1)$ を示す。 $$ \begin{aligned} n &\ge (m+\tfrac12)^2 \\ &= m^2+m+\tfrac14 \\ &\gt m(m+1). \end{aligned} $$

($\impliedby$) $\sqrt{n}\lt m+\tfrac12 \implies n \le m(m+1)$ を示す。 $$ \begin{aligned} n &\lt (m+\tfrac12)^2 \\ &= m^2 + m + \tfrac14 \end{aligned} $$ 整数性より、$n \le m^2+m$ が従う。$\qed$

Lemma 5: $$\ForallL{n\in\N}{n\gt 0, n\le\floor{\sqrt{n}}\floor{\sqrt{n}+1} \implies \frac{n}{\floor{\sqrt{n}}} \le \frac{n}{\floor{\sqrt{n}+1}} + 1}$$

Proof

$m = \floor{\sqrt{n}}$ とおく。対偶を考える。 $n/m \gt n/(m+1)+1 \implies n\gt m(m+1)$ を示す。 $$ \begin{aligned} n(m+1) &\gt nm + m(m+1) \\ n &\gt m(m+1). \qquad\qed \end{aligned} $$

Lemma 6: $$\ForallL{n\in\N}{n\gt 0, n\le\floor{\sqrt{n}}\floor{\sqrt{n}+1} \implies \Floor{\frac{n}{\floor{\sqrt{n}+1}}} \lt \Floor{\frac{n}{\floor{\sqrt{n}}}}}$$

Proof

$m = \floor{\sqrt{n}}$ とおく。$n = m(m+1)$ のときは明らかなので、$n \lt m(m+1)$ とする。 $n\lt m(m+1) \implies \floor{\tfrac{n}{m+1}} \lt \floor{\tfrac nm}$ を示す。

$m = \floor{\sqrt{n}}$ より、$m^2 = \floor{\sqrt{n}}^2 \le n$ であり、 $$ \Floor{\frac{n}{m+1}} \lt \frac{n}{m+1} \lt m \le \frac nm $$ となる。整数性より $m\le \floor{\tfrac nm}$ であり、$\floor{\tfrac{n}{m+1}}\lt \floor{\tfrac nm}$ が従う。$\qed$

Theorem 7: $$\ForallL{n\in\N}{n\gt 0, \Floor{\frac{n}{\floor{\sqrt{n}+1}}} + \floor{\sqrt{n}+1} = \Floor{\frac{n}{\rounded{\sqrt{n}}}} + \rounded{\sqrt{n}}}$$

Proof

$\floor{\sqrt{n}}+\tfrac12 < \sqrt{n}$ のとき $\floor{\sqrt{n}+1} = \rounded{\sqrt{n}}$ であり、明らかに成り立つ。 以下、$\sqrt{n} \lt \floor{\sqrt{n}}+\tfrac12$ とする。 このとき、$\rounded{\sqrt{n}} = \floor{\sqrt{n}}$ なので、以下を示せばよい。 $$ \sqrt{n} \lt \floor{\sqrt{n}}+\frac12 \implies \Floor{\frac{n}{\floor{\sqrt{n}+1}}} + 1 = \Floor{\frac{n}{\floor{\sqrt{n}}}}. $$ $m = \floor{\sqrt{n}}$ とおく。Lemma 4 より、$$n\le m(m+1) \implies \Floor{\frac{n}{m+1}}+1 = \Floor{\frac{n}{m}}$$ を示せばよい。 Lemma 5 から $$ \Floor{\frac nm}\le \frac nm\le \frac{n}{m+1}+1. $$ Lemma 6 および整数性から $$ \Floor{\frac{n}{m+1}}\le \frac{n}{m+1}\lt \Floor{\frac nm} $$ なので、 $$ \Floor{\frac nm}\le \frac{n}{m+1} + 1 \lt \Floor{\frac nm} + 1 $$ が成り立つ。 すなわち、$\floor{\frac nm} = \floor{\frac{n}{m+1}}+1$ となる。$\qed$

Claim 8: $$\ForallL{n\in\N}{n\gt 0 \implies \floor{\sqrt{n}}\le \Floor{\frac{n}{\floor{\sqrt{n}}}} \le \floor{\sqrt{n}+2}}$$

Proof $m = \floor{\sqrt{n}}$ とおく。$m \le \sqrt{n} \lt m+1$ と整数性より $m^2\le n\le m^2+2m$ が成り立つ。よって $m\le \floor{n/m}\le n/m\le m+2$ が従う。

系

Corollary 9: Theorem 7 より、ABC 204 E 公式解説 の中で $t = \rounded{\sqrt{D}}-1$ を使っている部分で、代わりに $t = \floor{\sqrt{D}}$ を使うことができます。

Corollary 10: 二分探索を用いることで、整数の範囲で（浮動小数点数の演算を経由せず）$\floor{\sqrt{n}}$ を求められることは有名ですが、Lemma 4 を利用することで $\rounded{\sqrt{n}}$ も整数の範囲で求めることができます。

fn rounded_sqrt(n: u64) -> u64 {
    let floor_sqrt = floor_sqrt(n); // よしなに
    match floor_sqrt.overflowing_mul(floor_sqrt + 1) {
        // n > floor_sqrt * (floor_sqrt + 1) なら floor_sqrt + 1 と等しい
        (mul, false) if n > mul => floor_sqrt + 1,
        // そうでない場合（積がオーバーフローした場合も含む）は floor_sqrt と等しい
        _ => floor_sqrt,
    }
}

その他

一応確認として $1\le n\le 10^9$ の範囲で諸々の命題が成り立つことを確認していたのですが、整数の平方根の計算（指数探索による）を含む場合は 30 秒程度、浮動小数点数の計算のみの場合は 3 秒程度で済んだのでびっくりしました。

競プロをしているときの雑な感覚だと、$10^9$ 回程度の演算はそれなりの時間がかかりそうな気がしちゃうので（30 秒はそれなりの時間であるという見方もあるかも）。

証明を別のところで下書きしてから記事を書き始めたのですが、下書きの Lemma 4 の証明がこわれていて焦りました。

おわり

おわりです。久々に高校数学をやった気がしました。半年前は商の微分とかをやっていました。

rsk0315.hatenablog.com