SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) D,E,F問題メモ

SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)

最近のABC、Dが伏兵なことが多い。

D - Base n

• 0～9の数字からなる文字列 $X$ と整数 $M$ が与えられる
• $X$ を $n$ 進数として解釈した値のうち、$M$ 以下であるものの個数を求めよ
• ただし $n$ は $X$ に現れる最大の数字を $d$ として、$d+1$ 以上の整数値を取る変数である
• $1 \le Xの桁数 \le 60$
• $1 \le M \le 10^{18}$

二分探索だが、コーナーケースに注意が必要。

$f(n)$ を、$X$ を $n$ 進数として解釈した後の値とする。
$X=111$ のとき、$f(2)=7$ である。

まず、$X$ が1桁の場合、1の位しかないので $f(n)$ は $n$ にかかわらず $X$ 固定である。
$X$ の値が $M$ 以下なら1通り、超過なら0通りとなる。
ここの場合分けを見落としがち（6WA）。

以下、$X$ は2桁以上とする。

$n$ が大きくなるほど $f(n)$ は大きくなる（狭義単調増加）ので、 $f(n) \le M$ が満たされる最大の $n$ を二分探索で探す。

それを $t$ とすると、$n=d+1～t$ は全て $f(n) \le M$ の条件を満たし、また $f(n)$ の値も全て異なる。

0通りの場合に注意して、$t-d$ が答え。

二分探索開始時の最小値・最大値に少し迷うところだが、、、

最小値は、$d+1$ にしてしまうとそれがそもそも不可能だった場合の区別が発生して面倒。
$X$ が $n$ 進数としてあり得ない数（ある桁に $n$ 以上の数字が含まれる）であっても、気にせず 同等の計算をして $f(n)$ を求めることは可能だし、 それでも二分探索に必要な単調増加性は崩れないので、最小値は $0$ に設定しておけばよい。

最大値については、制約上、$n$ は $X=10, M=10^{18}$ のとき最大となり、この時 $t=10^{18}$ となる。

Python3

def check(k):
    y = int(x)
    t = 1
    tmp = 0
    while y:
        tmp += t * (y % 10)
        y //= 10
        t *= k
    return tmp <= m


x = input()
m = int(input())

if len(x) == 1:
    if m < int(x):
        print(0)
    else:
        print(1)
    exit()

l = 0
r = 10 ** 18 + 1

while l + 1 < r:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid

d = int(max(x))
if l < d + 1:
    print(0)
else:
    print(l - d)

E - Train

• $N$ 個の都市を $M$ 本の鉄道が結ぶ
• $i$ 番目の鉄道は都市 $A_i$ と $B_i$ を結ぶ
  • 列車は、時刻が $K_i$ の倍数になる毎に、互いの都市からもう一方に向けて出発する
  • 所要時間は $T_i$
  • 乗り換えの時間は無視できる
• 都市 $X$ を時刻0に出発したとき、$Y$ に着ける最も早い時刻を求めよ
• たどり着けないときは -1 を出力せよ
• $2 \le N \le 10^5$
• $0 \le M \le 10^5$
• $1 \le T_i,K_i \le 10^9$

ちょっとだけ変則的な最短経路探索。

頂点 $v$ から次の頂点へ向かう辺のコストが $v$ への到着時刻によって変わりうる（次の列車を待つ時間として表現される）。

辺のコストが時刻によって可変の場合、Dijkstra法などのアルゴリズムが使えない場合があるので、確認する必要がある。

使えない場合というのは、 「ある頂点に後から到着した方が、辺のコストが下がって、先に到着するより早く次の頂点にたどり着ける」、 つまり追い抜かされるようなことが発生する場合。

今回を考えると、待ってる間に追いつかれることはあれど、追い抜かされることは無い。 よって問題なくDijkstra法が使える。

時刻 $t$ に頂点 $v$ に着き、そこから鉄道 $i$ に乗る場合、 次の頂点に付く時刻は $ceil \left ( \dfrac{t}{K_i} \right ) \times K_i + T_i$ となるので、 これを次の頂点へのコストとすればよい。

Python3

from heapq import heappop, heappush


