トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）F,G 問題メモ

トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）

F - Earn to Advance

問題

$N \times N$ グリッドを左上 $(1,1)$ から右下 $(N,N)$ まで移動する
はじめ、所持金は0
マス $(i,j)$ では以下の3種類の行動を行える
- その場にとどまって $P_{i,j}$ 円得る
- $R_{i,j}$ 円支払って右へ移動する
- $D_{i,j}$ 円支払って下へ移動する
最小の行動回数を求めよ
$2 \le N \le 80$

解法

移動中に所持金が足りなくなったとき、現在いるマスで補充する代わりに、通過したうち $P_{i,j}$ が最大のマスで、「そこにいた時に、先を見越して所持金を補充しておいた」ことにしてよい。

これにより、各マスでは「所持金が $R_{i,j}$ 以上になるまで補充できたら、すぐ右に移動する」（下も同様）としてよい。

$DP[i,j,k,l]=(1,1)$ から $(i,j)$ への移動で、通過マスのうち $P_{k,l}$ が最大であった場合の、(最小行動回数, その時の最大所持金)

行動回数と所持金の2つの値を管理しなければならない。行動回数は少ない方がよいが、所持金は多い方がよい。
2つが相反する場合、DPにはどちらを残すべきか？

①行動回数が多くなってしまうが所持金は多い状況
②行動回数が少なくすむが所持金は少ない状況

答えとして求めるのは行動回数なので②は必須だが、この先、「②では所持金が足りなくなってしまうが、①では手持ちで足りるので補充しなくて済んで、最終的に逆転する」ようなことはないか？

ないと言える。

「所持金が足りればすぐに移動する」という行動基準を考えると、各状況の所持金を $C_①,C_②$ として、$0 \le C_①,C_② \lt P_{k,l}$ である。

$C_②+P_{k,l} \gt C_①$ なので、②で1回補充すると所持金は $C_②$ の方が大きくなる。
つまりこれ以降で、②では補充するが①ではしなくて済む（または、①の方が補充回数が少なくなる）状況が訪れるとしても、補充回数の差はせいぜい1回で逆転まではしないし、その場合も所持金は②の方が多いので、②が完全に優位である。

（この先の通過マスで、$P_{k,l}$ がより多い他のマスに更新されているかもしれないが、いずれにしろ上記の理論は変わらない）

よって、DPは②の行動回数が最小の状態（同じなら、所持金がより多い方）を残す、として問題ない。

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

Python3

import os
import sys

import numpy as np


def solve(inp):
    n = inp[0]
    offset = 1
    ppp = np.zeros((n, n), np.int64)
    for i in range(n):
        ppp[i, :] = inp[offset + i * n:offset + i * n + n]
    offset += n * n
    rrr = np.zeros((n, n - 1), np.int64)
    for i in range(n):
        rrr[i, :] = inp[offset + i * (n - 1):offset + (i + 1) * (n - 1)]
    offset += n * (n - 1)
    ddd = np.zeros((n - 1, n), np.int64)
    for i in range(n - 1):
        ddd[i, :] = inp[offset + i * n:offset + (i + 1) * n]

    INF = 1 << 60
    dpc = np.full((n, n, n, n), INF, np.int64)
    dpm = np.full((n, n, n, n), 0, np.int64)
    dpc[0, 0, 0, 0] = 0
    for i in range(n):
        for j in range(n):
            for k in range(n):
                for l in range(n):
                    cost = dpc[i, j, k, l]
                    money = dpm[i, j, k, l]
                    if cost == INF:
                        continue
                    if ppp[k, l] < ppp[i, j]:
                        new_k = i
                        new_l = j
                    else:
                        new_k = k
                        new_l = l
                    if i < n - 1:
                        d = ddd[i, j]
                        if d > money:
                            c = (d - money - 1) // ppp[new_k, new_l] + 1
                            new_money = money + ppp[new_k, new_l] * c - d
                            new_cost = cost + c + 1
                        else:
                            new_money = money - d
                            new_cost = cost + 1
                        if dpc[i + 1, j, new_k, new_l] > new_cost:
                            dpc[i + 1, j, new_k, new_l] = new_cost
                            dpm[i + 1, j, new_k, new_l] = new_money
                        elif dpc[i + 1, j, new_k, new_l] == new_cost:
                            if dpm[i + 1, j, new_k, new_l] < new_money:
                                dpc[i + 1, j, new_k, new_l] = new_cost
                                dpm[i + 1, j, new_k, new_l] = new_money
                    if j < n - 1:
                        r = rrr[i, j]
                        if r > money:
                            c = (r - money - 1) // ppp[new_k, new_l] + 1
                            new_money = money + ppp[new_k, new_l] * c - r
                            new_cost = cost + c + 1
                        else:
                            new_money = money - r
                            new_cost = cost + 1
                        if dpc[i, j + 1, new_k, new_l] > new_cost:
                            dpc[i, j + 1, new_k, new_l] = new_cost
                            dpm[i, j + 1, new_k, new_l] = new_money
                        elif dpc[i, j + 1, new_k, new_l] == new_cost:
                            if dpm[i, j + 1, new_k, new_l] < new_money:
                                dpc[i, j + 1, new_k, new_l] = new_cost
                                dpm[i, j + 1, new_k, new_l] = new_money

    ans = dpc[-1, -1, :, :].min()

    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)

G - Points and Comparison

問題

