−目次

エイシングプログラミングコンテスト 2020 C,D,E,F問題メモ

エイシングプログラミングコンテスト 2020 C,D,E,F問題メモ

エイシングプログラミングコンテスト 2020

決してお肉を熟成させたり、新品のヘッドホンに謎の音を流し続ける企業ではない。

C - XYZ Triplets

問題

$f(n)$ を、以下の条件を満たす1以上の整数の組 $(x,y,z)$ の個数とする
条件
- $x^2+y^2+z^2+xy+yz+zx=n$
$N$ が与えられるので、 $f(1),f(2),...,f(N)$ をそれぞれ求めよ
$1 \le N \le 10^4$

解法

因数分解とかしてみたくなる形だが、あんまり綺麗にならない。

$N$ の制約は $10^4$ 。条件の式の左辺では $x,y,z$ それぞれ2乗していて、他の要素も全て正なので、どれかが $10^2$ を超えた時点で、もう全体の合計は $10^4$ を超えてしまう。

なので、 $x,y,z$ は $1～100$ の値しか取らない。これを全探索しても $10^6$ で収まり、十分間に合う。

        
              n = int(input())
ans = [0] * (n + 1)
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            d = x * x + y * y + z * z + x * y + y * z + z * x
            if n >= d:
                ans[d] += 1
            else:
                break
 
print('\n'.join(map(str, ans[1:])))

D - Anything Goes to Zero

問題

$popcount(n)$ を、「 $n$ を2進表記したときの1の個数」とする
$f(n)$ を、「 $n$ を $popcount(n)$ で割った余りに置き換えるという操作を繰り返した際に $n=0$ となるまでの操作回数」とする
2進表記で $N$ 桁の整数 $X$ が与えられる
$X$ の上から $i=1～N$ 桁目のビットを反転した整数を $X_i$ とする
$f(X_1),f(X_2),...,f(X_N)$ をそれぞれ求めよ
$1 \le N \le 2 \times 10^5$

解法

多倍長の出番！

$X$ が馬鹿でかいが、

$A$ を $B$ で割った余りは、 $B$ 未満にしかならない
$popcount(n)$ は、たかだか $\log{n}$

なので、操作を繰り返すたびに猛烈な勢いで小さくなる。たとえば、 $N$ が最大値でも1回操作するだけで $X \le 2 \times 10^5$ 、2回の操作で $X \le 16$ となる。 ¹⁾

なので、愚直にやっても数回で操作は終わる。特に、 $X \le 2 \times 10^5$ まで $f(X)$ を事前計算なりメモ化なりしておけば、2回目以降の操作結果はそれを参照すればよくなる。

さて、最初の1回の計算だが、これは工夫する必要がある。いくら多倍長整数をPythonが扱えるとはいえ、割り算は桁数に比例した時間がかかるので、1回で $O(N)$ 、これを各桁を反転させた数で毎回やると $O(N^2)$ となる。

できるだけ、最初の1回（ $N$ 桁の整数を割る）の処理回数は少なくしたい。

なるべく事前計算で共通化できる部分を探すと、

各 $X_1,X_2,...$ で反転させるビットは1箇所だけなので、オリジナルの $popcount(X)$ を $d$ とすると、 $popcount(X_i)$ は $d+1$ か $d-1$ のどちらか
$X$ の $i$ 桁目が '0' だった場合、 $X_i = X + 2^{N-i}$
$X$ の $i$ 桁目が '1' だった場合、 $X_i = X - 2^{N-i}$

なので、 $X \% (d+1)$ と $X \% (d-1)$ を事前計算しておけば、あとは $2^{N-i} \% (d \pm 1)$ の差分更新のみで $X_i \% (d \pm 1)$ は求められる。

$X$ の $i$ 桁目が '0' の時
- $X_i \% popcount(X_i) = X_i \% (d+1) = (X \% (d+1) + 2^{N-i} \% (d+1)) \% (d+1)$
$X$ の $i$ 桁目が '1' の時
- $X_i \% popcount(X_i) = X_i \% (d-1) = (X \% (d-1) - 2^{N-i} \% (d-1)) \% (d-1)$

$2^{N-i}$ は、 $2^0$ から順に2をかけて $10^9+7$ で割ってを繰り返して $O(N)$ で事前計算しておける。Pythonでは pow() を使ってもよい。

これで最初の1回の操作後の $X_i$ を求められた。この時点で最初に述べた通り $X_i \le 2 \times 10^5$ になっているはずなので、後はそのまま求めても十分高速である。

