−目次

AtCoder Beginner Contest 169 D,E,F問題メモ

AtCoder Beginner Contest 169 D,E,F問題メモ

AtCoder Beginner Contest 169

なんか、厳密な証明はともかく「多分こうじゃね」って解法が思いつきやすい問題というのはある。今回は比較的そういう回だった。

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])