TopCoder Single Round Match 797

0完ですがHack１成功でレートは若干プラス。

Div1 Easy FlightPlan

　使える高さを固定すれば、スタートからゴールまで最低何歩で行けるかはBFSで書けるので、高さを全探索すれば良い。ただ、$O(N^4)$をPythonで通すのは無理。頑張ってC++を書いたものの、システムテストで落ちてしまった。

　注意すべきは二点。

・（BFSの書き方にもよるけど）スタート地点が全探索時の高さより高いときバグる可能性がある。

・オーバーフロー。全探索する高さをintにしていたら、高さ*cupなどの計算でオーバーフローしていた。

　この二つに引っ掛かってたのでダメ。特に一点目は、Pythonで書いててもミスってた可能性がありますね……。

　以下、システムテストを通ったコード。

#include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;
 
class FlightPlan
{
public:
  long long fly(int R, int C, vector<int> H, int cup, int cdn, int clr)
  {
    set<long long> S;
    S.clear();
    vector<long long> DP(R * C);
 
    for (int i = 0; i < R * C; i += 1)
    {
      DP[i] = 9999;
      S.insert(H[i]);
    }
    DP[0] = 0;
 
    long long ANS = 1000000000000000000;
 
    for (auto s : S)
    {
      if (s < H[0])
      {
        continue;
      }
      if (s < H[R * C - 1])
      {
        continue;
      }
      deque<int> Q;
      Q.push_back(0);
 
      for (int i = 0; i < R * C; i += 1)
      {
        DP[i] = 9999;
      }
      DP[0] = 0;
 
      while (Q.size())
      {
        int x = Q.front();
        Q.pop_front();
        int r = x / C;
        int c = x % C;
 
        if (r + 1 < R && H[(r + 1) * C + c] <= s && DP[(r + 1) * C + c] > DP[r * C + c] + 1)
        {
          DP[(r + 1) * C + c] = DP[r * C + c] + 1;
          Q.push_back((r + 1) * C + c);
        }
 
        if (r - 1 >= 0 && H[(r - 1) * C + c] <= s && DP[(r - 1) * C + c] > DP[r * C + c] + 1)
        {
          DP[(r - 1) * C + c] = DP[r * C + c] + 1;
          Q.push_back((r - 1) * C + c);
        }
 
        if (c + 1 < C && H[r * C + c + 1] <= s && DP[r * C + c + 1] > DP[r * C + c] + 1)
        {
          DP[r * C + c + 1] = DP[r * C + c] + 1;
          Q.push_back(r * C + c + 1);
        }
 
        if (c - 1 >= 0 && H[r * C + c - 1] <= s && DP[r * C + c - 1] > DP[r * C + c] + 1)
        {
          DP[r * C + c - 1] = DP[r * C + c] + 1;
          Q.push_back(r * C + c - 1);
        }
 
        if (DP[(R - 1) * C + C - 1] < 9999)
        {
          long long ANSX = 0;
          ANSX += (s - H[0]) * cup;
          ANSX += (s - H[(R - 1) * C + C - 1]) * cdn;
          ANSX += DP[(R - 1) * C + C - 1] * clr;
 
          if (ANS > ANSX)
          {
            ANS = ANSX;
          }
        }
      }
    }
    return ANS;
  }
};