今日の競プロ(2020/10/26) - gyouzasushi’s diary

久しぶりに書く。寝れへん

AOJ-2883 知識の証明(350点)

リンク
問題概要：4 桁のパスワード "0000" から "9999" それぞれに対し、以下のBNFで定義されるハッシュ関数<Hash>から得られるハッシュ値を計算せよ。但し、 'a', 'b', 'c', 'd' はそれぞれ 4 桁のパスワードの先頭から 1 桁目，2 桁目，3 桁目，4 桁目の数字を表し、演算子 '+', '*', '^' はそれぞれ bitwise or, bitwise and, bitwise xor を表す。

<Hash> ::= <Letter> | '['<Op> <Hash> <Hash>']' 
<Op> ::= '+' | '*' | '^' 
<Letter> ::= 'a' | 'b' | 'c' | 'd'

構文解析　ずっとどうしていいかわからんくて怪しい再帰でなんとかしてたけど、これ構文解析 Howto · GitHub読んでからだいぶわかってきた。ありがとうございます。この問題は考えること少なめで優しいね。

コードを表示

#include <bits/stdc++.h>
using namespace std;
using state = string::const_iterator;
int Letter(state &begin) {
    int ret = *begin - '0';
    begin++;
    return ret;
}
int Hash(state &begin) {
    if (*begin == '[') {
        begin++;
        char op = *begin;
        begin++;
        int lhs = Hash(begin);
        int rhs = Hash(begin);
        begin++;
        if (op == '+') {
            return lhs | rhs;
        }
        if (op == '*') {
            return lhs & rhs;
        }
        if (op == '^') {
            return lhs ^ rhs;
        }
    }
    return Letter(begin);
}
int main() {
    while (1) {
        string s;
        int p;
        cin >> s;
        if (s == ".") break;
        cin >> p;
        vector<int> cnt(16);
        int ans = 0;
        for (int i = 0; i <= 9999; i++) {
            string t = to_string(i);
            while (t.size() < 4) t = "0" + t;
            string ss = s;
            for (char &c : ss) {
                if (c == 'a') c = t[0];
                if (c == 'b') c = t[1];
                if (c == 'c') c = t[2];
                if (c == 'd') c = t[3];
            }
            state begin = ss.begin();
            int hs = Hash(begin);
            if (i == p) ans = hs;
            cnt[hs]++;
        }
        cout << ans << ' ' << cnt[ans] << '\n';
    }
}

AOJ-2608 Minus One(350点)

リンク
問題概要： $N$ 頂点 $M$ 辺の無向グラフ $G$ とふたつの頂点 $s,t$ が与えられる。 $G$ の異なる頂点 $(u,v)$ の組であって、 $G$ に辺 $(u,v)$ を追加したグラフにおける $s$ から $t$ への最短経路長が、 $G$ における $s$ から $t$ への最短経路長よりもちょうど $1$ 短くなるようなものはいくつか？

制約： $N \leq 10^5,M \leq 3\times 10^5$

$G$ における頂点 $i$ から頂点 $j$ への最短経路長を $dist_{i,j}$ と表すことにする。このとき、求めるべきは $dist_{s,u}+1+dist_{v,t}=dist_{s,t}$ を満たすような $(u,v)$ の組の総数で、これは $dist_{s,i}, dist_{t,i}$ のヒストグラムを作っておけば高速に求まる。

コードを表示

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    s--, t--;
    vector<vector<int>> g(n);
    while (m--) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    auto d = [&](int s) {
        vector<int> ret(n, -1);
        queue<int> q;
        ret[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int pos = q.front();
            q.pop();
            for (int nxt : g[pos]) {
                if (~ret[nxt]) continue;
                ret[nxt] = ret[pos] + 1;
                q.push(nxt);
            }
        }
        return ret;
    };
    using ll = long long;
    auto ds = d(s);
    auto dt = d(t);
    vector<ll> cnts(n), cntt(n);
    for (int i = 0; i < n; i++) {
        if (~ds[i]) cnts[ds[i]]++;
        if (~dt[i]) cntt[dt[i]]++;
    }
    ll ans = 0;
    int SUM = ds[t] - 2;
    for (int i = 0; i < n; i++) {
        if (SUM - i >= 0) ans += cnts[i] * cntt[SUM - i];
    }
    cout << ans << '\n';
}

AOJ-2426 宝探し(350点)

リンク
問題概要： $n$ 個のお宝があり、 $i$ 個目のお宝は座標 $(x_i,y_i)$ に埋まっている。「長方形領域 $x_1 \leq x \leq x_2, y_1\leq y \leq y2$ に埋まっているお宝は全部でいくつか？」という形式のクエリ $m$ 個を処理せよ。

制約： $n \leq 5000,m \leq 5\times 10^5,|x|\leq10^9,|y|\leq10^9$

