ARC122 参加記録 - Xenous の精進記録

1完(C問題)2ペナ 130分でした

A - Many Formulae

各 $A_i$ について、マイナスの個数がそれぞれわかれば良さそうです。 DPplus、DPminus を以下のように定めます。

DPplus[i] : $i$ 番目までで、 $i$ 番目がプラスで終わるようなプラスマイナスの並び方の総数
DPminus[i] : $i$ 番目までで、 $i$ 番目がマイナスで終わるようなプラスマイナスの並び方の総数

遷移は以下のようになります。

f:id:Xenous:20210615213043p:plain — DP の遷移イメージ

この遷移で更新させると、最後の $N$ 番目のマイナスで終わる並び方の総数はわかりますが、それ以前がぱっと見わかりません。実は、表を埋めていくと、以下のような法則が見つけられます。

f:id:Xenous:20210615213318p:plain — 各 $A_i$ でマイナスの場合の数を算出する

DPminus[i] $\times$ DPminus[N-i] の数が、 $A_i$ がマイナスになる場合の数と同じ

以上より、 $O(N)$ で計算することができました。

提出コード

MOD = pow(10,9)+7
def MODINV(n:int, MOD=MOD):
    return pow(n, MOD-2, MOD)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    # 初期化
    DPplus = [0] * N
    DPminus = [0] * N

    # 初期値
    DPplus[0] = 1

    # 遷移
    for i in range(1, N):
        DPplus[i] = (DPplus[i-1] + DPminus[i-1])%MOD
        DPminus[i] = DPplus[i-1]%MOD
    
    # 場合の数
    al = (DPminus[N-1] + DPplus[N-1])%MOD
    m = [0]
    for i in range(1, N):
        m.append((DPminus[i] * DPminus[N-i])%MOD)
    
    # 答え
    ans = 0
    for i, a in enumerate(A):
        ans += a * (al - m[i]) - a * m[i]
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

B - Insurance

自分が失う金額を以下のようにおきます。

$y_{i} = x + A_{i} - \min(A_{i}, 2x)$

求める期待値は次のように表せます。

$\displaystyle \frac1{N}\sum_{i} y_{i} = \frac{Nx + \sum_{i} A_{i} - \sum_{i} \min(A_{i}, 2x)}{N}$

右辺の分母の値の最小化を考えます。各 $y_i$ が凸関数であれば、その和も凸関数であるので、三分探索で見つけることができます。

$y_i = x + A_{i} - \min(A_{i}, 2x)$ について、グラフを描いてみます。 $\min$ の部分で場合分けが必要です。

$A_{i} > 2x$ 、すなわち $\frac{A_{i}}{2} > x$ のとき

$y_i = x + A_{i} - \min(A_{i}, 2x) = x + A_{i} - 2x = -x + A_{i}$

$A_{i} \leq 2x$ 、すなわち $\frac{A_{i}}{2} \leq x$ のとき

$y_i = x + A_{i} - \min(A_{i}, 2x) = x + A_{i} - A_{i} = x$

f:id:Xenous:20210615211703p:plain — $y_i = x + A_{i} - \min(A_{i}, 2x)$ の図

$y_i$ が凸関数ということがわかります。したがって和も凸関数で、求める式の最小化を三分探索します。

実装では、あらかじめ $A$ をソートしておき、累積和を求めておくと、 $\min$ の計算を $O(1)$ でできます。全体では $O(N\log{N})$ でできます。

提出コード

from itertools import accumulate
from bisect import bisect_left

def f(x:int):
    global A, accumulateA, N, sumA
    idx = bisect_left(A, 2*x)
    res = N*x + sumA - accumulateA[idx] - 2*x*(N-idx)
    return res


def main():
    global A, accumulateA, N, sumA
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    sumA = sum(A)
    accumulateA = [0] + list(accumulate(A))

    # 三分探索
    L = 0; R = 10**14+1
    err = 0.0000001
    while abs(R-L) > err:
        c1 = (L*2 + R) / 3
        c2 = (L + R*2) / 3
        if f(x = c1) > f(x = c2): L = c1
        else: R = c2
    ans = min(f(L), f(c1), f(c2))/N
    print(ans)


if __name__ == "__main__":
    main()

C - Calculator

唯一解けました。実装含め70分くらいかかってます。

最初に 1 を加えてから、操作3, 操作4, 操作3, 操作4, ... と操作するのが最も数字を大きくできる方法のように見えます。実際に計算するとこれがフィボナッチ数列になっていることもわかります。

ちなみに $10^{18}$ には、上記のように操作するとして、合計90回くらいで到達できます。

次に操作1, 操作2 の意味について考えます。操作1や操作2を行うと、そこから加算されていく数字がフィボナッチ数列的に増えていきます。

f:id:Xenous:20210613003019p:plain — 遷移例と操作2による差分の増加具合

方針としては、 $N$ を超えない最大のフィボナッチ数を求めて、その値との差分をさらにフィボナッチ数を構成することで縮めていくことを考えます。

以下は $N = 50$ のときの数列の例です。

f:id:Xenous:20210613003359p:plain — $N = 50$ のときの $(x,y)$ の遷移

初手では $34$ が最も( $50$ を超えずに) $50$ に近い数字になります。その差分の $16$ を埋めることを考えます。

$16$ に最も近い数字の $13$ は、一行目の $(x, y)$ の遷移 7番目 (0-index) に初めて出てきています。つまり、差分が $16$ となっているところから 7回前で、操作1 を行うことで、差分を $13$ 埋めることができます。その操作を行なった遷移列が 2 行目の $(x, y)$ の遷移になります。

このように求めたい数字との差を、フィボナッチ数列の値で縮めていくために、何回前に操作1, 操作2 をしておけばいいのかを探索することで、求める操作列を作ることができます。

提出コード

from bisect import *


def fibonacci_l(n, seta=1, setb=0):
    l = [(seta-1, setb)]
    a, b = seta, setb; l.append((a, b))
    for k in range(n):
        a, b = l[-1]
        if k%2 == 0: l.append((a, a+b))
        else: l.append((a+b, b))
    return l


def main():
    N = int(input())
    if N == 1:
        print(1)
        print(1)
        return
    base = fibonacci_l(100)
    baselside, _ = map(list, zip(*base))
    
    ans = base.copy()
    idx = bisect_left(baselside, N)-2
    diff = N - base[idx][0]
    #print(ans[:idx+1])

    while diff > 1:
        #print(diff)
        nextidx = bisect_left(baselside, diff)-2
        i, j = ans[idx+1 - nextidx]
        #print(i, j)
        ans = ans[:idx+1 - nextidx] + fibonacci_l(100, i+1, j)
        lside, _ = map(list, zip(*ans))
        idx = bisect_left(lside, N)-2
        #print(ans[:idx+1])
        diff = N - ans[idx][0]

    #print(idx)
    ans = ans[:idx+1]
    #print(ans)

    res = []
    for k in range(len(ans)-1):
        bfx, bfy = ans[k]
        afx, afy = ans[k+1]
        if bfx == afx:
            if afy == bfy+1: res.append(2)
            else: res.append(4)
        else:
            if afx == bfx+1: res.append(1)
            else: res.append(3)
    
    res.append(1)
    print(len(res))
    print(*res, sep='\n')


if __name__ == "__main__":
    main()

D - XOR Game

少しだけ考えました。あとで解きたい問題です。