ただし、 $X$ で元から立ってる '1' が1個しか無かった場合、 $d-1$ がゼロ除算とならないよう、注意。（その時は $X_i=0$ なので、 $f(X_i)=0$ である）

        
          
          
              
              from functools import lru_cache
 
 
@lru_cache(maxsize=None)
def f(x):
    if x == 0:
        return 0
    return f(x % bin(x).count('1')) + 1
 
 
n = int(input())
x = input()
d = x.count('1')
y = int(x, base=2)
y0 = y % (d + 1)
y1 = y % (d - 1) if d > 1 else 0
buf = []
 
for i in range(n):
    if x[i] == '0':
        m = d + 1
        z = (y0 + pow(2, n - i - 1, m)) % m
    else:
        m = d - 1
        if m == 0:
            buf.append(0)
            continue
        z = (y1 - pow(2, n - i - 1, m)) % m
    buf.append(f(z) + 1)
 
print('\n'.join(map(str, buf)))

            

        
      

E - Camel Train

問題

ラクダが $N$ 頭いる。これを好きな順に1列に並べる
$i=1～N$ について、以下の情報が決まっている
- ラクダ $i$ は、左から $K_i$ 番目以内にいれば $L_i$ 、そうでなければ $R_i$ の得点を得る
並べる順番を上手く決めて得られる得点の総和の最大値を求めよ
テストケースは $T$ 個与えられるので、それぞれについて求めよ
$1 \le T \le 10^5$
$1 \le N \le 2 \times 10^5$
1つの入力ファイルの $N$ の総和 $\le 2 \times 10^5$

解法

$L_i$ と $R_i$ 、置けるならなるべく得点の高くなる方に置きたい。

なので、この2つでグループ分けする。

以下、 $L_i \ge R_i$ （なるべく $K_i$ 番目以内に置きたい）を考える。

$K_i$ が小さく、置ける範囲が限定されている方から置いていく。説明のため、この順に $i$ を振りなおす。

i    1   2   3   4   5   6
Ki   1   2   2   4   4   4

Li  10   4   5  20   2   7
Ri   5   2   2  16   1   1
L-R  5   2   3   4   1   6

上記の例で、 $i=1,2$ までは特に問題なく置ける。

$i=3$ のとき、もう $K_3=2$ 番目までに2頭のラクダが置かれているので、ラクダ $3$ を諦めるか、既に置かれたラクダのどれか1頭を諦めるかしないといけない。

これは、「採用するのを $L_i$ から $R_i$ にしたときの減点が一番ましなもの」から選ぶとよい。つまり、 $L_i-R_i$ の優先度キューを持っておいて、一番小さいものを諦めればよい。

この場合はラクダ2を諦めるのがよいので、暫定の並びは以下のようになる。ラクダ2は、好きな位置に置いてよい。（1,3も、 $K_i$ の条件が満たされてたら特にこの順でないといけない、というものではない。視覚的な並びをわかりやすくするための一例として。）

ラクダ   1  3  ...  2 
得点    L1 L3      R2

$i=4,5$ は、再び問題なく置ける。

ラクダ   1  3  4  5  ...  2 
得点    L1 L3 L4 L5      R2

しかし $i=6$ で、またどれか1つを諦めなければならない。同様に $L_i-R_i$ が最小であるラクダ5を諦める。

ラクダ   1  3  4  6  ...  2 ...  5
得点    L1 L3 L4 L6      R2     R5

これで、 $L_i \ge R_i$ のラクダから得られる得点の最大値は求まった。

同様のことを $L_i \lt R_i$ のラクダについてもやる。こちらは右から埋めていくが、 $K_i ← N-K_i$ としておくと同様の式で考えられる。

1グループのラクダの中で、得点の大きい側に置けるものは、 $K_i$ に余裕があっても左詰・右詰にして問題ない。すると、中間が空く。

ラクダ   1  3  4  6  _  _  _  7  8  9

中間に、得点の小さい方を採用せざるを得なくなったラクダを並べると、片方のグループの配置がもう片方を阻害するようなことなく、両方の最大値を達成できる。

ラクダ   1  3  4  6  |  2  5  10  |  7  8  9
           Li≧Ri    |  大きい方  |   Li＜Ri
          Li採用可   |  採用不可  |  Ri採用可

なので、 $L_i \ge R_i$ と $L_i \lt R_i$ グループそれぞれで得点を最大化し、足し合わせたものが答えとなる。

        
          
          
              
              import sys
from heapq import heappush, heappushpop
 