座標圧縮＋二次元累積和。かなりやりたくなかったけど、この程度で音をあげとったらICPCは戦えへんのやろなあ、と思ってがんばったよ。

コードを表示

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> p(n);
    vector<int> xs(n), ys(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        xs[i] = x;
        ys[i] = y;
        p[i] = make_pair(x, y);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());

    vector<vector<int>> v(n + 2, vector<int>(n + 2));
    for (auto &[x, y] : p) {
        x = lower_bound(xs.begin(), xs.end(), x) - xs.begin() + 1;
        y = lower_bound(ys.begin(), ys.end(), y) - ys.begin() + 1;
        v[y][x]++;
    }

    for (int i = 0; i < n + 1; i++) {
        for (int j = 0; j < n + 1; j++) {
            v[i + 1][j + 1] += v[i + 1][j] + v[i][j + 1] - v[i][j];
        }
    }

    for (int i = 0; i < m; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        x1 = lower_bound(xs.begin(), xs.end(), x1) - xs.begin();
        y1 = lower_bound(ys.begin(), ys.end(), y1) - ys.begin();
        x2 = upper_bound(xs.begin(), xs.end(), x2) - xs.begin();
        y2 = upper_bound(ys.begin(), ys.end(), y2) - ys.begin();
        cout << v[y2][x2] - v[y2][x1] - v[y1][x2] + v[y1][x1] << '\n';
    }
}

AOJ-2613 Unordered Operators(350点)

リンク
問題概要：以下のBNFで示される形式の数式が与えられる。演算子 '+', '-', '*' の優先順位を適切に定めたときの、数式の計算結果の最大値を求めよ。

<expr> ::= ( <expr> ) | <number> | <expr> <op> <expr>
<op> ::= + | - | *
<number> は非負整数を表す。

優先順位を全部試す。括弧付きの四則演算のときとほぼ一緒で、演算子のとこだけちょっと抽象化すればいける。

コードを表示

#include <bits/stdc++.h>
using namespace std;
using state = string::const_iterator;
using ll = long long;
const ll LINF = (((1ll << 62) - 1) << 1) + 1;
string ops1, ops2, ops3;
ll expr(state &begin);
ll number(state &begin) {
    ll ret = 0;
    while (isdigit(*begin)) {
        ret *= 10;
        ret += *begin - '0';
        begin++;
    }
    return ret;
}
ll factor(state &begin) {
    if (*begin == '(') {
        begin++;
        ll ret = expr(begin);
        begin++;
        return ret;
    }
    return number(begin);
}
ll term1(state &begin) {
    ll ret = factor(begin);
    while (1) {
        if (!count(ops1.begin(), ops1.end(), *begin)) break;
        if (*begin == '*') {
            begin++;
            ret *= factor(begin);
        } else if (*begin == '+') {
            begin++;
            ret += factor(begin);
        } else if (*begin == '-') {
            begin++;
            ret -= factor(begin);
        }
    }
    return ret;
}
ll term2(state &begin) {
    ll ret = term1(begin);
    while (1) {
        if (!count(ops2.begin(), ops2.end(), *begin)) break;
        if (*begin == '*') {
            begin++;
            ret *= term1(begin);
        } else if (*begin == '+') {
            begin++;
            ret += term1(begin);
        } else if (*begin == '-') {
            begin++;
            ret -= term1(begin);
        }
    }
    return ret;
}
ll expr(state &begin) {
    ll ret = term2(begin);
    while (1) {
        if (!count(ops3.begin(), ops3.end(), *begin)) break;
        if (*begin == '*') {
            begin++;
            ret *= term2(begin);
        } else if (*begin == '+') {
            begin++;
            ret += term2(begin);
        } else if (*begin == '-') {
            begin++;
            ret -= term2(begin);
        }
    }
    return ret;
}
int main() {
    string s;
    cin >> s;
    ll ans = -LINF;
    string ops = "+-*";
    sort(ops.begin(), ops.end());
    do {
        for (int l = 0; l <= 3; l++) {
            for (int m = 0; l + m <= 3; m++) {
                int r = 3 - l - m;
                ops1 = ops.substr(0, l);
                ops2 = ops.substr(l, m);
                ops3 = ops.substr(l + m, r);
                state begin = s.begin();
                ans = max(ans, expr(begin));
            }
        }
    } while (next_permutation(ops.begin(), ops.end()));
    cout << ans << '\n';
}

AOJ-2601 Evacuation Route(350点)

リンク
問題概要： $W$ 個のユニットに分けられた通路がある。ユニットには、以下の三種類が存在する。

入り口：時刻 $t=0,1,\ldots,a_i-1$ のそれぞれにおいてちょうど一人の人が現れる。時刻 $t$ にユニット $i$ にいる人は、時刻 $t+1$ にはユニット $i-1,i,i+1$ のいずれかに移動できる。時刻 $t$ に現れた人は、時刻 $t+1$ 以降から移動を開始する。

