AtCoder Beginner Contest 164 ABC164 参加記

感想

参加しました。Dまで4完で849位でした。Dは既出だったので脳死で解きました。ごめんなさい。自分より後ろのヒストグラムを持つと考えると面白いです。Eはが小さいことに気づき、頂点にさらに所持金を状態としてもちダイクストラすればよさそうというところまでは気付いたのですが、慣れておらず実装できませんでした。拡張ダイクストラはよく出るので、頑張りたいところです。

D - Multiple of 2019

をで割った余りは、とが互いに素であることから、をで割った余りに等しいです。よって、Zero Sum Rangesを思い出せば、解法が思いつきます。

int main() {

    string S;
    cin >> S;
    int N = S.size();
    reverse(all(S));

    //指数の計算 繰り返し二乗法を使ってもよい
    vector<int> modpows(N);
    modpows[0] = 1;
    rep1(i,N)modpows[i] = (10*modpows[i-1])%2019;

    map<int, ll> mp;
    mp[0] = 1;
    ll tmp = 0;
    ll ans = 0;
    rep(i,N){
        tmp += (modpows[i]*(S[i]-'0'))%(2019);
        tmp %= 2019;
        if(i >= 3)ans += mp[tmp];
        mp[tmp]++;
    }
    cout << ans << endl;
}

E - Two Currencies

冒頭でも書きましたが、の制約が他のそれと比べて異常に小さいので、ここに出題の意図がありそうだとわかります。ここから、のお金の状態増やしてグラフ上のダイクストラをすればよさそうだとわかります。俗にいう拡張ダイクストラです。ダイクストラは拡張されておらず、元々存在するグラフの頂点を倍加したりして状態が増えた拡張されたグラフにおけるダイクストラを言います。

お金はだけ持っていれば全ての移動中両替を行わずに移動できるので、それ以上両替するのは無駄であり、それ以上持っているならば、両替を行うという選択肢を取る必要はなくなります。よって、元のグラフの頂点を倍し、それに対応して辺を増やすということをします。これでも頂点数は個、辺数はなので、ダイクストラがであることを思い出せば、十分に高速であることがわかります。

実装

かつっぱさんの実装を参考にしています。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
const ll INFLL = (ll) 1e18 + 1;
struct edge{
    ll to;
    ll a;
    ll b;
};
vector<ll> A,B,C,D;
vector<vector<edge>> edge1,edge2;

vector<ll> dijkstra(ll s){
    priority_queue<l_l, vector<l_l>, greater<l_l>> pq;
    vector<ll> dist(55*3000, INFLL);
    dist[s] = 0;
    pq.push({dist[s], s});
    while(!pq.empty()){
        auto tmp = pq.top();
        pq.pop();
        ll from = tmp.second;
        ll d = tmp.first;
        for(auto p: edge2[from]){
            if(dist[p.to] > dist[from] + p.b){
                dist[p.to] = dist[from] + p.b;
                pq.push(l_l(dist[p.to], p.to));
            }
        }
    }
    return dist;
}
ll f(ll v, ll s){
    return v*3000 + s;
}
int main(){
    ll n, m ,s, u, v;
    cin >> n >> m >> s;
    edge1.resize(n);
    A.resize(m);
    B.resize(m);
    C.resize(n);
    D.resize(n);
    for(ll i = 0;i < m;i++){
        cin >> u >> v >> A[i] >> B[i];
        u--;v--;
        edge1[u].push_back({v,A[i],B[i]});
        edge1[v].push_back({u,A[i],B[i]});
    }
    for (int i = 0; i < n; ++i) {
        cin >> C[i] >> D[i];
    }
    edge2.resize(n*(3000+5));
    for(ll i = 0;i < n;i++){
        for(ll j = 0;j <= 2999;j++){
            ll to = min(j + C[i], 2999ll);
            edge2[f(i,j)].push_back({f(i, to), 0, D[i]});
            for(auto e: edge1[i]){
                if(j - e.a < 0)continue;
                edge2[f(i,j)].push_back({f(e.to, j-e.a), e.a, e.b});
            }
        }
    }
    s = min(s, 2999LL);
    auto dist = dijkstra(f(0,s));
    for(ll i = 1;i < n;i++){
        ll ans = INFLL;
        for(ll j = 0;j < 3000;j++){
            ans = min(ans, dist[f(i, j)]);
        }
        cout << ans << endl;
    }
}