概要

各日に滞在する都市を選び、移動ルートに従いながら得点合計を最大化する問題です。
「\(j\) 日目に都市 \(i\) にいるときの最大得点」を状態とする動的計画法（DP）で解きます。

考察

滞在計画は長さ \(K\) の都市列なので、すべて列挙すると都市の選び方が最大で \(N^K\) 通りあり、明らかに間に合いません。

そこで、次のように考えます。

• \(j\) 日目に都市 \(v\) にいる
• その前日 \(j-1\) 日目には、都市 \(v\) へ移動できる都市 \(u\) にいたはず

つまり、都市 \(v\) に \(j\) 日目に到達するためには、辺 \(u \to v\) が存在する都市 \(u\) から来る必要があります。

したがって、

\[ dp[j][v] = j \text{ 日目に都市 } v \text{ にいるときの最大得点} \]

とすると、遷移は次のようになります。

\[ dp[j][v] = \max_{u \to v} dp[j-1][u] + ((P_v \times j) \bmod Q) \]

初日は好きな都市から始められるので、

\[ dp[1][v] = P_v \bmod Q \]

です。

ここで重要なのは、「都市 \(v\) に入ってくる辺」だけを見ればよいことです。
全都市の組み合わせを調べると \(O(KN^2)\) になり重いですが、実際に存在する辺だけを使えば \(O(KM)\) 程度で済みます。

また、\(dp[j]\) を計算するには \(dp[j-1]\) だけあれば十分なので、DP 配列は 2 次元ではなく 1 次元配列を使い回せます。

アルゴリズム

各都市 \(v\) について、「\(v\) に入ってくる都市」のリストを作ります。

例えば、辺 \(a \to b\) があるなら、rev[b] に a を追加します。

DP を次のように定義します。

• dp[v]: 現在の日に都市 \(v\) にいるときの最大得点

初期状態は 1 日目です。

\[ dp[v] = P_v \bmod Q \]

その後、2 日目から \(K\) 日目まで順に更新します。

都市 \(v\) のその日の得点を

\[ score(v, j) = (P_v \times j) \bmod Q \]

とすると、

\[ new\_dp[v] = \max_{u \in rev[v]} dp[u] + score(v, j) \]

です。

最後に、\(K\) 日目終了時点でどの都市にいてもよいので、

\[ \max_v dp[v] \]

を出力します。

実装では、毎回 \(P_v \times j\) を計算してもよいですが、コードでは各都市の得点を前日から加算して更新しています。

\[ (P_v \times j) \bmod Q = ((P_v \times (j-1)) \bmod Q + P_v) \bmod Q \]

この性質を使い、weights[v] にその日の都市 \(v\) の得点を保持しています。

計算量

• 時間計算量: \(O(K(N+M))\)
• 空間計算量: \(O(N+M)\)

\(N \leq 1000\), \(M \leq 50000\), \(K \leq 1000\) なので十分間に合います。

実装のポイント

• 初日はどの都市からでも始められるため、dp = pmod[:] とします。

• 2 日目以降に都市 \(v\) にいるには、都市 \(v\) へ入る辺が必要です。そのため、入ってくる辺を rev[v] として管理します。

• 到達不可能な状態は非常に小さい値 NEG = -10**18 で表します。

• \(K=1\) の場合は移動を考える必要がないため、単に max(P_i % Q) を出力します。

• weights[v] を毎日更新することで、\((P_v \times j) \bmod Q\) を効率よく求めています。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M, K, Q = data[0], data[1], data[2], data[3]

    P = data[4:4 + N]
    pmod = [x % Q for x in P]

    rev = [[] for _ in range(N)]
    idx = 4 + N
    for _ in range(M):
        a = data[idx] - 1
        b = data[idx + 1] - 1
        idx += 2
        rev[b].append(a)

    if K == 1:
        print(max(pmod))
        return

    nonempty = [(i, rev[i]) for i in range(N) if rev[i]]

    NEG = -10**18
    dp = pmod[:]
    weights = pmod[:]

    n = N
    q = Q
    pm = pmod
    ne = nonempty
    neg = NEG

    for _ in range(K - 1):
        old = dp
        ndp = [neg] * n
        wt = weights

        for i, ins in ne:
            wi = wt[i] + pm[i]
            if wi >= q:
                wi -= q
            wt[i] = wi

            mx = neg
            for u in ins:
                val = old[u]
                if val > mx:
                    mx = val

            ndp[i] = mx + wi

        dp = ndp

    print(max(dp))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。