t = int(sys.stdin.buffer.readline())
buf = []
for _ in range(t):
    n = int(sys.stdin.buffer.readline())
    lll = []
    rrr = []
    ans = 0
    for i in range(n):
        k, l, r = map(int, sys.stdin.buffer.readline().split())
        if l >= r:
            lll.append((k, l - r))
            ans += l
        else:
            rrr.append((n - k, r - l))
            ans += r
    lll.sort()
    rrr.sort()
    q = []
    for k, lr in lll:
        if len(q) < k:
            heappush(q, lr)
        else:
            ans -= heappushpop(q, lr)
    q = []
    for k, rl in rrr:
        if len(q) < k:
            heappush(q, rl)
        else:
            ans -= heappushpop(q, rl)
 
    buf.append(ans)
 
print('\n'.join(map(str, buf)))

            

        
      

F - Two Snuke

問題

10個の整数 $s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2$ を、以下の条件を満たすように選ぶ
条件
- $0 \le s_1 \lt s_2$
  - $n,u,k,e$ についても同様
- $s_1+s_2+n_1+n_2+u_1+u_2+k_1+k_2+e_1+e_2 \le N$
ここで、10個の整数の組としてあり得るもの全てに対し、以下を計算し、その総和を $10^9+7$ で割ったあまりを求めよ
- $(s_2-s_1)(n_2-n_1)(u_2-u_1)(k_2-k_1)(e_2-e_1)$
テストケースは $T$ 個あるので、それぞれについて求めよ
$1 \le T \le 100$
$1 \le N \le 10^9$

解法

力業で何とかする方法。

$N$ の制約が $10^5$ とかならまだしも、 $10^9$ では $O(N)$ すらできない。ただ、問題として成立しているということは、何かしら綺麗にまとめる方法があるのだろうと考えて、とりあえずは無視して数えあげの方法を考える。

$s_1,s_2$ のようにアルファベットの部分が同じ変数を「ペア」とする。

各ペアの $□_2$ を、ベースと差分に分ける。たとえば $s_2 = s_1 + \Delta s$ とする。問題文の条件より、ベースは0以上、差分は1以上となる。

$(s_2-s_1)(n_2-n_1)(u_2-u_1)(k_2-k_1)(e_2-e_1) = \Delta s \Delta n \Delta u \Delta k \Delta e$ となるので、5つのペアの差分が全て同じものはまとめて計算できる。

5つの差分の合計が同じものの個数

5つの差分を固定して、合計を $S$ とすると、残り $N-S$ を10個の変数のベースとして振り分けられる。

振り分けるときは、 $□_1$ と $□_2$ に同時に振り分けないといけないので、2ずつ消費する。また、どれにも振り分けず余らせてもよい。

従って、 $\dfrac{N-S}{2}$ を、6個（5個のペア+「どれにも振り分けない」ことを示す1個）に分ける重複組み合わせで、ベースへの振り分け方を数えあげられる。

${}_{6}H_{\frac{N-S}{2}} = {}_{5+\frac{N-S}{2}}C_{\frac{N-S}{2}} = {}_{5+\frac{N-S}{2}}C_5$

5つの差分の合計が $S$ になる場合の差分の積

DPを考えると、

$DP[i][j]=i$ 番目のペアまで考えて、差分の合計が $j$ であるような全てのペアにおける差分の積の合計

たとえば $DP[2][4]$ を考えると、2つの差分で合計が4になるのは $(\Delta s, \Delta n)=(1,3),(2,2),(3,1)$ があるので、積はそれぞれ $3,4,3$ となり、合計は10となる。

最初は、差分がそのままDPの値となる。

    j   1  2  3  4  5
DP[1]   1  2  3  4  5

遷移は、以下のようになる。

DP[1][1] からの遷移は、
DP[1]   1
        `--,--,--,--,
          x1 x2 x3 x4
          ↓ ↓ ↓ ↓
DP[2]   -  1  2  3  4  (DP[1][1] からの遷移分のみ)

DP[1][2] からの遷移は、
DP[1]      2
           `--,--,--,
             x1 x2 x3
             ↓ ↓ ↓
DP[2]   -  -  2  4  6  (DP[1][2] からの遷移分のみ)

これを、遷移後の方を主体にして数式で表すと、 $\displaystyle DP[i][j] = \sum_{k=1}^{j-1}{DP[i-1][k](j-k)}$ となる。

さて、しかし $j$ は $10^9$ までの値を取りうるので、これをそのままは計算できない。

Σの中身は割とシンプルなので、上手いことΣを取った式で表せないか。

おや、こんなところにWolfram Alphaさんが。

Wolfram|Alpha 日本語版

