目次
AtCoder Beginner Contest 169 D,E,F問題メモ
なんか、厳密な証明はともかく「多分こうじゃね」って解法が思いつきやすい問題というのはある。今回は比較的そういう回だった。
D - Div Game
問題
- 正整数 $N$ が与えられる
- $N$ に対して、以下の操作を最大何回行うことができるか、求めよ
- 操作: $N$ を、以下の条件を全て満たす整数 $z$ で割った値で置き換える
- 素数 $p$ と正整数 $e$ で、$z=p^e$ と表せる
- $N$ は $z$ で割り切れる
- 過去の操作で $z$ として選んだどの数とも異なる
- $1 \le N \le 10^{12}$
解法
$N$ を素因数分解したとき、$N=2^a3^b5^c$ と表せるとすると、$z$ を作るのに使える素数は $2,3,5$ のいずれか。他の素数を使うと $N$ を割り切れない。
1つの素数しか使わないので、例えば $p=2$ として $z$ を作って $N$ を割っても $3^b5^c$ の部分には影響がない。素数ごとに考えることができる。
さらに、同じ $z$ を使ってはいけないので、$p=2,e=1$ として $z=2$ を使うと、次からは $p=2$ の時は別の $e$ を使わなければならない。
操作をできるだけ多くしたいので、$e$ は小さい方から $1,2,3,...$ と使っていくのがよい。
よって、素因数分解の後、指数 $a,b,c$ に着目し、それぞれが $a=1+2+3+...$ でどこまでの和で表せるかを調べればよい。
たとえば $N=2^{12}3^75^47$ なら、$1+2+3+4 \le 12 \lt 1+2+3+4+5$ のため、$z=2^1,2^2,2^3,2^4$ まで操作できて、$2^5$ は無理。
同様に3は3回、5は2回、7は1回処理できるので、あわせて10回が答え。
from collections import defaultdict
def prime_factorize(n):
ret = defaultdict(int)
while n % 2 == 0:
n //= 2
ret[2] += 1
d = 3
while d * d <= n:
while n % d == 0:
n //= d
ret[d] += 1
d += 2
if n > 1:
ret[n] += 1
return dict(ret)
n = int(input())
pf = prime_factorize(n)
ans = 0
for c in pf.values():
i = 1
while i <= c:
c -= i
i += 1
ans += 1
print(ans)
E - Count Median
問題
- ある長さ $N$ の数列の中央値を、以下で定義する
- $N$ が奇数の時、ソートしてちょうど真ん中の値
- $N$ が偶数の時、ソートして真ん中の2つの値を足して2で割った値
- さて、いま数列 $X_1,X_2,...,X_N$ があるが、具体的な値は分かっていない
- $i=1～N$ のそれぞれについて、$A_i \le X_i \le B_i$ であることは分かっている
- 中央値としてあり得る値の個数を求めよ
- $2 \le N \le 2 \times 10^5$
解法
ソートが必要なため実際は $O(N \log{N})$ であるものの、それ以外の実装はほぼ $O(1)$ の、机の上で解く問題。
偶数の場合、複数の値がからんでややこしそうなため、とりあえず1つの値のみで決まる奇数の場合を考える。
「仮に $k$ が中央値と仮定して、これが可能か？」を考える。「あり得る値」なので、他の値は $k$ が中央値となるよう都合よく（問題文の条件の範囲で）決めてよい。
奇数の場合
中央値は、「自分より小さい値が $\dfrac{N}{2}$ 個」「自分より大きい値が $\dfrac{N}{2}$ 個」存在すればよい。（切り捨て）
$A_i$ をソートして、小さい方から $\dfrac{N+1}{2}$ 番目（$A_i$ の中での中央値）が、中央値が取れる最小値となる。これより小さくなると、自分より小さい値が $\dfrac{N}{2}$ 個作れない。
この場合、自分より $A_i$ の大きな数が確実に $\dfrac{N}{2}$ 個あるので、大きい方の個数の条件も満たせる。
┃-------------┃
┃------| |----┃
┃-----| |--------┃
↑ ↑
最小 最大
中央値の取り得る最大値も、同様に考えると、$B_i$ の中央値であることが分かる。
後は、最小と最大の間の整数なら、どんな数でも作れるか？ を考える必要がある。
Aj Bk
|---| ┃---| |----┃ |-----|
|----------------------|
最大・最小を取る $A_j, B_k$ について、$X_j, X_k$ の区間同士が断絶していたとしても、それを覆うような区間があれば、そいつが中央値になることはできる。 （$A_j$ より右の区間では常に左に $\dfrac{N}{2}$ 個以上の数を存在させられ、$B_k$ より左の区間にも常に右に $\dfrac{N}{2}$ 個以上の値を存在させられる）
つまり作れない場合、最小と最大の間に、どんな $A_i,B_i$ でも作れない数があることになる。しかし、その場合、
|------| |---|
|-----| |---|
|--| |---|
左に $\frac{N+1}{2}$ 個、右にも同数の区間が必要になり、あわせて $N+1$ 個の区間が必要となり矛盾する。
よって、どんな数でも作れる。$最大-最小+1$ が答えとなる。
偶数の場合
真ん中の2数を別々に考えて $M_1,M_2$ として、それぞれが取り得る最小・最大は、$N$ が奇数の場合と同様に考えられる。
- たとえば $N=12$ として
- $M_1$…最小: $A_i$ の小さい方から 6番目の数、最大: $B_i$ の小さい方から 6番目の数
- $M_2$…最小: $A_i$ の小さい方から 7番目の数、最大: $B_i$ の小さい方から 7番目の数
すると、中央値の最小は、$\dfrac{(M_1の最小)+(M_2の最小)}{2}$、最大は $\dfrac{(M_1の最大)+(M_2の最大)}{2}$ となる。
また、こちらは2で割るので、0.5刻みで値を取ることができる点に注意。
奇数の場合と同様に考えると、$M_1$ の取り得る範囲、$M_2$ の取り得る範囲はそれぞれ連続であることが示せるので、中央値も最小・最大の間の全ての数を取れる。
import sys
def solve_even(n, aaa, bbb):
li = n // 2 - 1
ri = n // 2
aaa.sort()
bbb.sort()
ll = aaa[li]
lr = aaa[ri]
rl = bbb[li]
rr = bbb[ri]
return (rl + rr) - (lr + ll) + 1
def solve_odd(n, aaa, bbb):
k = n // 2
aaa.sort()
bbb.sort()
return bbb[k] - aaa[k] + 1
n, *ab = map(int, sys.stdin.buffer.read().split())
if n % 2 == 0:
ans = solve_even(n, ab[0::2], ab[1::2])
else:
ans = solve_odd(n, ab[0::2], ab[1::2])
print(ans)
F - Knapsack for All Subsets
問題
- 長さ $N$ の正整数列 $A_1, A_2, ..., A_N$ と、正整数 $S$ が与えられる
- この数列の、空でない部分集合は $2^N - 1$ 通りある
- ある部分集合を $T$ として、$f(T)$ を以下で定める
- $T$ の部分集合であって、総和が $S$ であるものの個数
- $T$ としてあり得る全ての集合について $f(T)$ を求め、その総和を $\mod{998244353}$ で求めよ
- $1 \le N \le 3000$
- $1 \le S \le 3000$
解法
ある集合の、冪集合の、さらに部分集合を考えるので、こんがらがって問題文の意味の把握が難しい。
とりあえず、元の数列の全ての要素を使えるとして、$A_i+A_j+... = S$ を満たすものの個数は、よくあるナップサック問題として求められる。
- $DP[i][w]=i$ 個目の要素まで見て、和が $w$ となるような場合の数
で、そういう集合が、たとえば以下の例で、5通りあったとする。
N = 6 S = 7
A = {1, 1, 2, 2, 3, 6}
{1, 6} 1の選び方で2通り
{1, 1, 2, 3} 2の選び方で2通り
{2, 2, 3}
ある部分集合 $T$ が、たとえば $\{2,2,3\}$ を $f(T)$ に数え挙げるなら、$T$ にこの3個の要素は当然入ってないといけなくて、残りの要素はどうだっていい。
よって、$\{2,2,3\}$ が数えられるような $T$ は、残りの4要素の決め方で $2^4$ 個存在する。
他の要素も同様に $\{1,6\}$ は $2^5$ 個、$\{1,1,2,3\}$ は $2^3$ 個存在するので、これらを全て総計して、答えは96となる。
しかし、通常のナップサック問題は、「$A_i+A_j+...=S$ を満たす $\{A_i,A_j,...\}$ の要素数」まではわからない。
上記の例では、「5通り」という部分しか分からない。これでは答えが求められない。
かといって、以下のようなDPでは、計算量が $O(N^3)$ となり、間に合わない。
- $DP[i][j][w]=i$ 番目の要素まで見て、そのうちの $j$ 個を使い、和が $w$ となるような場合の数
ここでは、$T$ の個数を直接求めに行くとよい。日本語が難しいが、
- $DP[i][w]=i$ 個目の要素まで見て、「和が $w$ となるような集合を作れるような $T$ の個数」
つまり、通常のナップサック問題では $i$ 番目の要素が選ばれなければそのままだが、このDPでは、以下の2通りを考える。
- もともと $T$ に $i$ 番目の要素が選ばれていない
- $T$ に $i$ 番目の要素は選ばれたものの、和が $S$ になる集合には選ばれなかった
よって、DPの遷移において、$i$ 番目の要素を選ばない場合の遷移を2倍する。
w 0 1 2 3 4
初期 1
x2↓ ↘ "↓"の遷移を2倍して行う
3 2 1
↓↘ ↓↘
1 4 2 2 1
...
import sys
import numpy as np
n, s, *aaa = map(int, sys.stdin.buffer.read().split())
MOD = 998244353
dp = np.zeros(s + 1, np.int64)
dp[0] = 1
for a in aaa:
ndp = dp * 2 % MOD
if a <= s:
ndp[a:] += dp[:-a]
dp = ndp % MOD
print(dp[s])