出口：出口。

防火扉：時刻 $|a_i|$ 以降、遮断されてしまう。

出口にたどり着くことができる人は最大で何人か？
制約： $W\leq 10^5,|a_i| \leq 10^4$

人々が目指すのは、左右どちらか一方の最寄りの出口であると考えてよい。よって、各入り口について「左側の最寄り出口にたどり着くことができるのは最大何人か？」「右側の最寄り出口にたどり着くことができるのは最大何人か？」をそれぞれ計算できれば解けて、これは index をガチャガチャやってると RangeMinimumQuery で処理できることがわかる。セグ木。

ACLのやつを写経してみたけど意外としんどくなかった。本番も　迷うくらいなら書いちゃえ！w　ぐらいでいいんかもね。

コードを表示

#include <bits/stdc++.h>
using namespace std;
const int INF = 1'000'000'000;
template <class S, S (*op)(S, S), S (*e)()>
struct SegmentTree {
public:
    SegmentTree(const vector<S>& v) : _n(int(v.size())) {
        log = ceil_pow2(_n);
        size = 1 << log;
        d = vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }
    void set(int p, S x) {
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    S get(int p) {
        return d[p + size];
    }
    S prod(int l, int r) {
        S sml = e(), smr = e();
        l += size;
        r += size;
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

private:
    int _n, size, log;
    vector<S> d;
    int ceil_pow2(int n) {
        int x = 0;
        while ((1U << x) < (unsigned int)(n)) x++;
        return x;
    }
    void update(int k) {
        d[k] = op(d[2 * k], d[2 * k + 1]);
    }
};
using S = int;
S op(S a, S b) {
    return min(a, b);
}
S e() {
    return INF;
}
int main() {
    int w;
    cin >> w;
    vector<int> a(w), ex = {-INF, INF};
    for (int i = 0; i < w; i++) {
        cin >> a[i];
        if (a[i] == 0) ex.push_back(i);
    }
    sort(ex.begin(), ex.end());

    vector<int> ans(w, 0);
    {
        vector<int> seg(w, INF);
        for (int i = 0; i < w; i++) {
            if (a[i] < 0) seg[i] = -a[i] - i;
        }
        SegmentTree<S, op, e> segt(seg);
        for (int i = 0; i < w; i++) {
            if (a[i] <= 0) continue;
            int r = *lower_bound(ex.begin(), ex.end(), i);
            if (r == INF) continue;
            int MIN = segt.prod(i, r) + i;
            ans[i] = max(ans[i], min(a[i], MIN));
        }
    }
    {
        vector<int> seg(w, INF);
        for (int i = 0; i < w; i++) {
            if (a[i] < 0) seg[i] = -a[i] - (w - 1 - i);
        }
        SegmentTree<S, op, e> segt(seg);
        for (int i = 0; i < w; i++) {
            if (a[i] <= 0) continue;
            int l = *(--lower_bound(ex.begin(), ex.end(), i)) + 1;
            if (l < 0) continue;
            int MIN = segt.prod(l, i) + (w - 1 - i);
            ans[i] = max(ans[i], min(a[i], MIN));
        }
    }
    cout << accumulate(ans.begin(), ans.end(), 0) << '\n';
}

AOJ-1132 Circle and Points(450点)

リンク
問題概要：座標平面上に $N$ 個の点がある。半径 $1$ の円を自由に動かすとき、円の周または内部にある点の個数の最大値を求めよ。
制約： $N\leq 300$

円が二つの点を含むとき、その点が周上にくるように円を動かしても損しない。こうすると注目している二点に対して円の候補が二つ（こっち側かあっち側か）に絞られるので、あとはその二点の選び方を全探索すればOK（そのような二点が選べない場合は $1$ が答え）。

コードを表示

#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
const double EPS = 1e-9;
int sgn(double a) {
    return (a < -EPS) ? -1 : (a > EPS) ? 1 : 0;
};
struct Point {
    double x, y;
    Point(double _x, double _y) : x(_x), y(_y) {
    }
    Point operator+(const Point &rhs) {
        Point res(*this);
        return res += rhs;
    }
    Point operator-(const Point &rhs) {
        Point res(*this);
        return res -= rhs;
    }
    Point operator*(const double &rhs) {
        Point res(*this);
        return res *= rhs;
    }
    Point operator/(const double &rhs) {
        Point res(*this);
        return res /= rhs;
    }
    inline bool operator<(const Point &b) {
        if (sgn(x - b.x)) return sgn(x - b.x) < 0;
        return sgn(y - b.y) < 0;
    }
    Point operator+=(const Point &rhs) {
        x += rhs.x, y += rhs.y;
        return *this;
    }
    Point operator-=(const Point &rhs) {
        x -= rhs.x, y -= rhs.y;
        return *this;
    }
    Point operator*=(const double &rhs) {
        x *= rhs, y *= rhs;
        return *this;
    }
    Point operator/=(const double &rhs) {
        x /= rhs, y /= rhs;
        return *this;
    }
    Point rotate(const double &theta) {
        double px = x, py = y;
        x = px * cos(theta) - py * sin(theta);
        y = px * sin(theta) + py * cos(theta);
        return *this;
    }
    double abs() {
        return sqrt(x * x + y * y);
    }
    double dot(const Point &rhs) {
        return x * rhs.x + y * rhs.y;
    }
    double det(const Point &rhs) {
        return x * rhs.y - y * rhs.x;
    }
    double arg() {
        return atan2(y, x);
    }
};
inline bool operator<(const Point &a, const Point &b) {
    if (sgn(a.x - b.x)) return sgn(a.x - b.x) < 0;
    return sgn(a.y - b.y) < 0;
}
ostream &operator<<(ostream &os, Point &p) {
    return os << fixed << setprecision(10) << p.x << ' ' << p.y;
}
int main() {
    while (1) {
        int n;
        cin >> n;
        if (n == 0) break;
        vector<Point> p;
        for (int i = 0; i < n; i++) {
            double x, y;
            cin >> x >> y;
            p.emplace_back(x, y);
        }
        int ans = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                Point c = (p[i] + p[j]) / 2;
                Point v = p[i] - p[j];
                if (sgn(v.abs() - 2) > 0) continue;
                Point w = Point(-(v.y), v.x);
                w *= sqrt(1.0 - (v / 2).abs() * (v / 2).abs()) / w.abs();
                for (Point o : {c + w, c - w}) {
                    int cnt = 0;
                    for (int k = 0; k < n; k++) {
                        if (sgn((p[k] - o).abs() - 1) <= 0) cnt++;
                    }
                    ans = max(ans, cnt);
                }
            }
        }
        cout << ans << '\n';
    }
}

