各操作、$X$ を小さく保てる方を貪欲に選べばよい。但しそのままシミュレーションするとTLE。
$A$ 倍は重ねる毎にすごい勢いで増え方が増すので、最初は $A$ 連打、どこかから $B$ 連打がよい。
$A$ 倍の回数は高々60回程度。ここまではシミュレートすれば良い。
$B$ を選択した方がよくなったところで、$Y-X$ を $B$ で割ると、残り $B$ を足す操作を行える回数が一発でわかる。
Python3
x, y, a, b = map(int, input().split())
ans = 0
while x * a < x + b and x * a < y:
x *= a
ans += 1
remaining = y - x - 1
ans += remaining // b
print(ans)
移動は、$x,y$ 軸方向はマンハッタン距離、高さ方向は上りはマンハッタンだが、下りはコスト不要、という具合になっている。
コストが有向なことと、三角不等式を満たすかどうかに注意。
今回、都市 $1→2$ と $2→1$ のコストが異なる。
よって、どこから始めてもいいわけではなく、ちゃんと問題文の通りに都市1から始めて、都市1に戻るコストを求める必要がある。
また、三角不等式とは3つの都市 $i,j,k$ について $dist(i→k) \le dist(i→j)+dist(j→k)$ となる関係のことだが、
これが成り立たない場合「$i→k$ に行くなら、直接行くより $j$ を経由した方が近道」となってしまい、
都市 $i,k$ の座標から求めた距離が、必ずしも最短ではなくなってしまう。
その場合、Floyd-Warshallなどで全点間最短距離を事前に求めておかないと、2都市間の真の最短距離がわからなくなる。
今回の場合はそのようなことが無いので、2点間の座標から最短距離が求められる。
都市 $2～N$ の巡回セールスマンを解く。
初期値として、各都市、その1都市だけしか訪問していない場合のコストに都市 $1$ からの距離を入れておく。
各都市 $i$ について、全都市を経由しつつ $i$ を最後に訪れた場合の最小コストに、都市 $i→1$ のコストを加算したものを計算し、
その中の最小コストが答えとなる。
$O(2^NN^2)$
Python3
def solve(n, cities):
INF = 10 ** 18
dp = [[INF] * (n - 1) for _ in range(1 << (n - 1))]
x1, y1, z1 = cities[0]
cities = cities[1:]
for i in range(n - 1):
x2, y2, z2 = cities[i]
dp[1 << i][i] = abs(x2 - x1) + abs(y2 - y1) + max(0, z2 - z1)
for b in range(1, 1 << (n - 1)):
e = b
while e:
c = e & -e
d = c.bit_length() - 1
f = b ^ c
xd, yd, zd = cities[d]
res = INF
while f:
g = f & -f
h = g.bit_length() - 1
xh, yh, zh = cities[h]
res = min(res, dp[b ^ c][h] + abs(xd - xh) + abs(yd - yh) + max(0, zd - zh))
f ^= g
dp[b][d] = min(dp[b][d], res)
e ^= c
ans = INF
for i in range(n - 1):
x2, y2, z2 = cities[i]
ans = min(ans, dp[-1][i] + abs(x1 - x2) + abs(y1 - y2) + max(0, z1 - z2))
return ans
n = int(input())
cities = [tuple(map(int, input().split())) for _ in range(n)]
print(solve(n, cities))
何かbit操作でややこしい書き方しちゃってる感。
2次元DP。遷移がこんがらがらがる。
まず、頂点の次数が2以下なので、連結成分は以下に分類できる。（孤立点もパスに含められるけど、数え上げの際に例外的なので分けて考える）
これに基づいて、以下のDPで連結成分の作り方を数えていく。
ある状態から、次に1つ新しい連結成分を作る場合の数は、「頂点の選び方」×「選んだ頂点の繋ぎ方」となる。
頂点の選び方は連結成分のサイズによって、繋ぎ方は分類（パスかサイクルか）によって異なる。
また、消費する辺の個数も分類に依存し、パスなら（サイズ－1）、サイクルならサイズと同数となる。
選び方を数え上げるに当たっては、ダブりに注意。
たとえば連結成分を2個生成する場合、どちらを先に生成しても全体としての場合の数は1つなのに、ダブって数えられることがあってはならない。
解説pdfにあるように「まだ決まっていない頂点の中で最も番号の小さいものを含む成分について決める」と考えると、重複が防止できる。
もらうDPを考えると、ある $i,j$ について遷移元となるのは以下のようになる。
j .. 7 8 9 10 ..
i ●: 計算中のi,j
.. □ △ ○: 孤立点を生成したときの遷移元
.. □ △ △: パスを生成したときの遷移元（サイズ上限 $L$ まで）
9 □ △ □: サイクルを生成したときの遷移元（サイズ上限 $L$ まで）
10 ○
11 ●
孤立点の場合、その1点を確定させるだけなので1通りしかない。
パスの場合、各サイズ $S=2～L$ につき、
サイクルの場合、各サイズ $S=2～L$ につき、
これを1個1個計算していけばよい。
最終的に $DP[N][M]$ を参照するが、これは「最大連結成分が $L$ 以下」のパターン数となる。
よって、$L$ を $L-1$ としたものについても同様に求めると、その差分で $L$ ちょうどのパターン数が求められる。
計算量は $O(NML)$ だが、$L$ にあたる部分は $DP[i][j]$ の更新では $\min(i,j,L)$ 個までしか参照されないので、だいたい3分の1くらい？になる。
Python3
import os
import sys
import numpy as np
def solve(inp):
MOD = 10 ** 9 + 7
def mod_pow(x, a, MOD):
ret = 1
cur = x
while a:
if a & 1:
ret = ret * cur % MOD
cur = cur * cur % MOD
a >>= 1
return ret
def prepare(n, MOD):
facts = np.ones(n + 1, np.int64)
for m in range(1, n + 1):
facts[m] = facts[m - 1] * m % MOD
finvs = np.ones(n + 1, np.int64)
finvs[n] = mod_pow(facts[n], MOD - 2, MOD)
for m in range(n, 1, -1):
finvs[m - 1] = finvs[m] * m % MOD
return facts, finvs
n, m, l = inp
facts, finvs = prepare(n, MOD)
inv2 = finvs[2]
def count(n, m, l):
if l <= 1:
return 0
dp = np.zeros((n + 1, m + 1), np.int64)
dp[0, 0] = 1
for i in range(1, n + 1):
dp[i] = dp[i - 1]
for j in range(1, m + 1):
for s in range(2, l + 1):
choice = facts[n - i + s - 1] * finvs[s - 1] % MOD * finvs[n - i] % MOD
if i - s >= 0 and j - s >= 0:
if s == 2:
dp[i, j] = (dp[i, j] + dp[i - s, j - s] * facts[s - 1] % MOD * choice) % MOD
else:
dp[i, j] = (dp[i, j] + dp[i - s, j - s] * facts[s - 1] % MOD * inv2 % MOD * choice) % MOD
if i - s >= 0 and j - s + 1 >= 0:
dp[i, j] = (dp[i, j] + dp[i - s, j - s + 1] * facts[s] % MOD * inv2 % MOD * choice) % MOD
else:
break
return dp[n, m]
return (count(n, m, l) - count(n, m, l - 1)) % MOD
if sys.argv[-1] == 'ONLINE_JUDGE':
from numba.pycc import CC
cc = CC('my_module')
cc.export('solve', '(i8[:],)')(solve)
cc.compile()
exit()
if os.name == 'posix':
# noinspection PyUnresolvedReferences
from my_module import solve
else:
from numba import njit
solve = njit('(i8[:],)', cache=True)(solve)
print('compiled', file=sys.stderr)
inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)