概要

\(N\) 個の都市と一方通行の移動ルートが与えられ、\(K\) 日間にわたって都市を巡ります。\(j\) 日目に都市 \(i\) に滞在したときのスコアが \((P_i \times j) \bmod Q\) で与えられるとき、\(K\) 日間のスコアの合計の最大値を求める問題です。

考察

この問題では、\(K\) 日間の滞在計画（都市の列）の中でスコアの合計を最大化する必要があります。 すべての可能な滞在計画を列挙しようとすると、1日目の選択肢が \(N\) 通り、2日目以降も最大で \(N\) 通りの選択肢があるため、全体で \(O(N^K)\) の計算量となり、制約の \(K \le 1000\) ではTLE（実行時間超過）になります。

そこで、「\(j\) 日目に都市 \(i\) に滞在しているときの、\(j\) 日目までのスコアの最大値」を管理することを考えます。これを dp[j][i] とします。 \(j\) 日目に都市 \(i\) に滞在できるのは、\(j-1\) 日目に都市 \(u\) に滞在しており、かつ都市 \(u\) から都市 \(i\) への移動ルートが存在する場合です。したがって、以下の遷移が成り立ちます。

\[dp[j][i] = \max_{u \to i \text{の辺が存在}} (dp[j-1][u]) + (P_i \times j) \bmod Q\]

このように、前日の状態だけを使って当日の状態を更新していく手法を動的計画法（DP）と呼びます。DPを用いることで、無駄な全探索を避け、効率的に最大値を求めることができます。

アルゴリズム

1. 初期化: 1日目はどの都市からでもスタートできるため、すべての都市 \(i\) について dp[1][i] = (P_i \times 1) \bmod Q とします。
2. DPテーブルの更新: \(j = 2\) から \(K\) まで、以下の処理を繰り返します。
   • 前日のDP配列（dp_prev）を用いて、当日のDP配列（dp_curr）を更新します。
   • すべての移動ルート \(u \to v\) について、dp_curr[v] = max(dp_curr[v], dp_prev[u]) を行います。この時点では、まだ当日のスコアは加算しません。
   • すべての都市 \(i\) について、到達可能であれば当日のスコアを加算します：dp_curr[i] += (P_i \times j) \bmod Q。
3. 答えの出力: \(K\) 日目のDP配列の中にある最大値が、求めるスコアの合計の最大値です。

なお、メモリ使用量を抑えるため、\(K\) 日分の配列を全て保持するのではなく、前日と当日の2つの配列だけを使い回す（インプレース更新）ことで空間計算量を削減しています。

計算量

• 時間計算量: \(O(N + K \times M)\)
  • 初期化に \(O(N)\)、各日ごとにすべての辺を調べるのに \(O(M)\)、各日ごとにスコアを加算するのに \(O(N)\) かかるため、全体で \(O(N + K \times (M + N))\) となります。制約下では十分高速です。
• 空間計算量: \(O(N + M)\)
  • グラフの隣接リストに \(O(N + M)\)、DP配列に \(O(N)\) のメモリを使用します。

実装のポイント

• スコアの加算タイミング: 移動先の都市 \(v\) に到達可能かどうかを判定した後に、当日のスコア \((P_v \times j) \bmod Q\) を加算します。到達不可能な都市（dp_curr の値が \(-\infty\) のまま）にはスコアを加算しないように注意が必要です。

• 初期値の設定: 到達不可能な状態を表すために、十分に小さい値（例えば \(-10^{18}\) など）を初期値として設定します。

• Pythonの入力高速化: 入力サイズが大きくなる可能性があるため、sys.stdin.readline を使用して入力を受け取ることで処理を高速化しています。

  ソースコード

import sys

def solve():
    input = sys.stdin.readline
    N, M, K, Q = map(int, input().split())
    P = list(map(int, input().split()))
    
    adj = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        adj[u - 1].append(v - 1)
    
    for i in range(N):
        adj[i] = tuple(adj[i])
        
    INF = 10**18
    dp_prev = [-INF] * N
    for i in range(N):
        dp_prev[i] = (P[i] * 1) % Q
        
    for j in range(2, K + 1):
        dp_curr = [-INF] * N
        for u in range(N):
            val = dp_prev[u]
            if val == -INF:
                continue
            for v in adj[u]:
                if val > dp_curr[v]:
                    dp_curr[v] = val
        
        mul = j
        for i in range(N):
            if dp_curr[i] != -INF:
                dp_curr[i] += (P[i] * mul) % Q
                
        dp_prev = dp_curr
        
    print(max(dp_prev))

if __name__ == '__main__':
    solve()

この解説は or-glm5.2-high によって生成されました。