今日の競プロ(2020/4/12) + AtCoder Beginner Contest 162 + Codeforces Round #633 (Div. 1)

AtCoder 5問レーティング：1707→1705 (-2) :(
Codeforces 2問 rating : 1936→1884 (-52) :(
GCJ 1問
行動自粛コンテスト 3問

行動自粛コンテスト A - 登山

マスの上下左右に辺をはってDijkstra。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (int i = 0; i < sz(v); i++) {
        os << v[i];
        if (i < sz(v) - 1) os << " ";
    }
    return os;
}
template <typename T>
vector<T> Dijkstra(int s, vector<vector<pair<int, T>>>& g) {
    priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>>
        que;
    int n = sz(g);
    vector<T> d(n);
    rep(i, n) d[i] = LINF;
    d[s] = 0;
    que.push(make_pair(0LL, s));
    while (!que.empty()) {
        pair<T, int> p = que.top();
        que.pop();
        int v = p.second;
        if (d[v] < p.first) continue;
        for (auto e : g[v]) {
            if (chmin(d[e.first], d[v] + e.second)) {
                que.push(make_pair(d[e.first], e.first));
            }
        }
    }
    return d;
}
int main() {
    int h, w;
    cin >> h >> w;
    int n = h * w;
    vector<ll> v(n);
    rep(i, n) cin >> v[i];
    vector<vector<pair<int, ll>>> g(n);
    rep(i, n) {
        if (i % w != 0) g[i].emplace_back(i - 1, max(0ll, v[i - 1] - v[i]));
        if (i % w != w - 1) g[i].emplace_back(i + 1, max(0ll, v[i + 1] - v[i]));
        if (i - w >= 0) g[i].emplace_back(i - w, max(0ll, v[i - w] - v[i]));
        if (i + w < n) g[i].emplace_back(i + w, max(0ll, v[i + w] - v[i]));
    }
    cout << Dijkstra(0, g)[n - 1] << endl;
}

行動自粛コンテスト B - 置き換え

問題

解説AC。
「 $dp[i][j]=i$ 回目の操作まで行い、末尾の要素が $j$ となるような場合の数」をする。これだと間に合わないように見えるが、 $j$ として考えるのは $A_1\times A_2 \times \ldots \times A_n \leq 10^6$ の約数だけでいいので、実は間に合う。

提出

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 998244353;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (int i = 0; i < sz(v); i++) {
        os << v[i];
        if (i < sz(v) - 1) os << " ";
    }
    return os;
}
struct modint {
    ll x;
    modint(ll x = 0) : x((x % MOD + MOD) % MOD) {
    }
    ll value() const {
        return x;
    }
    modint operator-() const {
        return modint(-x);
    }
    modint& operator+=(const modint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    modint& operator-=(const modint a) {
        if ((x += MOD - a.x) >= MOD) x -= MOD;
        return *this;
    }
    modint& operator*=(const modint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    modint operator+(const modint a) const {
        modint res(*this);
        return res += a;
    }
    modint operator-(const modint a) const {
        modint res(*this);
        return res -= a;
    }
    modint operator*(const modint a) const {
        modint res(*this);
        return res *= a;
    }
    modint pow(ll t) const {
        if (t == 0) return 1;
        modint a = pow(t >> 1);
        a *= a;
        if (t % 2 == 1) a *= *this;
        return a;
    }
    modint inv() const {
        return pow(MOD - 2);
    }
    modint& operator/=(const modint a) {
        return (*this) *= a.inv();
    }
    modint operator/(const modint a) const {
        modint res(*this);
        return res /= a;
    }
};
ostream& operator<<(ostream& os, const modint& x) {
    os << x.value();
    return os;
}
int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    ll p = 1;
    rep(i, n) cin >> a[i], p *= a[i];
    vector<ll> v;
    for (ll d = 1; d <= p; d++) {
        if (p % d == 0) {
            v.push_back(d);
        }
    }

    vector<map<ll, modint>> dp(n + 10);
    dp[0][a[0]] = 1;
    modint ans = 0;
    rep(i, n - 1) {
        for (ll j : v) {
            for (ll k : v) {
                if (j * a[i + 1] % k) continue;
                dp[i + 1][k] += dp[i][j];
            }
        }
    }
    for (ll j : v) ans += dp[n - 1][j];
    cout << ans << endl;
}

行動自粛コンテスト C - バス

問題

Dijkstra + 二分探索やる。 $K \leq 10^{15}$ をなぜか int で受け取っててなかなか合わなかった…。

提出

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 998244353;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (int i = 0; i < sz(v); i++) {
        os << v[i];
        if (i < sz(v) - 1) os << " ";
    }
    return os;
}
template <typename T>
vector<T> Dijkstra(int s, vector<vector<pair<int, T>>>& g) {
    priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>>
        que;
    int n = sz(g);
    vector<T> d(n);
    rep(i, n) d[i] = LINF;
    d[s] = 0;
    que.push(make_pair(0LL, s));
    while (!que.empty()) {
        pair<T, int> p = que.top();
        que.pop();
        int v = p.second;
        if (d[v] < p.first) continue;
        for (auto e : g[v]) {
            if (chmin(d[e.first], d[v] + e.second)) {
                que.push(make_pair(d[e.first], e.first));
            }
        }
    }
    return d;
}
int main() {
    int n, m;
    ll k;
    cin >> n >> m >> k;
    vector<int> a(m), b(m);
    vector<ll> c(m), d(m);
    rep(i, m) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--;
        b[i]--;
    }
    ll ok = LINF, ng = 0, mid;
    while (ok - ng > 1) {
        mid = (ok + ng) / 2;
        vector<vector<pair<int, ll>>> g(n);
        rep(i, m) {
            if (d[i] <= mid) {
                g[a[i]].emplace_back(b[i], c[i]);
                g[b[i]].emplace_back(a[i], c[i]);
            }
        }
        (Dijkstra(0, g)[n - 1] <= k ? ok : ng) = mid;
    }
    cout << (ok == LINF ? -1 : ok) << endl;
}

