AtCoder Beginner Contest 037 D - 経路

,

http://abc037.contest.atcoder.jp/tasks/abc037_d

atcoderでcinを殺してくるの珍しい。油断してTLEした。

solution

なんらかの愚直な計算をすればよい。$O(HW)$。 実装は以下のいづれか。

  • 左上から右下へ順に、メモ化再帰
  • 値の大きいものからソートして順に、DP

implementation

入力の量が大きい。scanf/printfを使う。

clang + cin/coutだとTLEする。gccだと大丈夫。10倍ぐらいの速度差があったとのことである。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <tuple>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, 1, -1 };
const int mod = 1e9+7;
int main() {
    int h, w; scanf("%d%d", &h, &w);
    vector<vector<int> > a(h, vector<int>(w));
    vector<tuple<int,int,int> > q;
    repeat (y,h) repeat (x,w) {
        scanf("%d", &a[y][x]);
        q.push_back(make_tuple(a[y][x], y, x));
    }
    sort(q.rbegin(), q.rend());
    int ans = 0;
    vector<vector<int> > dp(h, vector<int>(w, 1));
    for (auto it : q) {
        int ayx, y, x; tie(ayx, y, x) = it;
        repeat (i,4) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (0 <= ny and ny < h and 0 <= nx and nx < w) {
                if (ayx < a[ny][nx]) {
                    dp[y][x] = (dp[y][x] + dp[ny][nx]) % mod;
                }
            }
        }
        ans = (ans + dp[y][x]) % mod;
    }
    printf("%d\n", ans);
    return 0;
}