$DP[2][j] = \dfrac{(j-1)j(j+1)}{6}$
$DP[3][j] = \dfrac{(j-2)(j-1)j(j+1)(j+2)}{120}$
$DP[4][j] = \dfrac{(j-3)(j-2)(j-1)j(j+1)(j+2)(j+3)}{5040}$
$DP[5][j] = \dfrac{(j-4)(j-3)(j-2)(j-1)j(j+1)(j+2)(j+3)(j+4)}{362880}$

出てきた $DP[i]$ を次々、次の遷移式に当てはめて計算させると、~~どういう理屈か~~綺麗な式が出てくる。

これで、5つの差分の合計が $j$ となるような組の、差分の積の総和が、 $O(1)$ で求まった。

なお、 $362880=9!$ のため、 $DP[5][j]$ は $\dfrac{(j+4)!}{9!(j-5)!}={}_{j+4}C_{9}$ と言いかえられる。

この意味

解説pdfの一部で触れられていて上記の結果もそれを示しているが、今回のDPで求めた「“和が $j$ になるような $i$ 個の正の数の積” の全てのあり得る組み合わせでの総和」というのは、組み合わせの場合数に変換できる。

まず、「和が $j$ になるような $i$ 個の非負数への分け方」は、「一列に $j$ 個並んだボールに、 $i-1$ 個の仕切りを挟む」と考えて、重複組み合わせで求められる。

「 $i$ 個の“正の数”」という制約がある場合は、あらかじめ $i$ 個の各数に1ずつ割り振っておいて、 $j-i$ 個のボールで考えるとよい。

 |----- j-i個 ----|
 ○○○○○ ...  ○
↑↑↑↑↑  ... ↑↑   j-i+1 個の隙間に i-1 個の仕切りを挟む

(j-i+1) H (i-1) = (j-1) C (i-1)

さて、次に $i$ 個の数の積を求める段階に移る。これは、「分割された各ボールの区間に、さらに1つずつの仕切りを挟む場合の数」と一致する。

   2   0     3      1
 ○○ | | ○○○ | ○
 
あらかじめ1ずつ割り振っていたのを加算して積を求めると
   3 x 1  x  4   x  2  =  24

最初の2つのボールの（両端を含む）間に、さらにもう1つの仕切りを挟む方法は3通り
 ○○
↑↑↑

2番目の区間は0個なので、この間に仕切りを挟む方法は1通り
      |  |
       ↑

同様に、3番目は4通り、4番目は2通りとなり、
仕切りの挟み方は 3x1x4x2=24通り。4数の積と一致する

そして、これは4つの区間が変わっても同様に計算するので、 $i-1$ 個の仕切りを最初から $2i-1$ 個に増やして「一列に $j-i$ 個並んだボールに、 $2i-1$ 個の仕切りを挟む場合の数」と考えることができる。

つまり、当初の問題は、 ${}_{j-i+1}H_{2i-1} = {}_{j+i-1}C_{2i-1}$ と表現できる。

これを、Wolfram Alphaでの結果と照らし合わせると、今回では $i=5$ を代入すると ${}_{j+4}C_{9}$ となり、確かに合致している。

合体

求めたいのは、 $\displaystyle \sum_{k=5}^{N}(DP[5][k] \times {}_{5+\frac{N-k}{2}}C_5)$ である。

これも、Wolframさんに計算させたいが、 $\frac{N-k}{2}$ の部分に切り捨て処理が入るので、 $k$ を偶数の場合と奇数の場合に分けて再度まとめる。

すると、さすがにあまり綺麗にはならないが、しかししっかりとΣが取れ、定数時間で計算できる式となる。

これを実装すれば、答えとなる。

まとめ

Wolfram Alpha先生すごい。

間に合わなかったのは手元での式変形をバグらせていたからなので、間違いはいつも人の手で起こる。

        
          
          
              
              MOD = 10 ** 9 + 7
INV0 = pow(81729648000, MOD - 2, MOD)
INV1 = pow(163459296000, MOD - 2, MOD)
t = int(input())
buf = []
for _ in range(t):
    n = int(input())
    m = n // 2
 
    even = 0
    for i, co in enumerate([-11188800, -11670840, 2429994, 8028877, 4647426, 1368843, 235536, 23988, 1344, 32]):
        even = (even + co * pow(m, i, MOD)) % MOD
    for c in range(m - 2, m + 4):
        even = even * c % MOD
    even = even * INV0 % MOD
 
    if n % 2 == 0:
        m -= 1
 
    odd = 0
    for i, co in enumerate(
            [-61387200, -162718920, -80000346, 32588015, 46247060, 20273505, 4868682, 706860, 62040, 3040, 64]):
        odd = (odd + co * pow(m, i, MOD)) % MOD
    for c in range(m - 1, m + 4):
        odd = odd * c % MOD
    odd = odd * INV1 % MOD
 
    ans = (even + odd) % MOD
    buf.append(ans)
 
