概要

\(N\) 個の都市と一方通行の \(M\) 本のルートが与えられ、\(K\) 日間の各日にちょうど \(1\) つの都市に滞在します。\(j\) 日目に都市 \(i\) に滞在すると \((P_i \times j) \bmod Q\) のスコアが得られます。隣り合う日にはルートで繋がった都市へ移動するという制約のもとで、\(K\) 日間のスコア合計の最大値を求める問題です。

考察

まず、各日に得られるスコア \((P_i \times j) \bmod Q\) は「その日にどの都市にいるか」だけで決まり、過去の滞在履歴には依存しません。つまり、\(j\) 日目のスコアは「都市」と「日付」の組だけで決まります。

このことから、ある日にどの都市にいるかが決まれば、そこまでに得られる最大スコアを記録しておけばよいという、典型的な動的計画法（DP）の構造が見えてきます。

具体的に、次の値を考えます。

\(dp_j[i]\) = 「\(j\) 日目に都市 \(i\) に滞在しているような滞在計画」における、\(1\) 日目から \(j\) 日目までのスコア合計の最大値

素朴に「すべての滞在計画を列挙する」アプローチでは、計画の総数が指数的に増えてしまい到底間に合いません。しかし上記の DP を使えば、\(j\) 日目の状態は \(j-1\) 日目の状態からの遷移だけで計算でき、効率的に解けます。

ポイントは遷移の方向です。\(j-1\) 日目に都市 \(u\) にいて、ルート \(u \to v\) が存在するなら、\(j\) 日目には都市 \(v\) にいることができます。このとき

\[dp_j[v] = \max\Bigl(dp_j[v],\; dp_{j-1}[u] + (P_v \times j \bmod Q)\Bigr)\]

と更新できます。つまり各ルートを 1 本ずつ見て、出発地の値から到着地の値を更新するという形になります。

アルゴリズム

1. 初期化（1 日目）: \(1\) 日目はどの都市からでも始められるので、すべての都市 \(i\) について $\(dp_1[i] = (P_i \times 1) \bmod Q = P_i \bmod Q\)$ とします。

2. 遷移（2 日目以降）: \(j = 2, 3, \ldots, K\) について次を行います。

   • まず \(j\) 日目に各都市 \(v\) に滞在したときに得られるスコア \(sc[v] = (P_v \times j) \bmod Q\) を計算しておきます。
   • \(j\) 日目の DP 配列 \(ndp\) を「到達不可能」を表す負の値で初期化します。
   • すべてのルート \((u, v)\) について、\(dp_{j-1}[u]\) が到達可能（非負）なら $\(ndp[v] \leftarrow \max(ndp[v],\; dp_{j-1}[u] + sc[v])\)$ と更新します。
   • 更新後の \(ndp\) を \(dp_j\) とします。

3. 答え: 最終的に \(K\) 日目の DP 配列の最大値 \(\max_i dp_K[i]\) が答えです。

到達不可能の扱いについて補足します。ルートの繋がり方によっては、ある日に滞在できない都市が出てきます。そこで「まだ到達できていない都市」は負の値（コードでは -1）でマークし、遷移元が到達不能な場合はその遷移をスキップします。これにより、不正な計画を誤って数えることを防いでいます。問題で有効な計画の存在が保証されているため、\(K\) 日目には少なくとも 1 つ非負の値が残ります。

計算量

• 時間計算量: \(O(N + K \times (N + M))\)
  • 各日について、スコア計算に \(O(N)\)、全ルートを走査する遷移に \(O(M)\) かかり、それを \(K\) 日分繰り返します。最大ケースでも \(K \times (N + M) \approx 1000 \times 51000 \approx 5 \times 10^7\) 程度で十分高速です。
• 空間計算量: \(O(N + M)\)
  • DP 配列は 1 日分（と次の日の分）のみ保持すればよく、ルート情報の保存に \(O(M)\) かかります。

実装のポイント

• DP 配列の使い回し: \(dp_j\) を計算したら \(dp_{j-1}\) はもう不要なので、配列を 2 本（または毎回新しく作る）だけ持てば十分です。\(K\) 日分すべてを保存する必要はなく、メモリを節約できます。

• スコアの事前計算: \(j\) 日目のスコア \((P_v \times j) \bmod Q\) は都市 \(v\) ごとに一度だけ計算して配列 \(sc\) に保存しておくと、遷移ループ内で同じ計算を繰り返さずに済みます。

• 遷移はルート単位で: 「到着地ごとに入ってくるルートを探す」のではなく「全ルートを 1 本ずつ見て出発地から到着地を更新する」と書くと、隣接リストを構築せずシンプルに実装できます。

• 入力の高速読み込み: \(N, M, K\) が最大 \(1000\)〜\(50000\) 規模なので、sys.stdin.buffer.read() でまとめて読み込むと入力処理が高速になり、Python でも余裕を持って間に合います。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); M = int(data[idx+1]); K = int(data[idx+2]); Q = int(data[idx+3])
    idx += 4
    P = [0] * (N + 1)
    for i in range(1, N + 1):
        P[i] = int(data[idx]); idx += 1
    edges = [(0, 0)] * M
    for k in range(M):
        u = int(data[idx]); v = int(data[idx+1]); idx += 2
        edges[k] = (u, v)

    NEG = -1
    dp = [NEG] * (N + 1)
    for i in range(1, N + 1):
        dp[i] = P[i] % Q

    for j in range(2, K + 1):
        sc = [0] * (N + 1)
        for i in range(1, N + 1):
            sc[i] = (P[i] * j) % Q
        ndp = [NEG] * (N + 1)
        for (u, v) in edges:
            du = dp[u]
            if du >= 0:
                val = du + sc[v]
                if val > ndp[v]:
                    ndp[v] = val
        dp = ndp

    print(max(dp))

main()

この解説は claude4.8opus-high によって生成されました。