第一回 AtCoder Japan Open -決勝- A,C問題メモ

第一回 AtCoder Japan Open -決勝-

A - Apples and Boxes

• 数直線の上に $N$ 個のりんごと $N$ 個の箱があります。具体的には、座標 $A_1, \dots, A_N$ にりんごが、座標 $B_1, \dots, B_N$ に箱が置かれています。
• りんごの箱詰めを担当する AtCoder さんは、ロボットアームを操作してりんごを箱の中に入れます。ロボットアームは最初座標 $0$ にあり、数直線上で自由に動かすことができます。ロボットアームがりんごのある座標にいるとき、そのりんごをつかむことができ、箱のある座標にいるとき、ロボットアームがつかんだりんごを離してその箱に入れることができます。ただし、ロボットアームは同時にひとつしかりんごを持つことができず、各箱にはひとつしかりんごを入れることができません。特定のりんごを特定の箱に入れなければならないといった制限はありません。
• 作業時間の制約上、ロボットアームの移動距離の合計は $T$ 以下でなくてはなりません。また、作業終了時にロボットアームが座標 $0$ に戻っている必要があります。このとき、最大でいくつのりんごを箱に入れることができるでしょうか？

• $1 \leq N \leq 4\,500$
• $0 \leq T \leq 10^{14}$
• $1 \leq A_1 \lt A_2 \lt \cdots \lt A_N \leq 10^{10}$
• $1 \leq B_1 \lt B_2 \lt \cdots \lt B_N \leq 10^{10}$
• $A_1, A_2, \dots, A_N, B_1, B_2, \dots, B_N$ はすべて異なる
• 入力はすべて整数

解説を読んでの自分用メモ。
「最適な取り方」がかなり気付きにくく、難しい。

• 解説 - 第一回 AtCoder Japan Open -決勝-

まずは取るリンゴと入れる箱を固定して、最適な移動方法を考える。
例えば $N$ 個全体のリンゴを箱に入れる場合を考える。

スタート地点、りんご、箱の座標をプロットし、各点で区切られた「区間」を何回通るかに着目する。
左から区間 $0,1,2,...,2N-1$ とする。
最後に $0$ に戻るので、各区間を通る回数は必ず偶数になる。

S---A---A---A---B---B---B
 ~~~ ~~~ ~~~ ~~~ ~~~ ~~~
  0   1   2   3   4   5    区間番号

移動方法が最適であることを証明する際には、以下の方法がとられる。

• 下限（「ある着眼点で絶対にこれ以上はかかる」という値）を求める
• 具体的に、下限を達成する方法を見つける

「$L_i:=$ 区間 $i$ より左にあるリンゴの数 － 左にある箱の数」とすると、 少なくとも $i$ 番目の区間は $2 \times \max(1,|L_i|)$ 回は通らなければならない。
∵ たとえば $L_i=2$ のとき、2個のリンゴは絶対に区間を越えて左から右に運ばなければならない（そして後で右から左に戻らなければならない）ためである。

そして、これは実際に移動可能である。

• $i$ 番目のリンゴは $i$ 番目の箱に入れる
• $A_i \lt B_i$ なら行きがけに拾って入れる
• $A_i \gt B_i$ なら帰りがけに拾って入れる

よって、取るリンゴと入れる箱が決まっていたら、リンゴと箱の個数バランスを管理することで求められる。

さて、$T$ 以内に拾って入れられる個数を求めたい。

先述の最適な移動方法から、以下の事実が言える。

• 対応するリンゴと箱のペアの間に、使われないリンゴ/箱は存在しない

たとえばそうでなく、使用しないリンゴをまたいでペアが発生する場合、

