みなさんお久しぶりです。研究室配属及び大学の全試験を終了し,春休みを迎えたswapmanです。最近また緑に舞い戻ったのですが, 運だけ感も若干否めないので気を引き締めてまた頑張っていきます。ということで, 春休み一発目は単調増加数列の数え上げ方について軽くまとめてみました。自分の覚書でもあるので,多少の雑さ加減はお許しを。それでは本編です。
単調増加数列の数え上げと組み合わせ
まず単調増加数列は2種類存在し,それは広義単調増加数列と狭義単調増加数列です。(広義の方はA[i-1] = A[i]を許容する場合のことを指します。)説明はこれくらいにして, 具体的な説明に入ります。まずは狭義単調増加数列について考えましょう。
狭義単調増加数列の場合
1 < A < B < C < D < E < .... α < β < Γ <= M のような数列を考えます。 この数列の中からN個の数字を選ぶ時, 狭義単調増加数列はいくつ存在するか？という問題を考えます。 まず適当にN個選ぶ時の場合の数はM×(M-1)×(M-2)×...(M-N+1)です。このうち1つの組み合わせに対してN!個の重複があるから, 題意の狭義単調増加数列の数は, (M) Choose(N) となります。この考え方を応用して広義単調増加数列についても考えてみましょう。
広義単調増加数列の場合
1 <= A <= B <= C <= D <= E <= .... α <= β <= Γ <= M のような数列を考えます。 この数列の中からN個の数字を選ぶ時, 広義単調増加数列はいくつ存在するか？という問題を考えます。 狭義単調増加数列の場合と同様に考えるべく題意の式を少し変形しましょう。 X=A, Y=B+1, Z=C+2...とすると題意の式は,1 <= X < Y < Z < .... <= M+N-1のように変形できます。これは先ほど示した狭義単調増加数列の問題と全く同じであるから, (M+N-1)Choose(N) とできます。よって広義でも狭義でも結局は 組み合わせ理論に帰着する ことがわかります。この記事とかおすすめです。https://betrue12.hateblo.jp/entry/2020/05/02/233025
補足
この考え方を使って解く問題の一例に次の問題があります。
https://atcoder.jp/contests/abc165/tasks/abc165_c
この問題の解説放送では, 全く違う解説の仕方をしているので参考にするといいでしょう。
解説放送のリンク：https://www.youtube.com/watch?v=C5_NnCp1CRI&feature=youtu.be