Google Code Jam 2020 Round 1A C - Square Dance

問題

昨日からずっとこれやってた。ACできてめちゃめちゃ嬉しい。

次のラウンドで確認するのは前のラウンドで compass neighbor がいなくなった人だけ
各人の compass neighbor が誰かが一瞬でわかるようにしておく

がポイント。

提出

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (int i = 0; i < sz(v); i++) {
        os << v[i];
        if (i < sz(v) - 1) os << " ";
    }
    return os;
}

int h, w;
int id(int i, int j) {
    return i * w + j;
}
int main() {
    int t;
    cin >> t;
    vector<set<int>> lr, ud;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << ": ";
        cin >> h >> w;
        int n = h * w;
        vector<ll> v(n);
        ll tot = 0;
        rep(i, n) cin >> v[i], tot += v[i];
        lr.clear();
        ud.clear();
        lr.resize(h);
        ud.resize(w);
        rep(i, h) rep(j, w) {
            lr[i].insert(id(i, j));
            ud[j].insert(id(i, j));
        }
        rep(i, h) {
            lr[i].insert(-1);
            lr[i].insert(INF);
        }
        rep(j, w) {
            ud[j].insert(-1);
            ud[j].insert(INF);
        }

        set<int> q, tmp;
        vector<int> el;
        rep(i, n) q.insert(i);
        ll ans = tot;
        while (1) {
            el.clear();
            tmp.clear();
            for (int id : q) {
                int i = id / w, j = id % w;
                ll sum = 0;
                auto itr1 = lr[i].upper_bound(id);
                auto itr2 = lr[i].lower_bound(id);
                auto itr3 = ud[j].upper_bound(id);
                auto itr4 = ud[j].lower_bound(id);
                if (*itr1 != INF) sum += v[id] - v[*itr1];
                if (*(--itr2) != -1) sum += v[id] - v[*itr2];
                if (*itr3 != INF) sum += v[id] - v[*itr3];
                if (*(--itr4) != -1) sum += v[id] - v[*itr4];
                // cout << v[id] << " " << sum << endl;
                if (sum < 0) {
                    if (*itr1 != INF) tmp.insert(*itr1);
                    if (*itr2 != -1) tmp.insert(*itr2);
                    if (*itr3 != INF) tmp.insert(*itr3);
                    if (*itr4 != -1) tmp.insert(*itr4);
                    el.push_back(id);
                    tot -= v[id];
                }
            }
            for (int id : el) {
                int i = id / w, j = id % w;
                lr[i].erase(id);
                ud[j].erase(id);
                tmp.erase(id);
            }
            q = tmp;
            if (q.empty()) break;
            ans += tot;
        }
        cout << ans << endl;
    }
}

std::gcd 便利〜

提出

ABC162 D - RGB Triplets

問題

$S_i \neq S_j$ かつ $S_i \neq S_k$ かつ $S_j \neq S_k$

$(S_i,S_j,S_k)=$ ('R', 'G', 'B'), ('R', 'B', 'G'), ('G', 'R', 'B'), ('G', 'B', 'R'), ('B', 'R', 'G'), ('B', 'G', 'R') ということなのでこれらを全部数えた。どう考えても ('R'の個数) × ('G'の個数) × ('B'の個数) でよかった……。

$j-i \neq k-j$

$j-i = k-j$ の方が数えやすいので、そっちを数えてあとで引く。

提出

ABC162 E - Sum of gcd of Tuples (Hard)

問題

はい来たいつものやつ！！「gcd が $G$ になるような数列は何通りあるか？」を $1 \leq G \leq K$ について考えるやつ。
gcd が $G$ になるためには、数列の全要素が $G$ の倍数であることが必要。一方、全要素が $2G$ の倍数だと gcd は $G$ ではなく $2G$ になってしまうし、 $3G,4G,\ldots$ の場合も同様。つまり、「 $f(G)=$ gcd がGとなるような数列の数」とすると、 $f(G)=(\frac{K}{G})^N-f(2G)-f(3G)-\ldots$ 。これを上から順番に計算して、足す。
F解けなかったので明日やります