def dijkstra(x, y, links):
    q = [(0, x)]
    visited = set()
    while q:
        cost, v = heappop(q)
        if v == y:
            return cost
        if v in visited:
            continue
        visited.add(v)
        for u, t, k in links[v]:
            if u in visited:
                continue
            new_cost = ((cost - 1) // k + 1) * k + t
            heappush(q, (new_cost, u))
    return -1


n, m, x, y = map(int, input().split())
x -= 1
y -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    a, b, t, k = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add((b, t, k))
    links[b].add((a, t, k))

print(dijkstra(x, y, links))

F - Potion

• $N$ 種類の素材、素材 $i$ は $A_i$ の魔力を持つ
• ここから1つ以上の素材を選んで合成してポーションを作る
• $k$ 種類の素材を合成したポーションの魔力は、
  • 合成直後は素材の魔力の合計値
  • そこから時間が1経過する毎に、$k$ 増加する（連続的に増えるのでは無く、1経過した瞬間に $k$ 一気に増える）
• 時刻0に一度だけ素材を合成するとき、魔力がちょうど $X$ のポーションは最速でいつ手に入るか求めよ
• $1 \le N \le 100$
• $1 \le A_i \le 10^7$
• $10^9 \le X \le 10^{18}$

ちょうどというのがポイント。

なるべく合成直後の魔力を大きくした方が待ち時間は少なくなるが、 ちょうど $X$ にならず飛び越してしまったら作れない。

合成した素材の個数 $j$ を固定してみる。

「合成した $j$ 種類の素材の合計値」と「$X$」の $\mod{j}$ が等しいとき、 しばらく待つことでちょうど魔力が $X$ のポーションを作れる。

X=93  j=10
合成直後
   43    → 53 → 63 → ... → 93

合成後、魔力は mod j が等しくなる数を小さい方から余すところなく列挙するので、いつかはXに等しくなる
逆に最初に mod j が等しくないと、Xには決してならない

よって、$\mod{j}$ が同じものの中では、合計値が大きい方が確実によい。
このあたりをまとめることで、DPが使えそう。

でも途中までは最終的な素材数がいくつになるかわからないので、とりあえずいろんな $j$ に対して求めながらDPする。

• $DP[i][j][k][l]=i$ 番目の素材まで考慮して、$j$ 個の素材を使い、$k$ で割ったあまりが $l$ であるような合計値の中での最大値

4つの添字のDPはなかなかごつい。 状態数は $N^4$ だが、まぁ $N$ が小さいのでなんとかなる。

遷移は難しくなくて、$i$ ごとに $j,k,l$ に対して以下のようにすればよい。

• $DP[i][j + 1][k][(l + A_i) \% k] \xleftarrow[\max]{} dp[i-1][j][k][l] + A_i$

で、最終的に $j=1～N$ に対して $DP[N][j][j][X\%j]$ に、 $j$ 個の素材を合成したときに魔力 $X$ のポーションを作成可能な合計値の最大値が入っているので、そこから必要な待ち時間を求め、 その中の最小値が答え。

まぁ、よく考えると添字 $k$ は他の $k$ の値を使ったりしないので、外に出して $O(N^3)$ のDPを $N$ 回やってもよかったね。

Python3

import os
import sys

import numpy as np


def solve(inp):
    n = inp[0]
    x = inp[1]
    aaa = inp[2:]
    dp = np.full((n + 1, n + 1, n), -1, np.int64)
    dp[0, :, 0] = 0
    for i in range(n):
        a = aaa[i]
        for j in range(i, -1, -1):
            for k in range(1, n + 1):
                for l in range(k):
                    if dp[j, k, l] == -1:
                        continue
                    dp[j + 1, k, (l + a) % k] = max(dp[j + 1, k, (l + a) % k], dp[j, k, l] + a)

    ans = 1 << 60
    for j in range(1, n + 1):
        total = dp[j, j, x % j]
        if total != -1:
            ans = min(ans, (x - total) // 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)

枝刈りで高速化しようとするなら、できることは様々あると思うが、

• 個数 $j$ の大きい方から試す
• どこかで暫定的な答え $t$ が得られる
• 今、考慮中の $j$ で、$A_i$ を大きい方から $j$ 個足した上で時刻 $t$ が経過しても魔力が $X$ に満たなければ、もうそれ以下の $j$ は考える必要が無い

というのが効果が大きそう（もちろん、$j$ が大きいうちは暫定的な答えがなかなか得られない入力も作ることができるので、絶対では無いが）