ちょっと実装多めのABC相当。EはPython, PyPyでTLEが取れず。
自分が未来予知能力を得たらどのように行動するかを考えると、明日、株価が1円でも上がるなら、有り金全部使って買って、明日売ればよい。
逆に下がるなら、今日は全て現金化して、明日（以降）買えばよい。
すると、連続で株価が上がろうと下がろうと、毎日、以下の行動を繰り返せばよいことが分かる。
最終日は現金を最大化したいので、買わないとする。
これをシミュレートすると通る。
意図的なテストケースでは、株価が 100, 200, 100, 200, … を繰り返したとき、2日で所持金を2倍にできる。
つまり、80日間で $2^{40} \times 1000 \simeq 10^{15}$ で1000兆円にもなる！（アメリカの国家予算の約2倍、ベゾスの約63倍）
逆に言うと、$DP[i日目][j株所持] = 所持現金の最大値$ というようなDPを作ってしまうと、爆発的に $j$ が増え、TLEする。（制約が小さいので騙されがち）
import sys
n, *aaa = map(int, sys.stdin.buffer.read().split())
stock = 0
cash = 1000
aaa.append(0)
for a_today, a_tomorrow in zip(aaa, aaa[1:]):
cash += stock * a_today
stock = 0
if a_today < a_tomorrow:
stock = cash // a_today
cash -= stock * a_today
print(cash)
公式pdfの解法1の途中までの $O(3^N N^2)$ 解法で、TLEになるはずなんだけど、通った。（計算量見積もり間違えてるかも？）
単純化して縦に敷く鉄道のみで考えると、鉄道を敷設する座標は街のどれかと一致させるのが最適となることが分かる。
たとえば、どの街のx座標でもない箇所に鉄道を敷いたとして
| 200
300 |<-2-o 300 x 3 + 200 x 2 = 1300
o-3->|
単純化のため各街の最寄りの路線が変化しないとして
左右のどちらかに1ずらす時のコスト変化を考えると、
どちらかは必ずコストを悪化させずにずらすことが出来る。
これを繰り返せば、左右適切な方の街のx座標までずらして、悪化することはない
| 200
|<---5----o 300 x 0 + 200 x 5 = 1000
o
300
実際は途中で最寄りの路線が変化することもあるが、その場合
なので、どちらにしろ改善する。
横に敷く鉄道でも同じことが言えるので、敷設する意味のある候補は1つの街につき縦・横の2本で $2N$ 箇所に限られる。
問題では $K$ ごとに答えを求めよとあるが、実装上は $N$ 個の街に鉄道を敷設する・しないの $2^N$ パターンを全探索して、 敷設する街が $k$ 個なら $k$ 個の場合の答えを更新することにする。
ひょっとすると複数の街で敷設する路線がかぶり、通る街は $k$ 個でも実質的に敷設する路線は $k$ 本でないかも知れないが、最小値を求める上では特に気にしなくともよい。
敷設すると決め打った街が $k$ 個とすると、さらにそれぞれで縦・横の計 $2^k$ パターンがあるので、これもループ内で全探索する。
そこでやっと敷設すると決め打つ路線が確定するので、$O(Nk)$ 使って各街からの歩行距離を求め、人口を掛け合わせてコストを算出し、$K=k$ の場合の答えを更新する。
計算量は、$\displaystyle \sum_{k=0}^{N} {}_NC_{k}2^k Nk = 2 \times 3^{N - 1} N^2$ なので、$O(3^N N^2)$ となる。
各街からの歩行距離を求めるとき、$k$ 個の街については既に0であることが分かっているので飛ばすようにすると、
$\displaystyle \sum_{k=0}^{N} {}_NC_{k}2^k (N-k)k = 2 \times 3^{N - 2} (N-1)N$ となり、ざっくり $\frac{1}{3}$ くらいにはなる、はず。
また、Numbaを使わないと、この方法ではPyPyでもTLEだった。
敷設すると決め打つ街のbit集合ごとに、以下の2つのbit演算が必要になる。
'1' が立っている数(bit count)を数える1011 を 1001 と 0010 に分ける
'1' が立っている数のカウントは、素のPythonでは bin(x).count('1') が十分速いと言われているが、PyPyやNumbaでは文字列を介するので高速化の妨げとなる。
以下で示すようなアルゴリズムが使える。
また、bitの部分集合を全探索する方法は、以下のようなテクニックが使える。
以下の例では、$b$ を鉄道を敷設する街全体のbit集合、$v$ を縦に敷く街のbit集合、$h$ を横に敷く街のbit集合として、 $b$ で立っているbitの部分集合を $v$ が 全探索している。$v$ と $b$ のXORを取ることで、補集合 $h$ が得られる。
b = 0b001101101
v = b
while v:
h = v ^ b
print(f'{v:09b}')
print(f'{h:09b}')
v = (v - 1) & b # ←この操作が鍵
ただし、この方法では $v = ∅$ だけは探索されないので、別途調べる必要がある。
import os
import sys
import numpy as np
def solve(inp):
n = inp[0]
xxx = inp[1::3]
yyy = inp[2::3]
ppp = inp[3::3]
ans = np.full(n + 1, 10 ** 18, dtype=np.int64)
default_dist = np.zeros(n, dtype=np.int64)
for i in range(n):
default_dist[i] = min(abs(xxx[i]), abs(yyy[i]))
for bit in range(1 << n):
k = (bit & 0x5555) + (bit >> 1 & 0x5555)
k = (k & 0x3333) + (k >> 2 & 0x3333)
k = (k & 0x0f0f) + (k >> 4 & 0x0f0f)
k = (k & 0x00ff) + (k >> 8 & 0x00ff)
i = 0
cur = 0
t = bit
selected = np.zeros(k, dtype=np.int64)
is_selected = np.zeros(n, dtype=np.int8)
while t:
if t & 1:
selected[cur] = i
is_selected[i] = 1
cur += 1
t >>= 1
i += 1
for bit2 in range(1 << k):
cost = 0
for i in range(n):
if is_selected[i]:
continue
town_dist = default_dist[i]
t = bit2
for j in range(k):
if t & 1:
town_dist = min(town_dist, abs(yyy[selected[j]] - yyy[i]))
else:
town_dist = min(town_dist, abs(xxx[selected[j]] - xxx[i]))
t >>= 1
cost += town_dist * ppp[i]
ans[k] = min(ans[k], cost)
return ans
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('\n'.join(map(str, ans)))
'U', 'D', 'L', 'R' $\}$ で、それぞれ $x$ 軸または $y$ 軸に平行な上、下、左、右を示す図入りの公式pdfがわかりやすい。
衝突する飛行機は、どういった向き・配置になっているか考えると、
↓
・・・
→・・・←
・・・
↑
同じ45度線上に位置するかどうかは、$x+y$（＼）や $x-y$（／）が一致するかどうかで判定できる。
なので、以下の情報を持っておく。
そして、方向の組み合わせ6組に対して、衝突しうる全ての飛行機の衝突までの時間を算出していく。
たとえば →と↓ の組なら、$x-y$ が同じになるものが衝突するので、$PLANES[R][2]$ と $PLANES[D][2]$ を使う。
両者に共通する $v$ があれば、そのリスト内の飛行機は衝突の可能性がある。
一方をソートし、もう一方を二分探索することで、衝突する飛行機の中で最も近いものと衝突するまでの時間が求められる。
軸が同じ（↑と↓、→と←）に関しては、距離の半分が衝突するまでの移動距離。なので距離x5が衝突までの時間。
軸が異なるもの（↑と→など）に関しては、$x$ 座標の差分がそのまま衝突までの移動距離。距離x10が衝突までの時間。
→
｜→
｜｜
｜｜ →
｜｜ ｜
｜｜ ｜ ↑
｜｜ ｜ ｜→
1 2 4 7 : x+yが同じ→方向の飛行機のx座標リスト
6 : x+yが同じ↑方向の飛行機の中の1つのx座標
[1 2 4 7] の中で 6 未満の座標である [1 2 4] は全て衝突するが、
その中でも最も大きいもの（4）が最も直近で衝突する。
これを二分探索なり尺取法で求める。
x座標の差が、そのまま衝突までの距離となる
計算量は、$N$ 機の飛行機の情報がPLANES内に分散するものの、
これは並列なので、まとめても $O(N \log{N})$ となる。
from bisect import bisect
from collections import defaultdict
n = int(input())
up = [defaultdict(list), defaultdict(list), defaultdict(list)]
dp = [defaultdict(list), defaultdict(list), defaultdict(list)]
lp = [defaultdict(list), defaultdict(list), defaultdict(list)]
rp = [defaultdict(list), defaultdict(list), defaultdict(list)]
for _ in range(n):
x, y, u = input().split()
x = int(x)
y = int(y)
if u == 'U':
up[0][x].append(y)
up[1][x + y].append(x)
up[2][x - y].append(x)
elif u == 'D':
dp[0][x].append(y)
dp[1][x + y].append(x)
dp[2][x - y].append(x)
elif u == 'L':
lp[0][y].append(x)
lp[1][x + y].append(x)
lp[2][x - y].append(x)
else:
rp[0][y].append(x)
rp[1][x + y].append(x)
rp[2][x - y].append(x)
def crush_time(planes1, planes2, idx):
""" 初期位置の座標が小さい方をplanes1にすること """
result = INF
for xy in planes1[idx]:
if xy not in planes2[idx]:
continue
s = planes1[idx][xy]
s.sort()
for x in planes2[idx][xy]:
i = bisect(s, x)
if i > 0:
result = min(result, x - s[i - 1])
return result
INF = 10 ** 18
ans = min(
crush_time(up, dp, 0) * 5,
crush_time(rp, lp, 0) * 5,
crush_time(rp, up, 1) * 10,
crush_time(dp, lp, 1) * 10,
crush_time(up, lp, 2) * 10,
crush_time(rp, dp, 2) * 10,
)
if ans == 5 * INF:
print('SAFE')
else:
print(ans)