ABC171 F

最大長100万の英小文字列の好きな場所に最大100万回英小文字を挿入して、できる可能性のある文字列を数え上げる問題。問題文

コンテスト中の思考

残り45分
- 短い文字列の場合を調べて規則性を見出してからDPだろう
- よーし、具体的な文字列の内容と関係なく、長さNで文字種Kの文字列に1文字追加すると、以下の関係が成り立つ！
  - f(N+1, K+1) = (26 - K) * (N + 1) * f(N, K)
  - f(N+1, K) = ((K - 1) * (N + 1) + 1) * f(N, K)
- DPしよう
  - 合流が起きるぞ
  - マスを四角く並べて隅から順に塗りつぶす…
  - あれ、これ100万×100万のオーダーでは？？
この時点で残り15分
- 実際に短い文字列に対してプログラムで全パターン列挙して数えるのをやらせて、パターンを発見しようとしているうちに時間切れ

解説を読んでからコンテスト後

- 文字列の先頭に文字を挿入することを考えると25倍
  - 先頭文字と同じものを挿入するのは、2文字目に挿入するのと区別がつかないからカウントしてはいけない
  - よって26文字から1文字引いて25
- この挿入の後に、さらに前に文字を挿入してはいけない
  - それは挿入順を入れ替えたものと区別がつかないから
  - 一般に、挿入した文字の挿入タイミングを入れ替えたものは同一なので、順列ではなく組み合わせになる必要がある
  - 重複ありなのでcombinations with replacement(日本語でなんというのかは忘れた)
- カーソルの位置をN、追加する文字数をKとした時に、追加するか、カーソルを進めるか、の二択を繰り返していって0,0になればゴール
- よく見たら途中の道はどこを通っても25倍なので、右下の26倍の道に入るタイミングで場合わけしたらよさそう
- 最初から26倍の道に入るのは1通り
- 1個25を取ってからから入るのはN-1通り
  - 図では2通り
  - (とこの時点では考えたが、長さNの文字列に対する挿入ポイントはN+1あるので本当はN通り、伏線A)
- 2個25を取るのは、重複ありで2個選ぶコンビネーション
  - 図では3通り
- というわけで求める値は
  - $\sum_{i=0}^K 25^i 26^{K-i} C^R(N-1, i)$
早速計算してみるが、サンプル1の答えが合わない
- NやKをひとつずらして試してみたらNをひとつ増やした時に正解になることがわかったのでそれでいいやということにした(おいおい
  - $\sum_{i=0}^K 25^i 26^{K-i} C^R(N, i)$
- この解説を書いてる時に理由がわかったので結果オーライ、伏線A回収

サンプル1に正解するコード python

K = 5
S = "oof"
P = 10 ** 9 + 7
N = len(S)


def factorial(n):
    ret = 1
    for i in range(2, n + 1):
        ret *= i
    return ret


def comb_rep(n, r):
    return factorial(n + r - 1) // factorial(r) // factorial(n - 1)


ret = 0
for i in range(K + 1):
    ret += (
        (25 ** i) *
        (26 ** (K - i)) *
        comb_rep(N, i)
    )
print(ret)

そのままサンプル2を入力してみたら時間がかかる
- そりゃそうでしょうね、剰余を取ってないのですごく桁の大きい長整数演算してるのだろう
- 右の3つの値を剰余取りながらテーブルに書いて再利用しよう $25^x, 26^x, x!$
サンプル2が十分な速度で計算できるようになったがなぜか答えが違う…
- 剰余を取ってから加減算と乗算をするのは許されるけどコンビネーションの中でやってる整除は許されない
- 競プロでよく使う二項係数(nCk)を素数(p)で割った余りの計算と逆元のまとめ | アルゴリズムロジック
  - なるほど逆元を求めておけば乗算で割り算ができるわけか
- よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方 - けんちょんの競プロ精進記録
  - inv[a] = MOD - inv[MOD % a] * (MOD / i) % MOD;
  - この式を使えばO(1)で逆元求まるのでO(N)で逆元テーブルが作れる
  - 漸化式の導出はちゃんと考えてない
    - 追記: 剰余群逆元漸化式の導出
  - とりあえずこれを使うことでサンプル2は正解できた

python

    f = 1
    invf = 1
    for i in range(2, N + K):
        f *= i
        f %= P
        F[i] = f
        q, r = divmod(P, i)
        INV[i] = -INV[r] * q % P
        invf *= INV[i]
        invf %= P
        INVF[i] = invf

サブミットしてみたらTLEだった
- 数値計算の塊だからよく効くだろうとnumbaでコンパイル
- AC https://atcoder.jp/contests/abc171/submissions/14596326
手元での速度比較 :

pure python
real    0m2.910s
user    0m2.781s
sys     0m0.124s

compiled with numba
real    0m0.363s
user    0m0.683s
sys     0m0.139s

numbaでどれくらい速くなるのか測ってみたのだが、userがrealを超えてるな…なにも考えてないPythonのコードがマルチスレッド(GIL OFF)で走るということ？？

#atcoder #ABC171

(C)NISHIO Hirokazu / Converted from Markdown (ja)
Source: [GitHub] / [Scrapbox]