... --A---A---B---(A)---A---B---B-- ...
      `---+---'         `---+---'
          `-----------------'

「使用しないリンゴを越えて移動させるリンゴ」の1つを「使用しないリンゴ」に置き換えた方が絶対にいい。

... --A--(A)--B----A----A---B---B-- ...
      `-------'    |    `---+---'
                   `--------'

使用しない箱があった場合も同様のことが言える。
これを連鎖的に考えると、最適解において「使うリンゴと箱のペア」の間に使われないリンゴ・箱はない事が言える。
さらにこれは、「使うリンゴと箱は、いくつかの「リンゴと箱が同数になる区間」からなる」と言い換えられる。

以下のDPを考える。

• $\mathrm{DP}[i,j]=i$ 番目の区間の右側まで移動しながら、$j$ 個のペアを確定させた場合の、（帰りを含めた）最小移動距離

2通りの遷移がある。区間 $i$ の距離を $d_i$ とする。

$i$ 番目の区間をまたぐペアは無い場合、単に移動するだけである。

• $\mathrm{DP}[i,j]←\mathrm{DP}[i-1,j]+2d_i$

$i$ 番目の区間の右にあるリンゴ/箱を使う場合、遡って「リンゴと箱が同数になる直近の連続区間」を見つける。
リンゴと箱の個数バランスを管理しつつ遡ると、その連続区間で「$k$ 個のペアを、移動距離 $c$ で得られる」というのがわかる。

区間番号 p   q                           i
    ... ---A---B---B---B---A---A---B---A---A-- ...    AとBが同数の直近区間
              |-----------------------------|         k=4, cは個数バランスを管理して求められる

区間 $q$ まで遡って同数となったとして、$\mathrm{DP}[q]$ は区間右側の $B$ を使った場合も含んだ中での最小値であるため、 さらに1つ $p$ まで遡って、以下のように更新する必要がある。

• $\mathrm{DP}[i,j+k]←\mathrm{DP}[p,j]+c+2d_q$

なお、直近以外の「リンゴと箱が同数になる区間」は考慮する必要は無い。
上例より広い「リンゴと箱が同数になる区間」を考えたとしても、 対応するペアの関係から $q$ を通るときは手ぶらで通るので、分けて考えてよい。

これでDPをすすめ、$\mathrm{DP}[i,j] \le T$ を満たす最大の $j$ が答えとなる。

Python3

import os
import sys

import numpy as np


def solve(inp):
    n, t = inp[:2]
    aaa = inp[2:n + 2]
    bbb = inp[n + 2:]

    points = [(0, 0)]
    points.extend([(a, 1) for a in aaa])
    points.extend([(b, -1) for b in bbb])
    points.sort()
    # print(f'{points=}')

    INF = 1 << 60
    dp = np.full((n * 2 + 1, n + 1), INF, dtype=np.int64)
    dp[0][0] = 0
    for i in range(1, n * 2 + 1):
        p1, b = points[i]
        p2, b2 = points[i - 1]

        not_take_cost = (p1 - p2) * 2
        for cnt in range(n + 1):
            cost = dp[i - 1, cnt]
            new_cost = cost + not_take_cost
            if new_cost > t:
                continue
            dp[i, cnt] = min(dp[i, cnt], new_cost)

        balance = b
        j = i - 1
        section_cost = 0
        while j >= 0 and balance != 0:
            p2, b = points[j]
            section_cost += 2 * abs(balance) * (p1 - p2)
            balance += b
            p1 = p2
            j -= 1
        if balance == 0:
            count = (i - j) // 2
            betweenness_cost = (points[j + 1][0] - points[j][0]) * 2
            # print(f'{i=} {j=} {count=} {section_cost=} {betweenness_cost=}')
            for cnt in range(n + 1):
                cost = dp[j, cnt]
                new_cost = cost + betweenness_cost + section_cost
                if new_cost > t:
                    continue
                dp[i, cnt + count] = min(dp[i, cnt + count], new_cost)

    # for i, state in enumerate(dp):
    #     print(i, state)

    ans = 0
    for i in range(1, n * 2 + 1):
        for j in range(n + 1):
            if dp[i, j] <= t:
                ans = max(ans, j)
    return ans


SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)


inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

C - Final Exam

• AtCoder さんは、$n$ 問の問題からなるテストを受験しました。
• このテストでは、$1$ 問ずつ問題が出題されていきますが、出題される問題の難易度は現時点での正解状況に応じて変化し、具体的には以下のようになります。
  • 現時点の正解数が、現時点での不正解数以上である場合、AtCoder さんは確率 $1/3$ で次の問題に正解する。
  • 現時点の正解数が、現時点での不正解数未満である場合、AtCoder さんは確率 $2/3$ で次の問題に正解する。
  • ここで、各問題の正解・不正解の確率は独立であると仮定する。
• 過半数の問題に正解すれば合格です。
• さて、AtCoder さんが合格する確率を $3^n$ 倍した値 $f(n)$ は整数になります。
• 整数 $N$ が与えられるので、$\sum_{n=1}^{N} \lfloor \frac{10^{18}}{n} \rfloor \times f(n)$ を $10^9 + 7$ で割った余りを計算してください。

• $1 \leq N \leq 10\,000\,000$
• $N$ は整数

いきなり $10^{18}$ とか出てきてよくわかんないが、 これは、本来「$f(1)～f(N)$ の全ての値を求めてください」という問いにしたかったが、 それだと出力に時間がかかるのでハッシュ化して出力させた、というようなこと、、、なのかな？
（床関数が出てくるので、$f(n)$ の中身をバラして主客転倒、みたいな話とは相性悪そうだし）

まず、ランダムウォークを描く。
各頂点 $(x,y)$ は、「$x$ 問後に 正解数 - 不正解数 $=y$ となっている状態」を表すとする。
$3^n$ 倍した結果を求めるので、辺には $1$ または $2$ の値をつけ、遷移時には辺の値を乗算すると見なしてよい。

               (3,3)             1
             1↗               ↗
          (2,2)               1        f(n) は、(n,y) において、
        1↗  2↘            ↗ ↘      y > 0 となる箇所の合計値
     (1,1)     (3,1)       1     8     （n=3 なら、1+8 = 9）
   1↗  2↘  1↗         ↗ ↘ ↗    ↑----------------------------
(0,0)     (2,0)         1     6
   2↘  2↗  2↘         ↘ ↗ ↘
    (1,-1)    (3,-1)       2    16
        1↘  2↗            ↘ ↗
         (2,-2)               2
             1↘               ↘
              (3,-3)             2

ほとんどの遷移は $y=0$ の中心線を境に対称となるのだが、唯一 $(x,0)$ から出る辺だけ、負の方に偏る。

この非対称性より、$(x,y)$ の値を $g(x,y)$ とすると、$y \gt 0$ において、$2g(x,y)=g(x,-y)$ となる。
ある $(x,y)$ に至るウォークを1つ取って、最後に $y=0$ を通過したのが $(x',0)$ だったとして、 それ以降を上下反転させたウォークの値は元のウォークのちょうど2倍になることから示せる。

よって、$n$ が奇数の場合はすぐに求まる。$f(n)=3^n \times \frac{1}{3}$ となる。

問題は偶数の時で、$f(n)=(3^n-g(n,0)) \times \frac{1}{3}$ となるため、$g(n,0)$ が必要となる。
$g(2,0),g(4,0),...$ を求めることを目標とする。

カタラン数の考え方を参考にする。

• $A(n):=g(2n,0)$
• $B(n):=y$ が非負の部分のみを通って、$(0,0)$ から $(2n,0)$ に至る全経路の値の総和

$B(n)$ は、経路数自体はカタラン数と一致し、どの経路も“2”の辺をちょうど $n$ 回通ることから、$2^n C(n)$ と表せる。（$C$ はカタラン数）

$A(n)$ は、$(0,0)$ から次に $y=0$ となる点 $(2k,0)$ を固定すると、

      ,- B(k-1) -,
    ○            ○
  ↗              x2↘
(0,0)                (2k,0) -- A(n-k) --> (2n,0)
  ↘x2            x2↗
    ○            ○
      `- B(k-1) -'

