ながめも

競技プログラミングについて

トップ > コンテスト参加記 > AtCoder Beginner Contest 176 ABC176 参加記

AtCoder Beginner Contest 176 ABC176 参加記

コンテスト参加記 AtCoder ABC ダイクストラ法 グリッド 最短経路問題 セグ木

50分5完で青パフォでした。 そういえば競プロを始めてから2年が経っていました。

D - Wizard in Maze

問題へのリンク

解説

見た瞬間にグリッド上でグラフを構築してダイクストラしたくなります。言語によって実行時間が厳しかったりするようですが、C++なら間に合いました。ダイクストラは以下のようにライブラリにして持っておくと便利だと思います。

実装

二次元座標を一次元座標に縮める方法がポイントです。頻出です。

template<class T> class Dijkstra {
public:
    int N;
    T inf;
    vector<T> cost;
    vector<vector<pair<T, int>>> edge;
 
    Dijkstra(const int N, T inf) : N(N), inf(inf),cost(N), edge(N) {
    }
 
    void make_edge(int from, int to, T w) {
        edge[from].push_back({ w,to });
    }
 
    void solve(int start) {
        for(int i = 0; i < N; ++i) cost[i] = inf;
 
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;
        cost[start] = 0;
        pq.push({ 0,start });
 
        while (!pq.empty()) {
            T v = pq.top().first;
            int from = pq.top().second;
            pq.pop();
            for (auto u : edge[from]) {
                T w = v + u.first;
                int to = u.second;
                if (w < cost[to]) {
                    cost[to] = w;
                    pq.push({ w,to });
                }
            }
        }
        return;
    }
};

ll H, W;
int f(int x, int y){
    return x * W + y;
}
bool IsIn(int x,int y){
    return 0<=x&&x<H&&0<=y&&y<W;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    cin >> H >> W;
    ll sx, sy;
    ll gx, gy;
    cin >> sx >> sy;
    cin >> gx >> gy;
    sx--;sy--;
    gx--;gy--;
    vector<string> S(H);
    rep(i,H)cin >> S[i];
    Dijkstra<ll> d(H*W, INFLL);
    rep(i,H)rep(j,W){
        if(S[i][j] == '#')continue;
        rep(k,4){
            int ni = i + dx[k];
            int nj = j + dy[k];
            if(not IsIn(ni,nj))continue;
            if(S[ni][nj] == '#')continue;
            d.make_edge(f(i,j), f(ni,nj), 0);
        }
        for(int p = -2; p <= 2; p++){
            for(int q = -2; q <= 2; q++){
                int ni = i + p;
                int nj = j + q;
                if(not IsIn(ni,nj))continue;
                if(S[ni][nj] == '#')continue;
                d.make_edge(f(i,j), f(ni,nj), 1);
            }
        }
    }
    d.solve(f(sx, sy));
    if(d.cost[f(gx,gy)] == INFLL){
        cout << -1 << endl;
    }
    else{
        cout << d.cost[f(gx,gy)] << endl;
    }

}

E - Bomber

問題へのリンク

解説

行を固定すると、列はどこを選べば良いでしょう？実は、列の中で最も多いところだけを確認するので良いです。

実装

列の最大をとる
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    ll H, W, M;
    cin >> H >> W >> M;
    vec<int> cntx(H,0), cnty(W,0);
    map<l_l, int> mp;
    vector<l_l> cnt_x;
    vector<l_l> cnt_y(1, {-1,-1});
    rep(i,M){
        int h, w;
        cin >> h >> w;
        h--; w--;
        cntx[h]++;
        cnty[w]++;
        mp[{h,w}]++;
    }
    rep(i,H)cnt_x.emplace_back(cntx[i], i);
    rep(j,W)cnt_y.emplace_back(cnty[j], j);
    sort(all(cnt_x), greater<>());
    sort(all(cnt_y));
    vector<int> kouho_y;
    for(int i = W; i >= 0; i--){
        kouho_y.emplace_back(cnt_y[i].second);
        if(cnt_y[i].first != cnt_y[i-1].first)break;
    }
    ll maxxy = cnt_y.back().first;
    ll ans = 0;
    rep(i,H){
        int idx = cnt_x[i].second;
        ll tmp = cnt_x[i].first;
        if(ans >= tmp + maxxy)break;
        for(auto y: kouho_y){
            chmax(ans, tmp + maxxy - (mp[{idx,y}] > 0));
            if(ans >= tmp + maxxy)break;
        }
    }
    cout << ans << endl;
}
range max queryのセグ木
/*
@title 抽象化セグ木
@category データ構造
*/
template<typename T>
class SegTree {
  public:
    int N;//葉の数
    vector<T> data;//配列
    T unit;//単位元
    function<T(T,T)> op;//区間クエリで使う処理
    function<T(T,T)> update;//点更新で使う処理
    T _query(int a, int b, int k, int l, int r) {
        if(r <= a || b <= l)return unit;
        if(a <= l && r <= b){
            return data[k];
        }
        else{
            T c1 = _query(a, b, 2 * k + 1, l, (l + r) / 2); //左の子
            T c2 = _query(a, b, 2 * k + 2, (l + r) / 2, r); //左の子
            return op(c1, c2);
        }
    }
    //コンストラクター
    //_N: 必要サイズ, _unit: 初期値かつ単位元, _op: クエリ関数, _update: 更新関数
    SegTree(int _N, T _unit, function<T(T, T)> _op, function<T(T, T)> _update) 
        :unit(_unit), op(_op), update(_update){
        N = 1;
        while(N < _N)N *= 2;
        data.assign(2 * N - 1, unit);
    }
    //i(0-indexed)の値にupdate関数を適用
    void change(int i, T x){
        i += N - 1;
        data[i] = update(data[i], x);
        while(i > 0){
            i = (i - 1) / 2;
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2]);
        }
    }
    //[a, b)の区間クエリの実行
    T query(int a, int b){
        return _query(a, b, 0, 0, N);
    }
    //添字でアクセス
    T operator[](int i) {
        return data[i + N - 1];
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    ll H, W, M;
    cin >> H >> W >> M;
    auto f = [&](long long a, long long b){
        return max(a, b);
    };
    auto g = [&](long long a, long long b){
        return a + b;
    };
    SegTree<long long> Tree(W,0,f,g);
    vvec<int> v(H);
    rep(i,M){
        int h, w;
        cin >> h >> w;
        h--;w--;
        v[h].emplace_back(w);
        Tree.change(w, 1);
    }
    ll ans = 0;
    rep(i,H){
        for(auto j: v[i])Tree.change(j, -1);
        ll tmp = v[i].size() + Tree.query(0,W);
        chmax(ans, tmp);
        for(auto j: v[i])Tree.change(j, 1);
    }
    cout << ans << endl;
}

F - Brave CHAIN

問題へのリンク

DPっぽかったですがまた解法を確認していません。