概要

この問題は、与えられた \(N\) 個の都市と \(M\) 本の一方通行の道路（有向グラフ）において、条件を満たすように \(K\) 日間の移動経路（パス）を選択し、得られるスコアの合計を最大化する問題です。

\(j\) 日目に都市 \(i\) に滞在したときのスコアは \((P_i \times j) \bmod Q\) であり、滞在する日（ステップ数）によってスコアが変化するため、効率的な探索が必要となります。

考察

1. 素朴なアプローチとその限界

最も単純な方法として、1日目からスタートして \(K\) 日目までのすべての移動経路を深さ優先探索（DFS）などで全探索することが考えられます。 しかし、1つの都市から平均して \(d\) 本の道路が伸びているとすると、経路の総数は \(O(d^K)\) のように指数関数的に増加します。今回の制約では \(K \le 1000\) であるため、全探索では確実に実行時間制限（TLE）になってしまいます。

2. 動的計画法（DP）の適用

「\(j\) 日目に都市 \(v\) に滞在しているときの最大スコア」を決定するために必要な情報は、「\(j-1\) 日目にどの都市にいて、そのときの最大スコアがいくらであったか」 だけです。それ以前（\(1\) 日目から \(j-2\) 日目まで）の具体的な移動経路を細かく覚えておく必要はありません。

このように、過去の最適な状態を利用して段階的に計算を進める手法である 動的計画法（DP） が非常に有効です。

具体的には、以下のように状態を定義します。 - \(dp[j][v]\) : \(j\) 日目に都市 \(v\) に滞在しているときの、それまでのスコアの合計の最大値（到達不可能な場合は \(-1\) などの無効値）

\(j\) 日目に都市 \(v\) に滞在できるのは、前日（\(j-1\) 日目）に「都市 \(v\) へ直接移動できる都市 \(u\)」に滞在していた場合のみです。したがって、遷移式は以下のようになります。

\[dp[j][v] = \max_{u \to v \text{ のルートが存在する}} (dp[j-1][u]) + (P_v \times j) \bmod Q\]

3. メモリの節約（空間計算量の削減）

\(dp[j][v]\) の値を計算するために必要なのは、直前のステップである \(dp[j-1]\) の情報だけです。\(j-2\) 日目以前のデータは必要ありません。 したがって、サイズ \(N\) の1次元配列を2つ（「前日のDPテーブル」と「今日のDPテーブル」）だけ用意し、ステップごとに使い回すことで、メモリ使用量を大幅に削減（\(O(KN) \to O(N)\)）できます。

アルゴリズム

1. グラフの逆辺の構築: 都市 \(v\) に遷移してくる元の都市 \(u\) を素早く列挙するために、各都市 \(v\) に向かって入ってくる辺（逆辺）の隣接リスト in_edges を作成します。

2. 初期化: 1日目のDPテーブル dp を作成します。1日目は好きな都市からスタートできるため、すべての都市 \(v\) について以下のように初期化します。 $\(dp[v] = (P_v \times 1) \bmod Q\)$

3. DPの遷移（\(j = 2\) から \(K\) までループ）: 各ステップ \(j\) において、新しいDPテーブル next_dp（初期値はすべて \(-1\)）を用意します。 各都市 \(v\) について、以下を行います。

   • 都市 \(v\) に入る辺を持つすべての都市 \(u\)（in_edges[v]）の中で、dp[u] の最大値 max_val を探す。
   • max_val が存在する場合（\(-1\) でない場合）、next_dp[v] = max_val + (P_v * j) % Q とする。
   • ループの最後に、dp = next_dp と更新する。

4. 答えの出力: \(K\) 日目の遷移が完了した時点での dp の最大値 max(dp) が求める答えとなります。

計算量

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

• 初期化: 各都市の1日目のスコア計算に \(O(N)\) かかります。
• DPの遷移: 1つのステップ \(j\) において、すべての都市 \(v\) とその入次数（入ってくる辺の数）を走査します。すべての都市の入次数の合計は、全体の辺の数 \(M\) に等しくなります。よって、1ステップあたりの遷移の計算量は \(O(N + M)\) です。
• これを \(K-1\) 回繰り返すため、遷移全体の計算量は \(O(K(N + M))\) となります。

制約の最大値（\(N = 1000, M = 50000, K = 1000\)）を代入すると、最悪の場合でも計算回数は約 \(5.1 \times 10^7\) 回となり、Pythonでも実行時間制限に余裕で間に合います。

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

• グラフの隣接リスト（逆辺）の保持に \(O(N + M)\) のメモリを使用します。
• DPテーブルは長さ \(N\) の1次元配列を2つ保持するだけなので、必要なメモリは \(O(N)\) です。
• したがって、全体の空間計算量は \(O(N + M)\) となり、非常に省メモリです。

実装のポイント

• 貰うDPの採用: 各都市 \(v\) に対して「どの都市から遷移できるか」を逆方向にたどる「貰うDP」の形にすることで、無駄な状態の更新を防ぎ、直感的でシンプルなコードにしています。

• 高速な入出力と最適化: Pythonにおけるループのオーバーヘッドを削減するため、sys.stdin.read を用いて入力を一括で取得しています。また、隣接リスト in_edges をリストのリストからタプルのリストに変換しておくことで、ループ内のアクセスを高速化しています。

  ソースコード

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    Q = int(data[3])

    P = [int(x) for x in data[4 : 4 + N]]

    in_edges = [[] for _ in range(N)]
    idx = 4 + N
    for _ in range(M):
        u = int(data[idx]) - 1
        v = int(data[idx + 1]) - 1
        in_edges[v].append(u)
        idx += 2

    in_edges = [tuple(edges) for edges in in_edges]

    dp = [(p * 1) % Q for p in P]

    for j in range(2, K + 1):
        next_dp = [-1] * N
        for v in range(N):
            max_val = -1
            for u in in_edges[v]:
                if dp[u] > max_val:
                    max_val = dp[u]
            if max_val != -1:
                next_dp[v] = max_val + (P[v] * j) % Q
        dp = next_dp

    print(max(dp))


if __name__ == "__main__":
    solve()

---

この解説は gemini-3.5-flash-high によって生成されました。