[CodeQUEEN 2024 予選 ABC358] G - AtCoder Tour

[Q] G - AtCoder Tour

コンテスト終了時点でFastestCodeでした！
BFSでO(HM)の解法です。難しいことはしてません。

考察
1. KがHMより大きい場合、最大値のマスでひたすら待機をすることになりそう。
2. 毎ターン最大値max_Aを獲得できれば理想解を得られる。これを前提と考えると、
3. A -= max_Aとすれば、マスを損失値として管理できる。
4. BFSで、そのマスに到達するまでの最小損失と最小ターン数をメモする。
5. 解答は、すべてのマスについて、K * max_Aからそのターンに至るまでの損失値を除いたもののうち、最大のもの。

実装

int main()
{
 ll H, W, K;
  cin >> H >> W >> K;
  ll si, sj;
  cin >> si >> sj;
  --si;
  --sj;
  vector<vector<ll>> A(H, vector<ll>(W));

  ll max_a = 0;
  rep(i, H) rep(j, W){
    cin >> A[i][j];
    chmax(max_a, A[i][j]);
  }

  // 基本的にmax_aでK回とどまると考える。損失を計算する
  rep(i, H) rep(j, W){ 
    A[i][j] -= max_a;
  }

  // BFS最大2500ターン
  // dp[i][j] = (i, j)にいるときの最小損失と、その最小ターン数
  vector<vector<ll>> dp(H, vector<ll>(W, -oo));
  vector<vector<ll>> turns(H, vector<ll>(W, 0));

  dp[si][sj] = A[si][sj];
  queue<pll> Q;
  // 初期入れ。最初のマスと、最初に移動するマスだけ独立してdpが埋まる
  rep(d, 4){
    ll ni = si + dy[d];
    ll nj = sj + dx[d];
    if (isn_field(ni, nj, H, W))
      continue;
    dp[ni][nj] = A[ni][nj];
    turns[ni][nj] = 1;
    Q.push({ni, nj});
  }

  ll turn = 1;
  while(!Q.empty()){
    if (turn > K)
      break;
    ++turn;
    ll sz = Q.size();
    while(sz--){
      ll i, j;
      tie(i, j) = Q.front();
      Q.pop();
      rep(k, 4){
        ll ni = i + dy[k];
        ll nj = j + dx[k];
        if (isn_field(ni, nj, H, W))
          continue;
        if (dp[ni][nj] >= dp[i][j] + A[ni][nj])
          continue;
        dp[ni][nj] = dp[i][j] + A[ni][nj];
        turns[ni][nj] = turn;
        Q.push({ni, nj});
      }
    }
  }

  ll ans = 0;
  ll mx = K * max_a; // 理想解
  // すべてのマスについて、そのマスでK回待機した場合のスコアを得る
  rep(i, H) rep(j, W){
    chmax(ans, mx + dp[i][j] + A[i][j] * (K - turns[i][j]));
  }
  cout << ans << endl;
}

https://atcoder.jp/contests/abc358/submissions/54623826