ABC 256 参加記

2022.06.19

競技プログラミング

34分5完で465位、パフォーマンスは1893でした。Fの解法を思いついて60分時点でコーディングできたのですが、結局TLEが消えずに通せませんでした… 理由はmintの除算に$\log$がつくことを忘れていたからでした。終了後に直したらACして悲しくなりました…

区間等差数列加算区間和取得セグ木はなんで動くのかとかを理解したらブログにまとめたいです。

A 2^N

問題

$N$が与えられます。$2^N$を出力してね。

$0 \leq N \leq 30$

提出コード

int main(){

    int N; cin >> N;
    ll ans = 1;
    rep(i, N){
        ans *= 2;
    }

    cout << ans << endl;
}

B Batters

問題

マス$0,1,2,3$の$4$つのマスがあり、始めますの上には何もありません。また、整数$P = 0$です。

正の整数からなる数列$A = (A_1, A_2, \cdots, A_N)$が与えられるので、$i = 1, 2,\cdots, N $の順に次の操作を行います。

マス$0$に駒を1つおく。

マス上のすべての駒を番号が$A_i$大きいマスに進める。移動先のマスが存在しない場合、それらを取り除いて$P$に取り除いた個数を加算する。

すべての操作を行った後の$P$を出力してね

$1 \leq N \leq 100$

$1 \leq A_i \leq 4$

提出コード

int main(){

    int N; cin >> N;
    vector<ll> A(N); for(int i = 0; i < N; i++) cin >> A[i];
    
    vi now(4, 0);
    now[0] = 1;
    int P = 0;
    for(auto a: A){

        now[0] = 1;
        vi nex(4, 0);

        rep(i, 4) if(now[i] == 1){
            if(i + a < 4) nex[i+a] = 1;
            else P++;
        }

        swap(now, nex);
    }

    cout << P << endl;
    
}

C Filling 3x3 array

問題

6つの整数$h_1, h_2, h_3, w_1, w_2, w_3$が与えられます。縦横$3\times 3$のマス目に、以下の条件をすべて満たすように各マスに正の整数を1つずつ書き込むことを考えます。

$i = 1, 2, 3$について、上から$i$行目に書き込んだ数の和が$h_i$となる。

$j = 1, 2, 3$について、左から$j$列目に書き込んだ数の和が$w_j$となる。

条件を満たす書き込み方は全部で何通り存在しますか？

$3 \leq h_i, w_j \leq 30~(i = 1, 2, 3, j = 1, 2, 3)$

考察

制約より、各マスには1以上30以下の数しか入りません。よって$(1, 1), (1, 2), (2, 1), (2,2)$にすべての組み合わせを入れてみて、いい感じにできるなら数えていくみたいなことをするとよいです。4つ決めるところは一直線になっていなければどこでもよいです。

提出コード

int main(){

    vi H(3), W(3);
    rep(i, 3) cin >> H[i];
    rep(i, 3) cin >> W[i];
    
    ll ans = 0;
    rrep(i, 30){
        rrep(j, 30){
            rrep(k, 30){
                rrep(l, 30){

                    vvi G(3, vi(3));
                    G[0][0] = i;
                    G[0][1] = j;
                    G[1][0] = k;
                    G[1][1] = l;

                    rep(u, 2){
                        G[2][u] = H[u] - G[0][u] - G[1][u];
                    }

                    rep(v, 3){
                        G[v][2] = W[v] - G[v][0] - G[v][1];
                    }
                    
                    if(H[2] != G[0][2] + G[1][2] + G[2][2]) continue;

                    int add = 1;
                    rep(x, 3) rep(y, 3) if(G[x][y] <= 0) add = 0;

                    ans += add;

                }
            }
        }
    }

    cout << ans << endl;
}

D Union of Interval

問題

$N$個の右半開区間$[L_i, R_i)$が与えられます。これらの和集合を$S$とします。$S$を最小の右半開区間の和集合で表してね

$1 \leq N \leq 2 \times 10^5$

$1 \leq L_i < R_i \leq 2 \times 10^5$

考察

$1 \leq L_i < R_i \leq 2 \times 10^5$ より、imos法が使えます。使うとよいです。

提出コード

int main(){

    int N; cin >> N;

    vll G(300000, 0);

    rep(i, N){
        ll x, y; cin >> x >> y;
        G[x] += 1;
        G[y] -= 1;
    }

    rep(i, 300000 - 1){
        G[i+1] += G[i];
    }

    bool in = false;
    vpll Ans;

    rep(i, 300000){
        if(in){
            if(G[i] > 0){
                Ans.back().se = i + 1;
            }else{
                in = false;
            }
        }else{
            if(G[i] > 0){
                Ans.pb({i, i + 1});
                in = true;
            }
        }
    }

    for(auto [f, s]: Ans) cout << f << " " << s << "\n";

}

E Takahashi’s Anguish

問題

$1$から$N$の番号がついた$N$人の人がいます。$1$から$N$までの整数を並び替えた列$P = (P_1, P_2, \cdots, P_N)$を$1$つ選び、人$P_1$,人$P_2$,$\cdots$人$P_N$の順番に$1$人ずつキャンディを配ることにしました。人$i$は人$X_i$のことが嫌いなので、高橋君が人$i$より先に人$X_i$にキャンディを配った場合、人$i$に不満度$C_i$がたまります。そうでない場合の人$i$の不満度は$0$です。高橋君が$P$を自由に選べるとき、全員の不満度の和の最小はいくつになりますか？

$2 \leq N \leq 2 \times 10^5$

$1 \leq X_i \leq N$

$X_i \neq i$

$1 \leq C_i \leq 10^9$

考察

いま人$i$にキャンディをあげたとき、全体で発生する不満度の合計を$A_i$とします。$A$の最小の人にキャンディをあげ、$A_{X_i}$を更新することを繰り返せばよいです。$A$の最小の人を求めるのにはセグメント木を用いるとよいです。(もしかしたら嘘解法かもしれません…?)

提出コード

#include <atcoder/all>
using namespace atcoder;

using S = pair<ll, ll>; // 発生する不満度, idx
S op(S a, S b){ 
    if(a.fi <= b.fi) return a;
    else return b;
}
S e(){ return {INF, 0}; }

int main(){

    int N; cin >> N;

    vll X(N+1); rrep(i, N) cin >> X[i];
    vll C(N+1); rrep(i, N) cin >> C[i];

    vector<S> v(N+10, {INF, 0});

    rrep(i, N) v[i] = {0, i};

    rrep(i, N){
        v[X[i]].fi += C[i];
    }

    segtree<S, op, e> seg(v);

    ll ans = 0;

    while(true){

        S mi = seg.all_prod();
        if(mi.fi == INF) break;
        seg.set(mi.se, {INF, mi.se});

        ans += mi.fi;
        S ch = seg.get(X[mi.se]);
        if(ch.fi != INF) ch.fi -= C[mi.se];
        seg.set(X[mi.se], ch);

    }

    cout << ans << endl;


}