Overview

A problem where we need to plan a \(K\)-day stay on a directed graph to maximize the total score, where the score for each day is \((P_{c_j} \times j) \bmod Q\). This can be solved using Dynamic Programming (DP).

Analysis

Key Observation

This problem can be rephrased as: “Find a path of length \(K\) (with vertex revisits allowed) on a directed graph to maximize the sum of weighted scores.”

Issue with the Naive Approach

If we try to enumerate all possible paths, there can be up to \(N^K\) plans, which is far too slow to pass within the time limit.

Solution Strategy

Since only “which city we are in on day \(j\)” affects the next transition, a DP that manages states as pairs of \((\text{day}, \text{city})\) is effective.

Specifically:

\[dp[j][i] = \text{the maximum score of a valid plan from day 1 to day } j \text{ such that we are in city } i \text{ on day } j\]

Algorithm

DP Formulation

Initial State (Day 1):

Since we can start from any city \(i\):

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

Transitions (\(j = 2, 3, \ldots, K\)):

To be in city \(i\) on day \(j\), we must have been in some city \(u\) on the previous day (day \(j-1\)) that has an edge to city \(i\). Therefore, we use a reversed adjacency list (the set of cities that have an incoming edge to city \(i\)):

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

If there are no incoming edges, we set \(dp[j][i] = -\infty\) (unreachable).

Final Answer:

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

Concrete Example

For example, if \(N=3, K=3\) and the edges are \(1 \to 2, 2 \to 3, 2 \to 1\):

• Day 1: We can choose any of the cities 1, 2, or 3.
• Day 2: Move to a city that has an incoming edge from the city we were in on the previous day.
• Day 3: Move similarly.

At each step of the DP, we efficiently find “which city we should have been in on the previous day to maximize the score.”

Complexity

• Time Complexity: \(O(K \times (N + M))\)
  • There is a loop for \(K\) days, and in each day, we look at all edges once (traversing the reversed adjacency lists takes \(M\) operations in total).
• Space Complexity: \(O(N + M)\)
  • We only need to keep two DP arrays: one for the previous day and one for the current day (\(O(N)\)).
  • \(O(N + M)\) for the adjacency list.

With the constraints \(N \leq 1000, M \leq 50000, K \leq 1000\), the maximum number of operations is approximately \(1000 \times 50000 = 5 \times 10^7\), which is well within the time limit.

Implementation Points

• By pre-building the reversed adjacency list, we can efficiently list “which cities can transition to city \(i\)” during the transitions.

• Two DP arrays (one for the previous day dp_prev and one for the current day dp_curr) are sufficient. After computing dp_curr each day, we overwrite dp_prev with it.

• Represent unreachable states with \(-1\) (or \(-\infty\)). If there are no reachable states from the previous day during a transition, that city becomes unreachable.

• For \(K = 1\), no moves are required, so we can simply output the maximum score among all cities.

  Source Code

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()

---

This editorial was generated by claude4.6opus-thinking.