Google Code Jam 2019 Round1B : Manhattan Crepe Cart

問題. Manhattan Crepe Cart

の格子上に 人がいる． 番目の人は にいて東西南北のいずれか （順番に 'E', 'W', 'S', 'N'）を向いている．すべての人はクレープ屋に最小の移動距離で移動しようとしている．ただし，距離はマンハッタン距離である．多くの人が向かう可能性のあるクレープ屋の場所を答えよ．ただし，向かう人数が同じになるクレープ屋の候補が複数ある場合は座標値が最小となるものを答えよ．

制約： ，　，　

解法．累積和

クレープ屋の場所を決めるときに東西方向と南北方向は互いに独立に決めれるので，ここでは南北方向について考える（ 座標）． 番目の人が にいて北に向かっているときに，この人が向かうクレープ屋の場所の候補は （）を満たす必要がある．同様に， 番目の人が南を向いているときは を満たす必要がある．すなわち，南北方向の座標が のクレープ屋に向かう可能性のある人数は，現在いる場所が を満たす北を向いている人数と， を満たす南を向いている人数の和である． 時間と 領域の前処理で累積和求めると，各 に対してその場所に向かう可能性のある人数を 時間で求めることができるので，それらの最大値は 時間で求まる．
同様に東西方向に対しても独立に求めれば答えが求まる．

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

void Solve() {
    int p, q;
    cin >> p >> q;

    vector<int> x(q + 2), y(q + 2);
    for (int i = 0; i < p; ++i) {
        int x_i, y_i;
        char d_i;
        cin >> x_i >> y_i >> d_i;

        if (d_i == 'N') {
            ++y[y_i + 1]; --y[q + 1];
        }
        else if (d_i == 'S') {
            --y[y_i]; ++y[0];
        }
        else if (d_i == 'E') {
            ++x[x_i + 1]; --x[q + 1];
        }
        else if (d_i == 'W') {
            --x[x_i]; ++x[0];
        }
    }

    for (int i = 1; i <= q; ++i) {
        x[i] += x[i - 1];
        y[i] += y[i - 1];
    }

    int idx_x = -1, idx_y = -1;
    for (int i = 0; i <= q; ++i) {
        if (idx_x == -1 || x[idx_x] < x[i]) idx_x = i;
        if (idx_y == -1 || y[idx_y] < y[i]) idx_y = i;
    }
    if (idx_x == -1) idx_x = 0;
    if (idx_y == -1) idx_y = 0;

    cout << idx_x << " " << idx_y << '\n';
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int T;
    cin >> T;
    for (int i_case = 1; i_case <= T; ++i_case) {
        cout << "Case #" << i_case << ": ";
        Solve();
    }

    return 0;
}

問題内容を勘違いして1時間ほどかかってしまった orz．問題を理解してからは解法はすぐ思いつく問題なのに残念すぎる．