abc172e

NISHIO Hirokazu [Translate]
ABC172E
E - NEQ


-----
数え上げ問題をみて、動的計画法かな？と思ったが余事象を引く方が楽なパターン

最近、一周回って「まずは素朴に書いていいんじゃない？」って思うようになってきた。問題文を読み間違えてる時に素早く気づけるし、TLEしたので複雑なアルゴリズムを書く場合にもテストコード生成させられる
pythondef blute(N, M):
    """
    >>> blute(2, 2)
    2

    >>> blute(2, 3)
    18
    """
    from itertools import permutations
    nums = range(M)
    count = 0
    for a in permutations(nums, N):
        for b in permutations(nums, N):
            if all(a[i] != b[i] for i in range(N)):
                count += 1
    print(count)

pythonfor M in range(1, 10):
    for N in range(1, M + 1):
        print("N, M, f = ", N, M, blute(N, M))

:N, M, f =  1 1 0
N, M, f =  1 2 2
N, M, f =  2 2 2
N, M, f =  1 3 6
N, M, f =  2 3 18
N, M, f =  3 3 12
N, M, f =  1 4 12
N, M, f =  2 4 84
N, M, f =  3 4 264
N, M, f =  4 4 216
N, M, f =  1 5 20
N, M, f =  2 5 260
N, M, f =  3 5 1920
N, M, f =  4 5 6360
N, M, f =  5 5 5280
N, M, f =  1 6 30
N, M, f =  2 6 630
N, M, f =  3 6 8520
N, M, f =  4 6 65160
N, M, f =  5 6 222480
N, M, f =  6 6 190800
N, M, f =  1 7 42
N, M, f =  2 7 1302
N, M, f =  3 7 28140
N, M, f =  4 7 390600
N, M, f =  5 7 3059280

f(N, M)
f(1, M) = M * (M - 1)

pythonfor M in range(2, 100):
    r1 = blute(1, M)
    r2 = blute(2, M)
    r3 = blute(3, M)
    debug("r2/r1, r3/r2, r3/r1", r2/r1, r3/r2, r3/r1)

:r2/r1, r3/r2, r3/r1 1.0 0.0 0.0
r2/r1, r3/r2, r3/r1 3.0 0.6666666666666666 2.0
r2/r1, r3/r2, r3/r1 7.0 3.142857142857143 22.0
r2/r1, r3/r2, r3/r1 13.0 7.384615384615385 96.0
r2/r1, r3/r2, r3/r1 21.0 13.523809523809524 284.0
r2/r1, r3/r2, r3/r1 31.0 21.612903225806452 670.0
r2/r1, r3/r2, r3/r1 43.0 31.674418604651162 1362.0
r2/r1, r3/r2, r3/r1 57.0 43.719298245614034 2492.0
r2/r1, r3/r2, r3/r1 73.0 57.75342465753425 4216.0
r2/r1, r3/r2, r3/r1 91.0 73.78021978021978 6714.0
r2/r1, r3/r2, r3/r1 111.0 91.8018018018018 10190.0

:In [11]: xs = np.array([0.0, 2.0, 22.0, 96.0, 284.0, 670.0, 1362.0, 2492.0])
In [12]: xs[1:] - xs[:-1]
Out[12]: array([   2.,   20.,   74.,  188.,  386.,  692., 1130.])
In [14]: dxs = xs[1:] - xs[:-1]

In [15]: dxs[1:] - dxs[:-1]
Out[15]: array([ 18.,  54., 114., 198., 306., 438.])
In [16]: ddxs = dxs[1:] - dxs[:-1]

In [17]: ddxs[1:] - ddxs[:-1]
Out[17]: array([ 36.,  60.,  84., 108., 132.])
In [19]: dddxs = ddxs[1:] - ddxs[:-1]

In [20]: dddxs[1:] - dddxs[:-1]
Out[20]: array([24., 24., 24., 24.])
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at 11/23/2025, 5:15:23 PM[Edit]
Related Pages
