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,\ldots$ と使っていくのがよい。

よって、素因数分解の後、指数 $a,b,c$ に着目し、それぞれが $a=1+2+3+\ldots$ でどこまでの和で表せるかを調べればよい。

たとえば $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,\ldots,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, \ldots, 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+\ldots = 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+\ldots=S$ を満たす $\{A_i,A_j,\ldots\}$ の要素数」まではわからない。

上記の例では、「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])

このウェブサイトはクッキーを使用しています。 Webサイトを使用することで、あなたはあなたのコンピュータにクッキーを保存することに同意します。 また、あなたはあなたが私たちのプライバシーポリシーを読んで理解したことを認めます。 同意しない場合はウェブサイトを離れてください。クッキーに関する詳細情報
programming_algorithm/contest_history/atcoder/2020/0531_abc169.txt · 最終更新: 2020/06/03 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0