AOJ-1140 Cleaning Robot(450点)

リンク
問題概要： $h\times w$ のタイルがある。それぞれのタイルはきれいか、汚れているか、障害物が置かれているである。お掃除ロボットは初期位置を出発し、汚れているタイルを全て掃除してまわりたい。このとき、ロボットの最小移動回数を求めよ。
制約： $w,h\leq 20,$ 汚れているタイルは $10$ 個以下

初期位置と汚れているタイルの全点対最短経路長を求めておいて、bitDP。

コードを表示

#include <bits/stdc++.h>
#define rep(i, x) for (int i = 0; i < (int)(x); i++)
using namespace std;
const int INF = 1'000'000'000;
const vector<int> dx = {0, 1, 0, -1};
const vector<int> dy = {1, 0, -1, 0};
int main() {
    while (1) {
        int w, h;
        cin >> w >> h;
        if (w == 0) return 0;
        vector<string> v(h, string(w, '.'));
        vector<int> ys, xs;
        rep(i, h) rep(j, w) {
            cin >> v[i][j];
            if (v[i][j] == 'o') {
                ys.push_back(i);
                xs.push_back(j);
            }
        }
        rep(i, h) rep(j, w) {
            if (v[i][j] == '*') {
                ys.push_back(i);
                xs.push_back(j);
            }
        }
        int n = int(xs.size());
        vector<vector<int>> d(n, vector<int>(n));
        bool ok = 1;
        rep(i, n) {
            vector<vector<int>> dd(h, vector<int>(w, INF));
            queue<pair<int, int>> q;
            dd[ys[i]][xs[i]] = 0;
            q.emplace(ys[i], xs[i]);
            while (!q.empty()) {
                auto [y, x] = q.front();
                q.pop();
                rep(j, 4) {
                    int ny = y + dy[j], nx = x + dx[j];
                    if (!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue;
                    if (dd[ny][nx] != INF) continue;
                    if (v[ny][nx] == 'x') continue;
                    dd[ny][nx] = dd[y][x] + 1;
                    q.emplace(ny, nx);
                }
            }
            rep(j, n) {
                d[i][j] = dd[ys[j]][xs[j]];
            }
        }

        vector<vector<int>> dp(1 << n, vector<int>(n, INF));
        dp[1][0] = 0;
        rep(bit, 1 << n) {
            rep(pos, n) if (bit >> pos & 1) {
                rep(nxt, n) if (~bit >> nxt & 1) {
                    int nbit = bit | (1 << nxt);
                    dp[nbit][nxt] =
                        min(dp[nbit][nxt], dp[bit][pos] + d[pos][nxt]);
                }
            }
        }
        int ans =
            *min_element(dp[(1 << n) - 1].begin(), dp[(1 << n) - 1].end());
        cout << (ans == INF ? -1 : ans) << '\n';
    }
}

完