AtCoder Beginner Contest 400 E,F問題メモ

AtCoder Beginner Contest 400

ABC300の前後、何回かDDos攻撃でアクセス困難になり、Unratedになることがあった。
そこから100回。今も攻撃はあるだろうけど、安定してRatedで無事開催できててすごい。

E - Ringo's Favorite Numbers 3

問題文

正整数 $N$ に対し、 $N$ が 400 number であることは以下の $2$ つの条件をともに満たすことであると定義します。
- $N$ の素因数はちょうど $2$ 種類である。
- $N$ の各素因数 $p$ について、 $N$ が $p$ で割り切れる回数は偶数回である。より厳密には、 $N$ の各素因数 $p$ について $p^k$ が $N$ の約数であるような最大の非負整数 $k$ は偶数である。

$Q$ 個のクエリが与えられるので、それぞれについて答えてください。各クエリでは、整数 $A$ が与えられるので、 $A$ 以下の最大の 400 number の値を求めてください。ただし、本問題の制約下では $A$ 以下の 400 number は常に存在します。

制約

$1 \leq Q \leq 2 \times 10^5$
各クエリについて、 $36 \leq A \leq 10^{12}$
入力される値はすべて整数

解法

$10^{12}$ 以下の “400 number” を全て求めてソートしておくことができれば、各クエリには二分探索で求められる。

$f(a,b,c,d)$ を、「 $(a番目の素数)^{2b}(c番目の素数)^{2d}$ として表される 400 number」と定義して、一番小さい $f(1,1,2,1)$ から経路探索のように求めていく。

$(a,b,c,d)$ からは、以下の4つに遷移する。

$a+1 \lt c$ の場合、 $(a+1,b,c,d)$
$(a,b+1,c,d)$
$(a,b,c+1,d)$
$(a,b,c,d+1)$

$10^{12}$ を超えたら打ち切り、また一度訪れた組を再度調べないように注意すると、 $10^{12}$ 以下の “400 number” の個数を $K$ として、 $O(K)$ で全列挙できる。

Python3

        
          
          
              
              from bisect import bisect
 
 
def get_primes(n):
    """ nまでの素数リスト """
    candidates = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        candidates.pop()
    candidates[1] = 0
    candidates[2] = 1
    for p in range(3, int(n ** 0.5) + 1, 2):
        if candidates[p]:
            for m in range(p * p, n + 1, 2 * p):
                candidates[m] = 0
    return [p for p, b in enumerate(candidates) if b]
 
 
def solve(q, queries):
    primes = get_primes(550000)
    limit = 10 ** 12
    cand = {36}
    q = [(36, 0, 2, 1, 2)]
    while q:
        p, a, b, c, d = q.pop()
        if b == 2 and d == 2:
            x = primes[a]
            y = primes[c + 1]
            pp = x ** 2 * y ** 2
            if pp <= limit and pp not in cand:
                cand.add(pp)
                q.append((pp, a, 2, c + 1, 2))
 
            if a + 1 < c:
                x = primes[a + 1]
                y = primes[c]
                pp = x ** 2 * y ** 2
                if pp <= limit and pp not in cand:
                    cand.add(pp)
                    q.append((pp, a + 1, 2, c, 2))
 
        x = primes[a]
        y = primes[c]
        pp = x ** (b + 2) * y ** d
        if pp <= limit and pp not in cand:
            cand.add(pp)
            q.append((pp, a, b + 2, c, d))
 
        pp = x ** b * y ** (d + 2)
        if pp <= limit and pp not in cand:
            cand.add(pp)
            q.append((pp, a, b, c, d + 2))
 
    cand = sorted(cand)
    ans = []
    for a in queries:
        i = bisect(cand, a)
        ans.append(cand[i - 1])
    return ans
 
 
q = int(input())
queries = [int(input()) for _ in range(q)]
ans = solve(q, queries)
print('\n'.join(map(str, ans)))

            

        
      

F - Happy Birthday! 3

問題文

半径で切って $N$ 等分された円形のケーキがあります。
各ピースには時計回りに $1, 2, \ldots, N$ の番号が付けられています。また、 $1 \leq i \leq N$ なる整数 $i$ についてピース $i$ をピース $N + i$ とも呼ぶこととします。
はじめ、すべてのピースの色は色 $0$ です。
あなたは、以下の操作を好きな回数行うことができます。
- $1 \leq a, b, c \leq N$ なる整数 $a, b, c$ を選ぶ。 $0 \leq i \lt b$ なる各整数 $i$ に対してピース $a + i$ の色を色 $c$ に変更する。この操作にはコストが $b + X_c$ かかる。

$1 \leq i \leq N$ なるすべての整数 $i$ に対してピース $i$ の色を色 $C_i$ にするために必要なコストの合計の最小値を求めてください。

制約

$1 \leq N \leq 400$
$1 \leq C_i \leq N$
$1 \leq X_i \leq 10^9$
入力される値はすべて整数

解法

操作は、平たく言うと「好きな扇形を好きな1色に塗りつぶす」となる。

制約メタ読みで区間DPに当たりを付ける。
円環であっても区間 $[l,r)$ は定義できる。「 $l \gt r$ の場合は $1$ と $N$ の境界を跨いでいる区間」と解釈すればよい。

$\mathrm{DP}[l,r]:=$ 区間 $[l,r)$ を塗るのに必要なコスト

初期状態は、各 $i$ に対し以下となる。

$\mathrm{DP}[i,i]=0$
$\mathrm{DP}[i,i+1]=X_{C_i}+1$

$\mathrm{DP}[l,r]$ を求める時、それより幅の短い区間は全て求まっているとして、 $[l,m)$ と $[m,r)$ に分割する箇所 $m=l+1,...,r-1$ を全探索する。

ピース $l$ を色 $C_l$ に塗る際に $m$ を跨がない場合は、単純に足し合わせ。
- $\mathrm{DP}[l,m]+\mathrm{DP}[m,r]$
$C_l=C_m$ の時に限り、ピース $m$ を塗る際に、 $l$ まで一緒に塗っていたことにできる。
- 追加分のコストは、区間を伸ばした分 $m-l$
- $\mathrm{DP}[l+1,m]+\mathrm{DP}[m,r]+(m-l)$

一見、なんかもっと他の遷移も考えなきゃいけないように思うが（ $m$ を塗る際に $l$ までは一緒には塗らないが、その手前のどこかまでは一緒に塗る場合、など）、その場合は他の分割箇所 $m$ でちゃんと考慮されるので、上記の遷移だけでいける。

これでDPを埋めていき、幅 $N$ の区間に対するDPの結果の中での最小値が答え。
（※定義上、幅 $N$ の区間の格納場所は $\mathrm{DP}[i,i]$ となり、初期状態の幅0の区間とダブってしまうので、幅 $N$ の場合だけはどこか別の場所に記録しておくとよい。他の区間を求める時に参照されることはないし）

計算量は $O(N^3)$

Python3