print('\n'.join(map(str, buf)))

            

        
      

ラグランジュ補間

Wolframさんがやってるのは、どうもこれっぽい。

答えが $x$ の $d$ 次多項式 $f(x)=a_0x^0+a_1x^1+a_2x^2+...+a_dx^d$ で表されるのであれば、相異なる $(x_i, f(x_i))$ を $d+1$ 個取ってくれば、 $f(x)$ が一意に定まる。

今回の場合、答えは $\displaystyle \sum_{k=5}^{N}({}_{k+4}C_{9} \times {}_{5+\frac{N-k}{2}}C_5)$ なので、これは 15次多項式になる。

Σの中身は $k$ の14次多項式だが、Σを取ると1次増える。また、Σの中身が多項式なら、取った後も多項式であることが証明されている。（4乗の和，べき乗の和の公式 | 高校数学の美しい物語）

なので、とりあえず $N$ が偶数と奇数の時に分けて、それぞれで最初の16項くらいまで愚直に計算する。偶奇を分けたのは、式に切り捨て除算があるので、関数が連続的でなくなり、補間が上手くいかなくなるため。

計算結果を用いてラグランジュ補間すると $f(x)$ の係数 $a_0,a_1,...,a_{15}$ が得られ、これを使うとどんな $N$ が来ても $O(d)$ で計算できる。

補間の計算量は $O(d^2)$ だが、プログラムをバグらせず書くのはなかなか大変。

なお、scipy.interpolate にはそのものズバリな lagrange() 機能があり大変手軽に使えるが、これは小数での計算になるので競プロではどうあがいても精度が足りない。

        
          
          
              
              import numpy as np
 
 
def lagrange(DEG, MOD):
    DIV = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 5 * 4 * 3 * 2 * 1
 
    def sub(n):
        result = 0
        for j in range(5, n + 1):
            tmp = 1
            for i in range(9):
                tmp *= j + 4 - i
            for i in range(5):
                tmp *= 5 + (n - j) // 2 - i
            tmp //= DIV
            result += tmp
        return result
 
    def np_pow(arr, exp, mod):
        res = np.ones_like(arr)
        tmp = arr.copy()
        while exp:
            if exp & 1:
                res = res * tmp % mod
            tmp = tmp * tmp % mod
            exp >>= 1
        return res
 
    even_result = np.array([sub(2 * x) for x in range(1, DEG + 1)], dtype=np.int64) % MOD
    odd_result = np.array([sub(2 * x + 1) for x in range(1, DEG + 1)], dtype=np.int64) % MOD
 
    base_coef = np.zeros((DEG, DEG), dtype=np.int64)
    base_coef[:, -1] = 1
    indices = np.arange(1, DEG + 1, dtype=np.int64)
    invs = np.ones(DEG, dtype=np.int64)
    for i in range(1, DEG + 1):
        idx = indices != i
        base_coef[idx, :-1] += base_coef[idx, 1:] * -i
        base_coef %= MOD
        invs[idx] *= indices[idx] - i
    base_coef *= np_pow(invs % MOD, MOD - 2, MOD)[:, None]
    base_coef %= MOD
 
    even_coef = even_result[:, None] * base_coef % MOD
    odd_coef = odd_result[:, None] * base_coef % MOD
    even_coef = even_coef.sum(axis=0) % MOD
    odd_coef = odd_coef.sum(axis=0) % MOD
 
    return even_coef, odd_coef
 
 
DEG = 16
MOD = 10 ** 9 + 7
even_coef, odd_coef = lagrange(DEG, MOD)
 
t = int(input())
buf = []
for _ in range(t):
    n = int(input())
    if n % 2 == 0:
        m = n // 2
        coef = even_coef
    else:
        m = (n - 1) // 2
        coef = odd_coef
 
    ms = np.ones(DEG, dtype=np.int64)
    for i in range(1, DEG):
        ms[i] = ms[i - 1] * m % MOD
 
    ans = (ms * coef % MOD).sum() % MOD
    buf.append(ans)
 
print('\n'.join(map(str, buf)))

            

        
      

¹⁾

Super-logarithm というらしい

−目次

エイシング プログラミング コンテスト 2020 C,D,E,F問題メモ