スコルの知恵袋

主にプログラミング関係の気になったこと等をまとめたブログ

AtCoder Beginner Contest 176 感想

競プロ 競プロ日記

atcoder.jp

AtCoderは好調。こどふぉは不調。世界のバランスは保たれている。

A - Takoyaki

提出コード

リンク： https://atcoder.jp/contests/abc176/submissions/16096210

void solve() {
    ll N, X, T;
    cin >> N >> X >> T;
    prints()((N + X - 1) / X * T);
}

B - Multiple of 9

問題名を見て一瞬冷や汗をかいた（みんなのトラウマ）。

提出コード

リンク： https://atcoder.jp/contests/abc176/submissions/16100219

void solve() {
    string S;
    cin >> S;
    ll sum = 0;
    for (auto c : S) {
        sum += c - '0';
    }
    prints()(sum % 9 == 0 ? "Yes" : "No");
}

C - Step

提出コード

リンク： https://atcoder.jp/contests/abc176/submissions/16106741

void solve() {
    ll N;
    cin >> N;
    Vl A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
    ll mx = 0;
    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        ans += max(mx - A[i], 0ll);
        chmax(mx, A[i]);
    }
    prints()(ans);
}

D - Wizard in Maze

ダイクストラだろうとはすぐに思ったけど、計算量は係数がかなり大きめの O(HW \log HW) なので一瞬ためらった。 でも、順位表を見ると光速でACしてる人がたくさんいたので安心して提出した。

実際、実行時間は 249ms でかなり余裕だった。

[追記]
解説によれば O(HW) で解けるらしいです（笑）

提出コード

リンク： https://atcoder.jp/contests/abc176/submissions/16123764

using Pos = array<ll, 2>;
int cell[1010][1010];
int dp[1010][1010];
 
