概要

有向グラフ上で \(K\) 日間の滞在計画を立て、各日のスコア \((P_{c_j} \times j) \bmod Q\) の合計を最大化する問題。動的計画法（DP）で解ける。

考察

重要な気づき

この問題は「有向グラフ上で長さ \(K\) のパス（頂点の再訪問あり）を見つけ、重み付きスコアの合計を最大化する」問題と言い換えられます。

素朴なアプローチの問題

全ての経路を列挙しようとすると、最大で \(N^K\) 通りの計画が存在し得るため、到底間に合いません。

解決の方針

「\(j\) 日目にどの都市にいるか」だけが次の遷移に影響するため、状態を \((\text{日目}, \text{都市})\) の組で管理する DP が有効です。

具体的には：

\[dp[j][i] = \text{1日目から } j \text{ 日目まで有効な計画で、} j \text{ 日目に都市 } i \text{ にいるときの最大スコア}\]

と定義します。

アルゴリズム

DP の定式化

初期状態（1日目）：

任意の都市 \(i\) から出発できるので：

\[dp[1][i] = (P_i \times 1) \bmod Q\]

遷移（\(j = 2, 3, \ldots, K\)）：

\(j\) 日目に都市 \(i\) にいるためには、前日（\(j-1\) 日目）に都市 \(i\) への辺を持つ都市 \(u\) にいる必要があります。そこで 逆隣接リスト（都市 \(i\) への入辺を持つ都市の集合）を使います：

\[dp[j][i] = \max_{u \in \text{rev\_adj}(i)} dp[j-1][u] + (P_i \times j) \bmod Q\]

入辺が存在しない場合、\(dp[j][i] = -\infty\)（到達不可能）とします。

最終的な答え：

\[\text{answer} = \max_{i=1}^{N} dp[K][i]\]

具体例

例えば \(N=3, K=3\) で辺が \(1 \to 2, 2 \to 3, 2 \to 1\) の場合：

• 1日目：都市1, 2, 3 のどれでも選べる
• 2日目：前日の都市から辺がある都市に移動
• 3日目：同様に移動

DP の各ステップで「前日にどの都市にいれば最大スコアになるか」を効率的に求めています。

計算量

• 時間計算量: \(O(K \times (N + M))\)
  • \(K\) 日分のループがあり、各日で全辺を1回ずつ見る（逆隣接リストの走査は全体で \(M\) 回）
• 空間計算量: \(O(N + M)\)
  • DP 配列は前日分と当日分の2つだけ保持すればよい（\(O(N)\)）
  • 隣接リストに \(O(N + M)\)

制約 \(N \leq 1000, M \leq 50000, K \leq 1000\) より、計算量は最大で約 \(1000 \times 50000 = 5 \times 10^7\) 程度であり、十分高速です。

実装のポイント

• 逆隣接リストを事前に構築しておくと、遷移の際に「都市 \(i\) に来られる都市はどこか」を効率的に列挙できる。

• DP 配列は2本（前日分 dp_prev と当日分 dp_curr）だけで十分。毎日 dp_curr を計算した後、dp_prev に上書きする。

• 到達不可能な状態を \(-1\)（または \(-\infty\)）で管理し、遷移時に到達可能な前日の状態が1つもなければその都市は到達不可能とする。

• \(K = 1\) の場合は移動が不要なので、単に全都市のスコアの最大値を出力すればよい。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    P = [0] * (N + 1)
    for i in range(1, N + 1):
        P[i] = int(input_data[idx]); idx += 1
    
    # adj[v] = list of cities that have an edge TO v (reverse adjacency)
    # We need: for each city v, which cities u have edge u -> v
    rev_adj = [[] for _ in range(N + 1)]
    # Also store forward adjacency to know which cities have outgoing edges
    fwd_adj = [[] for _ in range(N + 1)]
    
    for _ in range(M):
        a = int(input_data[idx]); idx += 1
        b = int(input_data[idx]); idx += 1
        fwd_adj[a].append(b)
        rev_adj[b].append(a)
    
    # DP approach:
    # dp[j][i] = maximum score achievable by staying at city i on day j
    # using a valid plan from day 1 to day j.
    #
    # Base case: dp[1][i] = (P[i] * 1) % Q for all i
    # Transition: dp[j][i] = max over u in rev_adj[i] of dp[j-1][u] + (P[i] * j) % Q
    #
    # But we also need to ensure that from day j, the plan can continue to day K.
    # Actually, the problem says "有効な滞在計画が少なくとも1つ存在する" is guaranteed,
    # and we just need to maximize over all valid K-day plans.
    # A plan must have length exactly K, so we need dp[K][i] for some i.
    #
    # However, we need to be careful: if K >= 2, on day j < K, city i must have
    # at least one outgoing edge to continue. But actually, we just need the full
    # path to exist. The DP forward ensures connectivity, and as long as dp[K][i]
    # is reachable, it's fine.
    #
    # Wait, but what if at day j < K we're at city i with no outgoing edges?
    # Then we can't continue. So we need to handle reachability.
    #
    # Approach: dp[j][i] = best score for days 1..j ending at city i, or -infinity if impossible.
    # For day j < K, city i must have at least one outgoing edge (otherwise we can't continue,
    # but actually that's handled naturally: if city i has no outgoing edge and j < K,
    # then dp[j][i] won't contribute to any dp[j+1][*], so it's fine).
    # Actually we just need max over i of dp[K][i].
    
    NEG_INF = -1
    
    # Use arrays for efficiency
    # dp_prev[i] for i in 0..N (1-indexed)
    dp_prev = [NEG_INF] * (N + 1)
    
    # Day 1
    for i in range(1, N + 1):
        dp_prev[i] = (P[i] * 1) % Q
    
    # If K == 1, answer is max of dp_prev
    if K == 1:
        print(max(dp_prev[1:]))
        return
    
    for j in range(2, K + 1):
        dp_curr = [NEG_INF] * (N + 1)
        score_j = [0] * (N + 1)
        for i in range(1, N + 1):
            score_j[i] = (P[i] * j) % Q
        
        for i in range(1, N + 1):
            # Find max dp_prev[u] for u in rev_adj[i]
            best = NEG_INF
            for u in rev_adj[i]:
                if dp_prev[u] > best:
                    best = dp_prev[u]
            if best != NEG_INF:
                dp_curr[i] = best + score_j[i]
        
        dp_prev = dp_curr
    
    print(max(dp_prev[1:]))

if __name__ == '__main__':
    main()

---

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