Eに嘘解法があったらしいとはいえ、A～Eを60分で200位、100分で360位はなかなか参加者レベルのインフレを感じる。
たとえば $M$ 日まであと10日の段階で、11日後以降に報酬が得られるバイトを受けても意味が無い。
あと1日の段階では $A_i=1$ のものしか受ける意味が無いので、その中から報酬最大のものを受けるのがよい。
あと2日の段階では、$A_i \le 2$ のバイトが受けられる。 そのうち、明日受けるものをわざわざ今日受けなくてもいいので、 明日受けると決めたものを除いた中から報酬最大のものを受けるのがよい。
このように、制約が強い後ろの日から考える。 「受ける意味のあるバイト候補リスト」を持ち、$M$ まであと $k$ 日の時に、
という処理を繰り返すとよい。この候補リストには、最大値を得る優先キューが使える。
キューが空になった時などの例外処理に注意。
import sys
from heapq import heappush, heappop
n, m = list(map(int, input().split()))
works = []
for line in sys.stdin:
a, b = map(int, line.split())
if a > m:
continue
works.append((a, b))
works.sort(reverse=True)
q = []
ans = 0
for i in range(1, m + 1):
while works and works[-1][0] <= i:
a, b = works.pop()
heappush(q, -b)
if q:
b = -heappop(q)
ans += b
print(ans)
ボタンを押した時に引かれるポイントは通過した辺の数に依存するので、辺ごとにコストに含めてしまってよい。
また、グラフ上で2点間の距離を求めるアルゴリズムは、だいたい最小値を求めるので、 今回のように最大値を求めたい場合は正負逆転して考える。
すると、辺の「コスト」は、$P-C_i$ として扱えばよさそう。
最小コストを求めるには、リンクに負のコストが現れるのでDijkstraは使えず、Bellman-Fordを使うことになる。
| アルゴリズム | 目的 | 計算量 | 制約 |
|---|---|---|---|
| ダイクストラ法 | 単一始点から全頂点への距離 | $O((E+V)\log{V})$ など | リンクコストは非負 |
| ベルマン-フォード法 | 単一始点から全頂点への距離 | $O(VE)$ | |
| ワーシャル–フロイド法 | 全頂点間距離 | $O(V^3)$ |
Bellman-Fordは負の閉路があった場合に検出できる。
今回の場合「その閉路を通った後 $N$ に行けるか？」を確かめる必要がある。以下の2つの方法が考えられる。
1から到達できない閉路は、Bellman-Fordでも検出されないので特別な考慮の必要は無い。
import sys
def solve(n, links, parents, costs):
q = [n - 1]
reachable = set()
while q:
v = q.pop()
if v in reachable:
continue
reachable.add(v)
q.extend(u for u in parents[v] if u not in reachable)
for v in reachable:
links[v] &= reachable
INF = 10 ** 12
dist = [INF] * n
dist[0] = 0
for _ in range(len(reachable)):
updated = False
for v in reachable:
d = dist[v]
if d == INF:
continue
cv = costs[v]
for u in links[v]:
if dist[u] > d + cv[u]:
dist[u] = d + cv[u]
updated = True
if not updated:
break
else:
return -1
return max(0, -dist[n - 1])
n, m, p = list(map(int, input().split()))
INF = 10 ** 12
links = [set() for _ in range(n)]
parents = [set() for _ in range(n)]
costs = [[INF] * n for _ in range(n)]
for line in sys.stdin:
a, b, c = map(int, line.split())
a -= 1
b -= 1
links[a].add(b)
parents[b].add(a)
costs[a][b] = min(costs[a][b], p - c)
print(solve(n, links, parents, costs))
愚直には、連立方程式が $p$ 個あり、変数が $p$ 個あるので、行列として考えて、掃き出し法で解ける。ただし、計算量は $O(p^3)$ となり、間に合わない。
行列の各行が全て等比数列の場合に特化した研究があるらしく、ヴァンデルモンドの行列式というらしい。
この場合、逆行列を $O(p^2)$ で求められるので、間に合う。というか上記Wikipediaの「応用」で述べられていることが、そのまま問題となっている。 具体的な逆行列の求め方は、英語版のVandermonde_matrixあたりに載ってそう？（未確認）
で、この解法はまあ知ってるか知ってないか感が強くて、思いつくのは厳しい。
ただし、今回の場合は、もう少しヒラメキ寄りの解法が使えて、それが解説pdfで解説されている。
$x(0 \le x \lt p)$ に対して、フェルマーの小定理から以下が言える。
\[ x^{p-1} \equiv \left\{ \begin{array}{ll} 0 & (x=0) \\ 1 \mod{p} & (otherwise) \end{array} \right. \]
なので、たとえば $x=3$ の時に $f(x)=1$ としたい場合、
$$f(x)=1-(x-3)^{p-1}$$
とすると、綺麗に $x=3$ の時のみ1、後は0 となる。
さらにこれは好きなだけ繋げられて、$x=3,5,8$ の時だと以下のようにできる。
$$f(x)=1-(x-3)^{p-1}+1-(x-5)^{p-1}+1-(x-8)^{p-1}$$
なので、$a_i=1$ である $i$ に対して $1-(x-i)^{p-1}$ を繋げることによって、目的の関数が得られる。
あとはこれを展開して、各係数 $b_i$ を求める。
$(x+k)^{p-1}$ の展開形における $x$ の係数は、二項係数を使って
$$\displaystyle (x+k)^{p-1} = x^{p-1} + \binom{p-1}{1}x^{p-2}k + \binom{p-1}{2}x^{p-3}k^2 + ... + \binom{p-1}{p-2}xk^{p-2} + k^{p-1}$$
なので、二項係数と $k$ の等比数列 $1,k,k^2,...,k^{p-1}$ を掛け合わせると、各項の係数に加算すべき値が分かる。
計算量を把握すると、
Pythonではなかなか $O(p^2)$ が厳しいが、NumPyを使って等比数列を $k=0～p-1$ について一括で求めるようにすれば間に合う。
というか、等比数列を必要な $k$ ごとに個別に求めるとTLEだったのに、一括で計算すると不要な $k$ まで含んでいるにもかかわらず500ms程度にまで高速化されたので、ほぉ～やっぱNumPyは速いんすねぇ～となる。
import numpy as np
p = int(input())
aaa = list(map(int, input().split()))
bins = [1]
for i in range(1, p):
bins.append(bins[-1] * (p - i) * pow(i, p - 2, p) % p)
bins = np.array(bins, dtype=np.int32)
pows_base = -np.arange(p, dtype=np.int32)
pows = np.zeros((p, p), dtype=np.int32)
pows[:, p - 1] = 1
for i in range(p - 2, -1, -1):
pows[:, i] = pows[:, i + 1] * pows_base % p
coefs = np.zeros(p, dtype=np.int32)
for i, a in enumerate(aaa):
if a == 0:
continue
coefs[0] += 1
coefs = (coefs - bins * pows[i]) % p
print(*coefs)