目次
エイシング プログラミング コンテスト 2020 C,D,E,F問題メモ
決してお肉を熟成させたり、新品のヘッドホンに謎の音を流し続ける企業ではない。
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$ となる。 1)
なので、愚直にやっても数回で操作は終わる。 特に、$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さんが。
- $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}$ と言いかえられる。
合体
求めたいのは、$\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)))
1)
Super-logarithm というらしい