2次元平面上の $N$ 個の点がある
$Q$ 本の直線 $y=A_i x + B_i$ が与えられる
各直線につき線上またはそれより上にある点の個数を求め、$Q$ 本を通しての総和を求めよ
$Q$ が多いので、$A_i,B_i$ は疑似乱数生成で与えられる（元の問題文参照）
$1 \le N \le 5000$
$1 \le Q \le 10^7$
$-10^8 \le A_i \le 10^8$
$-10^{16} \le B_i \le 10^{16}$
実装制限時間 10 sec

解法

PythonだとPyPyでも厳しい、Numbaでやっと通った。
ちょっと $N,Q$ を多くしすぎじゃないですかねと思ったが、 C++ だとコンパイルオプションを指定して愚直解を通されていたみたいなので、Writerさんは大変だと思い直した。

ある1クエリ $(A_i,B_i)$ だけに答えることを考えると、点が上手い具合にソートされていると、二分探索で答えを求められそうである。

「上手い具合にソート」とはどんな状態かを考えると、「各点を通る傾き $A_i$ の直線を引くと、それらが下から順に並んでいる」と言う状態である。
クエリの直線が、どの2点（から引かれた直線）の間にあるか二分探索で調べれば、そこから上の点は全て条件を満たすことになる。

      ／    ／  ／／
    ／    ／  ／／
  ①    ／  ④／    この傾きでは、③④②① の順に小さい
／    ②  ／／
    ／  ／③
  ／  ／／

$A_i$ が変わると、並び順も変わる

＼＼＼    ＼
  ①＼＼    ④      この傾きでは、①②③④ の順に小さい
    ＼②＼    ＼
      ＼＼③
        ＼＼＼

$A_i$ ごとにこれを求めていったらもちろんTLEだが、傾きがちょっと変わっただけでは大部分の順序は同じはず。

クエリを $A_i$ でソートして傾きを負の無限大から正の無限大へ徐々に変化させていったとき、各2点組の順位は「傾きが2点を結ぶ直線の傾きに等しくなった」前後に入れ替わる。

このような変化は $O(N^2)$ 箇所あり、隣り合った要素を入れ替える操作は $O(1)$ でおこなえる。

よって、「全ての2点間の傾き」と「クエリ1で与えられる直線の傾き $A_i$」を、まとめてイベントソートして、小さい方から「順位の入れ替え」または「二分探索による求解」をおこなっていけばよい。

ただし、

$X_i=X_j$ な2点は、最初から最後まで順位が入れ替わらない（$Y$ が大きい方が常に上）なので、イベントに含めなくてよい
最初の点の順位は、負の無限大の傾きの直線を引いたときの順位であり、$(X_i,Y_i)$ をこのままソートすればよい

$O((N^2+Q)\log{(N^2+Q)})$ で求められる。

点とクエリを別管理した方が、logの中身がばらけるので計算量は減る。ここまで $N,Q$ が大きいと、その違いも馬鹿にならないかも。

豆知識

線形合同法

今回の乱数生成式 $G_{n+1}=G_n \times 48271 \mod 2^{31}-1$ は線形合同法と呼ばれる疑似乱数生成式で、特に Park & Miller によって考案されたパラメータを用いている。
結果が32bitの範囲に収まり、式の単純さの割には（あくまで割には、だが）そこそこランダムっぽい値が生成されるらしい。

昔のAtCoderでは、このように乱数を用いて生成された入力だと、そのランダム性を利用する（ランダム性が見込めることで高速に動く説明が付く解法が想定解）ということも見られたが、今回はそういう意図はなく、単純に制約の都合だったのかな。

Python3


import os
import sys

import numpy as np


def solve(inp):
    n = inp[0]
    points = np.ascontiguousarray(inp[1:2 * n + 1])
    points = points.reshape((n, 2))
    sort_index = np.argsort((points[:, 0] << 30) + points[:, 1])
    points = points[sort_index]

    q = inp[2 * n + 1]
    g0, ra, rb = inp[2 * n + 2:]
    slopes = []
    position = np.arange(n)  # 初期位置index → 現在のindex
    for i in range(n):
        x1, y1 = points[i]
        for j in range(i + 1, n):
            x2, y2 = points[j]
            if x1 == x2:
                continue
            slopes.append(((y2 - y1) / (x2 - x1), 0, i, j))

    mod1 = (1 << 31) - 1
    mod2 = 2 * ra + 1
    mod3 = 2 * rb + 1
    g = g0
    for _ in range(q):
        g1 = (48271 * g) % mod1
        g2 = (48271 * g1) % mod1
        g3 = (48271 * g2) % mod1
        g = g3

        a = g1 % mod2 - ra
        b = (g2 * mod1 + g3) % mod3 - rb

        slopes.append((float(a), 1, b, 0))

    slopes.sort()
    ans = 0

    for slope in slopes:

        if slope[1] == 0:
            oi = slope[2]
            oj = slope[3]
            i = position[oi]
            j = position[oj]
            assert i + 1 == j
            xi, yi = points[i]
            points[i, 0] = points[j, 0]
            points[i, 1] = points[j, 1]
            points[j, 0] = xi
            points[j, 1] = yi
            position[oi] = j
            position[oj] = i

        else:
            a = int(slope[0])
            b = slope[2]

            l = -1
            r = n
            while l + 1 < r:
                m = (l + r) // 2
                x, y = points[m]
                # print(f'   {l=} {r=} {m=} {x=} {y=} {a*x+b=}')
                if a * x + b > y:
                    l = m
                else:
                    r = m
            ans += n - r

    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)

目次

トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）F,G 問題メモ

F - Earn to Advance

問題

解法

G - Points and Comparison

問題

解法

豆知識