これを各 $k$ について合計し、$\displaystyle A(n+1) = \sum_{k=0}^{n}6B(k)A(n-k)$ という漸化式が立てられる。

このままでは $O(N^2)$、分割統治FFTを使っても $O(N (\log{N})^2)$ となり、$N \le 10^7$ という制約では厳しい。

母関数で表現する。

• 数列の母関数の意味とその応用例 | 高校数学の美しい物語

漸化式が畳み込みの形となっている数列は、母関数同士の積も綺麗に表せる。
ちょうど上記のサイトにカタラン数の母関数を求める例が載っており、参考になる。

$G(x)=\sum B_kx^k$ とすると、$2G(x)^2 = \dfrac{G(x)-1}{x}$ とでき、$G(x)=\dfrac{1-\sqrt{1-8x}}{4x}$ となる。

同様に、$F(x)=\sum A_kx^k$ とすると、$6F(x)G(x)=\dfrac{F(x)-1}{x}$ より、$F(x)=\dfrac{2}{3 \sqrt{1-8x}-1}$ となる。

平方根が分母にあると厄介なので有理化する。$F(x)=\dfrac{6 \sqrt{1-8x}+2}{8(1-9x)}$

ここで、$\sqrt{1-8x}$ を展開した数列 $D$ は、A098579 - OEIS にあるように、

• $D(0)=1$
• $D(x)=-2^{x+1}C(x-1)$ （$x \ge 1$）

で表される。また、分母も一次式の単純な形なので、$F(x)$ の分子を展開し、$1-9x$ で割っていくと、数列 $A$ が復元できる。
一般に、ある多項式 $f(x)$ を $1-kx$ で割るというのは、$f(x)$ の $x^i$の係数を $a[i]$ とすると「$a[i+1]$ に $k \times a[i]$ を足し込む」という操作を $i=0,1,...$ に対して行っていくという簡単な操作で実装できる。

       ___1____6___48___408___...    ← ここに出てくる数列が A
1 - 9x )  1   -3   -6   -24   ...    ← F(x) の分子の展開 / 8
          1   -9
               6   -6
               6  -54
                   48   -24
                   48  -432
                        408

これで、各 $g(n,0)$ が求められた。

Python3

def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


def solve(n):

    MOD = 1_000_000_007
    facts, finvs = precompute_factorials(n, MOD)

    a = [1]
    p = -3
    for i in range(1, n // 2 + 1):
        a.append(p * facts[(i - 1) * 2] * finvs[i - 1] * finvs[i] % MOD)
        p = p * 2 % MOD

    for i in range(1, n // 2 + 1):
        a[i] += a[i - 1] * 9
        a[i] %= MOD

    ans = 0
    m = 10 ** 18
    total = 3
    INV3 = pow(3, -1, MOD)
    for i in range(1, n + 1):
        coef = m // i % MOD
        if i % 2 == 1:
            ans += coef * total * INV3
        else:
            ans += coef * (total - a[i // 2]) * INV3
        ans %= MOD
        total = total * 3 % MOD
    return ans


n = int(input())
print(solve(n))