void solve() {
    ll H, W;
    cin >> H >> W;
    Pos s, t;
    cin >> s[0] >> s[1];
    cin >> t[0] >> t[1];
    --s[0], --s[1], --t[0], --t[1];
    for (ll i = 0; i < H; i++) {
        string a;
        cin >> a;
        for (ll j = 0; j < W; j++) {
            cell[i][j] = a[j] == '#';
        }
    }
 
    for (ll i = 0; i < H; i++) {
        for (ll j = 0; j < W; j++) {
            dp[i][j] = I_INF;
        }
    }
 
    using Tup = tuple<int, int, int>;
    priority_queue<Tup, vector<Tup>, greater<Tup>> pq;
    pq.emplace(0, s[0], s[1]);
    dp[s[0]][s[1]] = 0;
    constexpr Pos steps[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    while (!pq.empty()) {
        auto [c, x, y] = pq.top();
        pq.pop();
        if (c > dp[x][y]) continue;
        for (ll i = 0; i < 4; i++) {
            int nx = x + steps[i][0];
            int ny = y + steps[i][1];
            int nc = c;
            if (!(nx >= 0 && nx < H && ny >= 0 && ny < W)) continue;
            if (cell[nx][ny] == 1) continue;
            if (dp[nx][ny] <= nc) continue;
            dp[nx][ny] = nc;
            pq.emplace(nc, nx, ny);
        }
        for (ll i = 0; i < 5; i++) {
            for (ll j = 0; j < 5; j++) {
                int nx = x + i - 2;
                int ny = y + j - 2;
                int nc = c + 1;
                if (!(nx >= 0 && nx < H && ny >= 0 && ny < W)) continue;
                if (cell[nx][ny] == 1) continue;
                if (dp[nx][ny] <= nc) continue;
                dp[nx][ny] = nc;
                pq.emplace(nc, nx, ny);
            }
        }
    }
    int ans = dp[t[0]][t[1]];
    if (ans == I_INF) {
        prints()(-1);
    }
    else {
        prints()(ans);
    }
}

E - Bomber

爆破対象の位置を (x_i, y_i)\ (i \in \{1,2,\ldots,M\}) とする。 爆弾を (x_b, y_b) にセットしたとき、 x_i = x_b を満たす i の個数を A、 y_i = y_b を満たす i の個数を B、 x_i = x_b かつ y_i = y_b を満たす i の個数 C とすると、爆破される個数は A + B - C で求められる。 ただし、 C の大きさは高々1。

x_b を固定したとき、 y_b としては B - C を最も大きくするものを選ぶのが最適。 各 y_b に対する B - C の値をセグ木で管理しながら x_b を動かして大域解を求める。

計算量は僕の実装だと O(M \log M)。でも係数がかなり大きくて実行時間は 1190 ms だった。

提出したら 3/130... とか表示されてびっくりした。こどふぉか？

提出コード

リンク： https://atcoder.jp/contests/abc176/submissions/16134198

template <class T, class Op>
class SegmentTree {
private:
    const Op op;
    const T id;
    std::vector<T> vec;
    int sz;
 
public:
    explicit SegmentTree(int n, Op op, T id) noexcept
        : op(op), id(id) {
        sz = 1;
        while (sz < n) sz <<= 1;
        vec.assign(sz * 2, id);
    }
    explicit SegmentTree(const std::vector<T>& vec, Op op, T id) noexcept
        : op(op), id(id) {
        int n = vec.size();
        sz = 1;
        while (sz < n) sz <<= 1;
        this->vec.assign(sz * 2, id);
        set_array(vec);
    }
    void set_value(int idx, T val) noexcept {
        vec[idx + sz] = val;
    }
    template <class RandomIt>
    void set_array(RandomIt _begin, RandomIt _end) noexcept {
        std::copy(_begin, _end, vec.begin() + sz);
    }
    void set_array(const std::vector<T>& vec) noexcept {
        set_array(vec.begin(), vec.end());
    }
    void build() noexcept {
        for (int i = sz - 1; i > 0; i--) {
            vec[i] = op(vec[i * 2], vec[i * 2 + 1]);
        }
    }
    void update(int idx, T val) noexcept {
        idx += sz;
        vec[idx] = val;
        for (idx >>= 1; idx > 0; idx >>= 1) {
            vec[idx] = op(vec[idx * 2], vec[idx * 2 + 1]);
        }
    }
    // Query [l, r)
    T query(int l, int r) const noexcept {
        T l_val = id, r_val = id;
        l += sz, r += sz - 1;
        for (; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) l_val = op(l_val, vec[l++]);
            if (!(r & 1)) r_val = op(r_val, vec[r--]);
        }
        return op(l_val, r_val);
    }
    const T& operator[](int idx) const noexcept {
        return vec[idx + sz];
    }
    void reset() noexcept {
        std::fill(vec.begin(), vec.end(), id);
    }
};
 
void solve() {
    ll H, W, M;
    cin >> H >> W >> M;
    map<ll, Vi> xs;
    map<ll, ll> ys;
    for (ll i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        xs[a].emplace_back(b);
        ++ys[b];
    }
 
    ll sz = (ll)ys.size();
    map<ll, ll> pos;
    Vl vals;
    for (auto [a, b] : ys) {
        vals.emplace_back(b);
        pos[a] = (ll)vals.size() - 1;
    }
 
    auto op = [](ll l, ll r) { return max(l, r); };
    SegmentTree seg(sz, op, 0ll);
    for (ll i = 0; i < sz; i++) {
        seg.set_value(i, vals[i]);
    }
    seg.build();
 
    ll ans = 0;
    for (const auto& [a, vec] : xs) {
        ll t = (ll)vec.size();
        for (auto b : vec) {
            ll idx = pos[b];
            ll v = seg[idx];
            seg.update(idx, v - 1);
        }
        chmax(ans, t + seg.query(0, sz));
        for (auto b : vec) {
            ll idx = pos[b];
            ll v = seg[idx];
            seg.update(idx, v + 1);
        }
    }
    prints()(ans);
}

F - Brave CHAIN

9000人中18人しか解けてませんけど（笑）。ABCにAGCの問題を出すのやめてください！！