AtCoder DISCO presents ディスカバリーチャンネル コードコンテスト2020 本戦 問題B - Hawker on Graph

問題リンク

公式解説と同じ解法ではあるのですが、より素朴な発想で同じ解法に至ったので、記録しておきます。

まず、この問題の難しいところは「所持金が負となることはない」というところで、これが無ければ有名問題で、以下のようにして解けます。

\( T \) ターンかけて \( i \) から \( j \) に移動するときの利得を \( A_T [i][j] \) とします。ここで、\( A_{T_1} [i][j] \) と \( A_{T_2} [i][j] \) が各 \( i, j \) についてわかっているとします。すると、\( T_1 + T_2 \) ターンかけて \( i \) から \( j \) に移動するとき、\( T_1 \) ターン時点で \( k \) を経由する場合を各 \( k \) について考えれば良いので、\( A_{T_1 + T_2}[i][j] = \max_k \{ A_{T_1}[i][k] + A_{T_2}[k][j]  \} \) と書けます。これによって、繰り返し二乗法を使って \( A_K \) を求めることができます。計算量は \( O(N^3 \log K) \) となり、\(  N \leq 200 \) なので十分高速です。

では、「所持金が負となることはない」という条件を考えていきます。初期の所持金が \( W \) のとき、\( T \) ターンかけて \( i \) から \( j \) に移動することを考えます。ひとまず「所持金が負となることはない」という条件を無視して、辺の重みの累積和の推移をグラフにします。

すると、遷移後の所持金は次のように書けます。

• 途中で所持金が \( 0 \) にならない場合は \( W + A_T [i][j] \) になります
• 途中で所持金が \( 0 \) になる場合は、累積和が最小値になる頂点が最後の所持金が \( 0 \) になる頂点になることに注目します。そうすると、累積和の最小値を \( A_T [i][j] \) から引いた値を \( B_T [i][j] \) として、最終的な所持金は \( B_T [i][j] \) になります

したがって、遷移後の所持金の最大値は \( \max( W + A_T [i][j], B_T [i][j] ) \) となります。

あとは、\( A_K \) と同様に \( B_K \) が繰り返し二乗法で計算できれば OK です。\( B_{T_1} [i][j] \) と \( B_{T_2} [i][j] \) が各 \( i, j \) についてわかっているとします。\( T_1 \) ターン時点で \( k \) を経由して\( T_1 + T_2 \) ターンかけて \( i \) から \( j \) に移動するパスを考えます。

このとき \( B_{T_1 + T_2}[i][j] \) の値は

• 累積和の最小値が \( i - k \) 間にある場合、\( B_{T_1}[i][k] + A_{T_2}[k][j] \)
• 累積和の最小値が \( k - j \) 間にある場合、\( B_{T_2}[k][j] \)

になるので、\( B_{T_1 + T_2}[i][j] = \max_k(B_{T_1}[i][k] + A_{T_2}[k][j], B_{T_2}[k][j]) \) と書けます。これによって、\( A_K, B_K \) に対して同時に繰り返し二乗法を適用できることがわかりました。

#include <bits/stdc++.h>
 
using namespace std;
using int64 = long long;
using vvi64 = vector<vector<int64>>;
 
constexpr int DEBUG = 0;
 
template<typename T>
vector<vector<T>> Make2DVector(int d1, int d2, T default_value) {
  return vector<vector<T>>(d1, vector<T>(d2, default_value));
}
 
template<class T> inline bool UpdateMax(T& a, T b) {
  if (a < b) { a = b; return 1; } return 0;
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
 
  int n, m;
  cin >> n >> m;
  int64 initial_score;
  cin >> initial_score;
  int s;
  cin >> s;
  s--;
  int64 k;
  cin >> k;
 
  constexpr int64 INVALID = -1E18;
  auto a = Make2DVector<int64>(n, n, INVALID);
  auto b = Make2DVector<int64>(n, n, INVALID);
  for (int i = 0; i < m; i++) {
    int from;
    int to;
    int64 w;
    cin >> from >> to >> w;
    from--;
    to--;
    a[from][to] = w;
    b[from][to] = max(w, 0LL);
  }
 
  // Computes A_{T_1 + T_2} and B_{T_1 + T_2} from
  // A_{T_1}, B_{T_1}, A_{T_2} and B{T_2}.
  auto merge_fn = [&](
      const vvi64& a1, const vvi64& b1,
      const vvi64& a2, const vvi64& b2) -> tuple<vvi64, vvi64> {
    auto a = Make2DVector<int64>(n, n, INVALID);
    auto b = Make2DVector<int64>(n, n, INVALID);
    
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
          if (a1[i][k] == INVALID) continue;
          if (a2[k][j] == INVALID) continue;
 
          UpdateMax(a[i][j], a1[i][k] + a2[k][j]);
          UpdateMax(b[i][j], b1[i][k] + a2[k][j]);
          UpdateMax(b[i][j], b2[k][j]);
        }
      }
    }
    return make_tuple(a, b);
  };
 
  // Computes A_p and B_p from A and B by doubling.
  function<tuple<vvi64, vvi64>(const vvi64&, const vvi64&, int64)>
      power_fn =
          [&](const vvi64& a1, const vvi64& b1, int64 p)
              -> tuple<vvi64, vvi64> {
    if (p == 1) return make_tuple(a1, b1);
    vector<vector<int64>> a2, b2;
    tie(a2, b2) = power_fn(a1, b1, p / 2);
    tie(a2, b2) = merge_fn(a2, b2, a2, b2);
    if (p % 2 == 1) {
      tie(a2, b2) = merge_fn(a2, b2, a1, b1);
    }
    return make_tuple(a2, b2);
  };
 
  vector<vector<int64>> ap, bp;
  tie(ap, bp) = power_fn(a, b, k);
 
  int64 ans = -1;
  for (int t = 0; t < n; t++) {
    if (ap[s][t] == INVALID) continue;
    UpdateMax(ans, initial_score + ap[s][t]);
    UpdateMax(ans, bp[s][t]);
  }
 
  cout << ans << endl;
}