AtCoder Beginner Contest 188（ABC188） - 接着剤の精進日記

atcoder.jp

冷え
Bondo416さんのAtCoder Beginner Contest 188での成績：2857位
パフォーマンス：892相当
レーティング：1478→1432 (-46) :(#AtCoder #ABC188 https://t.co/Hv9RlsSvQC
— ボンド@競プロ (@bond_cmprog) January 10, 2021

A - Three-Point Shot

$ \min(a, b) + 3 \gt \max(a, b) $かどうかをチェック
提出コード

void solve(){
    int X, Y;
    cin >> X >> Y;
    if(X > Y) swap(X, Y);
    if(X + 3 > Y) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - Orthogonality

問題文の通りに$ A_i \times B_i $の総和を求めてそれが0かどうか調べる
提出コード

void solve(){
    int N;
    cin >> N;
    ll sum = 0;
    vector<int> A(N), B(N);
    REP(i,N) cin >> A[i];
    REP(i,N) cin >> B[i];

    REP(i,N) sum += A[i] * B[i];
    if(sum == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

C - ABC Tournament

$ N $が小さいので愚直にシミュレートをすればいい
シミュレートして最後に負けた人が答え
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> A(1<<N);
    REP(i,1<<N) cin >> A[i];
    vector<int> idx(1<<N);
    iota(idx.begin(), idx.end(), 0);
    int ans = 0;
    while((int)idx.size() > 1){
        vector<int> next;
        for(int i=0;i<(int)idx.size();i+=2){
            if(A[idx[i]] > A[idx[i+1]]){
                ans = idx[i+1];
                next.emplace_back(idx[i]);
            }
            else{
                ans = idx[i];
                next.emplace_back(idx[i+1]);
            }
        }
        idx = next;
    }
    cout << ans + 1 << endl;
}

D - Snuke Prime

imos法で一日あたりのコストを$ imos_i $として求めておけば各日において
$ \min(imos_i, C) $の総和が答えとなる
ただし、値が大きいので座圧する必要がある
イベントソートだと座圧しなくても解くことが出来る
提出コード

void solve(){
    int N;
    ll C;
    cin >> N >> C;
    vector<ll> a(N), b(N), c(N);
    Compress<ll> cmp;
    REP(i,N){
        cin >> a[i] >> b[i] >> c[i];
        cmp.add(a[i]);
        cmp.add(b[i]+1);
    }
    cmp.build();
    int sz = cmp.size();
    vector<ll> imos(sz+1);
    REP(i,N){
        imos[cmp.get(a[i])] += c[i];
        imos[cmp.get(b[i]+1)] -= c[i];
    }
    REP(i,sz) imos[i+1] += imos[i];
    ll ans = 0;
    REP(i,sz-1){
        ans += min(imos[i], C) * (cmp[i+1] - cmp[i]);
    }
    cout << ans << endl;
}

提出コード（イベントソート）

void solve(){
    int N;
    ll C;
    cin >> N >> C;
    vector<ll> a(N), b(N), c(N);
    vector<pair<ll, ll>> event;
    REP(i,N){
        cin >> a[i] >> b[i] >> c[i];
        event.emplace_back(a[i], c[i]);
        event.emplace_back(b[i]+1, -c[i]);
    }
    sort(event.begin(), event.end());
    ll ans = 0, pre = 0, cur_c = 0;
    for(auto [d, cost] : event){
        ans += min(cur_c, C) * (d - pre);
        pre = d;
        cur_c += cost;
    }
    cout << ans << endl;
}

E - Peddler

制約から与えられるグラフはDAGとなる
そのため町$ i $から移動できる町を$ j $とすると
$ dp[j] = \min(dp[j], dp[i], A_i) $として町$ j $に辿り着ける町の中で金の最安値として$ i $の昇順にdpをする
そうすると各町$ i $の$ A_i - dp[i] $の最大値が答え
解説の解法2だとDAGじゃなくても解ける
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];
    vector<vector<int>> g(N);
    REP(i,M){
        int x, y;
        cin >> x >> y;
        g[--x].emplace_back(--y);
    }
 
    vector<ll> dp(N, LINF);
    REP(i,N){
        for(auto nv : g[i]) chmin(dp[nv], min(A[i], dp[i]));
    }
    ll ans = -LINF;
    REP(i,N) chmax(ans, A[i] - dp[i]);
    cout << ans << endl;
}

提出コード（解法2）

void solve(){
    int N, M;
    cin >> N >> M;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];
    vector<vector<int>> g(N);
    REP(i,M){
        int x, y;
        cin >> x >> y;
        g[--x].emplace_back(--y);
    }
    vector<int> idx(N);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int x, int y){
        return A[x] < A[y];
    });
    vector<bool> used(N);
    ll ans = -LINF;
    for(int i : idx){
        if(used[i]) continue;
        queue<int> q;
        q.emplace(i);
        while(!q.empty()){
            int v = q.front(); q.pop();
            for(auto nv : g[v]){
                if(used[nv]) continue;
                chmax(ans, A[nv] - A[i]);
                q.emplace(nv);
                used[nv] = true;
            }
        }
    }
    cout << ans << endl;
}

F - +1-1x2

類題がAGCにあるのでよしなにする
解説（AGCのだけど）はアルメリアさんのものがわかりやすいと思うので割愛（サボり）
atcoder.jp
betrue12.hateblo.jp

提出コード

void solve(){
    ll X, Y;
    cin >> X >> Y;
    ll ans = LINF;
    map<ll, ll> memo;
    priority_queue<LP, vector<LP>, greater<LP>> pq;
    pq.emplace(0, Y);
    while(!pq.empty()){
        auto [v, x] = pq.top(); pq.pop();

        if(v >= ans) continue;
        chmin(ans, v + abs(X-x));

        int r = (x & 1);
        ll nv = v + r + 1;
        int d = 2;
        if(nv < ans && (!memo.count(x / d) || nv < memo[x/d])){
            pq.emplace(nv, x / d);
            memo[x / d] = nv;
        }
        nv = v + (d - r) + 1;
        if(nv < ans && (!memo.count(x / d + 1) || nv < memo[x/d + 1])){
            pq.emplace(nv, x / d + 1);
            memo[x / d + 1] = nv;
        }
    }
    cout << ans << endl;
}