ABC 252 参加記

2022.05.23

競技プログラミング

65分6完(1ペナ)で401位、パフォーマンスは1904でした。青パフォが出せてうれしい～～～

A ASCII code

問題

整数$N$が与えられます。ASCII 文字コードが$N$であるような英小文字を出力してください。

提出コード

int main(){
    int N; cin >> N; 
    cout << char(N) << endl;
}

B Takahashi’s Failure

問題

高橋君の家には$N$個の食品があり、$i$番目の食品のおいしさは$A_i$です。また、高橋君には嫌いな食品が$K$個あり、具体的には$i=1,2,\cdots, K$について、$B_i$番めの食品が嫌いです。

高橋君は$N$個の食品のうち、おいしさが最大の食品から$1$つを選んで食べようと考えています。高橋君が嫌いな食品を食べる可能性があるならばYes、ないならばNoを出力してください。

$1 \leq K \leq N \leq 100$

$1 \leq A_i \leq 100$

$1 \leq B_i \leq N$

提出コード

int main(){

    ll N, K; cin >> N >> K;
    vector<ll> A(N); for(int i = 0; i < N; i++) cin >> A[i];
    vector<ll> B(K); for(int i = 0; i < K; i++) cin >> B[i];
    bool ans = false;
    ll ma = vmax(A);
    for(auto b: B) if(ma == A[b-1]) ans = true;
    YesNo(ans);

}

C Slot Strategy

問題

$N$個のリールからなるスロットがあり、$i$番目のリールの配列は文字列$S_i$によってあらわされます。($S_i$は0,1,$\cdots$,9がちょうど$1$回ずつ現れる長さ$10$の文字列)

それぞれのリールには対応するボタンがついており、高橋君は各非負整数$t$について、スロットが回り始めてからちょうど$t$秒後にボタンを$1$つ選んで押す(または何もしない)ことができます。

スロットが回り始めてから$t$秒後に$i$番目のリールに対応するボタンを押すと、$i$番目のリールは$S_i$の$(t \mod 10)+1$文字目を表示して泊まります。

高橋君はすべてのリールを止めたうえで、表示されている文字がすべて同じであるようにしたいです。高橋君が目標を達成できるようにすべてのリールを止めるまでに、スロットが回り始めてから最小で何秒かかるか求めてください。

$2 \leq N \leq 100$

考察

スロットを0,1,$\cdots$, 9 にそろえるときの最小の時間をそれぞれ考えればよいです。

提出コード

int main(){

    int N; cin >> N;
    vector<string> S(N); for(int i = 0; i < N; i++) cin >> S[i];
    
    string num = "0123456789";
    ll ans = INF;
    for(char n: num){
        vll cnt(10, -1);
        for(auto s: S){
            rep(i, 10) if(s[i] == n) cnt[i]++;
        }

        ll t = 0;
        rep(i, 10) if(cnt[i] != -1){
            chmax(t, 10 * cnt[i] + i);
        }
        chmin(ans, t);
    }
    cout << ans << endl;
    
}

D Distinct Trio

問題

長さ$N$の数列$A = (A_1, A_2, \cdots, A_N)$が与えられます。以下の2条件をともに満たすような整数の組$(i, j, k)$の個数を求めてください。

$1 \leq i < j < k \leq N$

$A_i, A_j, A_k$は相異なる

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

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

考察

余事象で考えました。すべての$A$が異なっていた場合、答えは${}_NC_3$です。ここから重複するものを引いていきます。

ある値$x$が数列$A$中に$cn$個現れたとします。すると、

2個$x$でもう一つがそれ以外である、すなわち${}_{cn}C_2 \times (N - cn)$ 個
3個$x$、すなわち${}{cn}C{3}$個

が重複して数えられていますので、これらを引きます。

提出コード

int main(){

    int N; cin >> N;
    vector<ll> A(N); for(int i = 0; i < N; i++) cin >> A[i];
    
    vll cnt(200010, 0);
    for(auto a: A) cnt[a]++;

    auto nC2 = [&](ll n) -> ll {
        return (n * (n-1)) / 2;
    };

    auto nC3 = [&](ll n) -> ll {
        return (n * (n-1) * (n-2)) / 6;
    };

    ll ans = nC3(N);
    for(auto cn: cnt) if(cn > 1){
        ans -= nC2(cn) * (N - cn);
        ans -= nC3(cn);
    }

    cout << ans << endl;
}

余事象を使いましたが、言い換えをすることでさらに簡単になります。与えられた条件は「$A_i < A_j < A_k$を満たす$(i, j, k)$の組の個数を求めよ」と読み替えることができるため、中央の$j$を全探索することで解けます。

E Roas Reduction

問題

$N$個の都市$1, 2, \cdots, N$と$M$本の道路$1, 2, \cdots, M$があります。

道路$i$は都市$A_i$と$B_i$を双方向に結び、距離は$C_i$です。どの都市間もいくつかの通路を通って行き来できます。

どの都市間もいくつかの道路を通って行き来できるという条件を満たすように$N-1$本の道路を保守し、それ以外の道路を廃道にすることにしました。保守する道路のみを通って都市$1$から都市$i$へ移動するときの距離を$d_i$とするとき、保守する道路の選び方であり$d_2+d_3+\cdots+d_N$を最小化するようなものを$1$つ出力してください。

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

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

$1 \leq A_i < B_i \leq N$

$i \neq j \Rightarrow (A_i, B_i) \neq (A_j, B_j)$

$1 \leq C_i \leq 10^9$

考察

頂点1からダイクストラをし、使った道を答えればよいです。

提出コード

int main(){

    map<pii, int> node;
    ll N, M; cin >> N >> M;
    vector<vector<pll>> G(N);
    rep(i, M){
        int a, b, c; cin >> a >> b >> c; a--; b--;
        if(a > b) swap(a, b);
        node[{a, b}] = i + 1;
        G[a].pb({b, c});
        G[b].pb({a, c});
    }

    vi Ans;
    min_priority_queue<pair<ll, pll>> que;
    vll dist(N, INF);
    dist[0] = 0;
    que.push({0, {0, -1}}); // dist, idx, bef
    
    
    while(!que.empty()){
        auto [di, now] = que.top(); que.pop();
        if(dist[now.fi] < di) continue;
        if(now.se != -1){
            int a = now.fi, b = now.se;
            if(a > b) swap(a, b);
            Ans.pb(node[{a, b}]);
        }
        
        for(auto e: G[now.fi]) if(dist[e.fi] > dist[now.fi] + e.se){
            dist[e.fi] = dist[now.fi] + e.se;
            que.push({dist[e.fi], {e.fi, now.fi}});
        }
    }

    for(int i = 0; i < Ans.size(); i++){
        cout << Ans[i] << (i != Ans.size() - 1 ? ' ' : '\n');
    }
}

「どこから来たのか」を持つためにだいぶぐちゃぐちゃなコードを書いてしまいました。時間があるときにupsolveしたいです…

F Bread

問題

長さ$L$のパンが1つあり、これを$N$人の子供たちに切り分けます。$i$番目のこともは長さ$A_i$のパンを欲しがっています。そこで、高橋君は次の操作を繰り返して、長さ$A_1, A_2, \cdots, A_N$のパンを切り出して配ることにしました。

長さ$k$のパン$1$つと$1$以上$k-1$以下の整数$x$を選ぶ。選んだパンを長さ$x$と$k-x$のパンに切り分ける。

この時、$x$の値によらずコストが$k$かかる。

誰にも配られずに余るパンがいくつあってもかまいません。すべての子供たちにパンを配るために必要な最小のコストを求めてください。

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

$1 \leq A_i \leq 10^9$

$\sum_{i=1}^N A_i \leq L \leq 10^{15}$

考察

蟻本49ページを開きます。すると$\sum_{i=1}^N A_i = L$のときの考え方が載っています。

$\sum_{i=1}^N A_i < L$のときは、$i+1$番目の子供が長さ$L - \sum_{i=1}^N A_i$のパンを欲しがっていると考えればよいです。

証明は…わかりません…

提出コード

int main(){

    ll N, L; cin >> N >> L;
    vector<ll> A(N); for(int i = 0; i < N; i++) cin >> A[i];
    min_priority_queue<ll> que;
    for(auto a: A) que.push(a);
    if(sum(A) != L) que.push(L - sum(A));
    ll cost = 0;
    while(que.size() > 1){
        ll mi1 = que.top(); que.pop();
        ll mi2 = que.top(); que.pop();
        cost += mi1 + mi2;
        que.push(mi1 + mi2);
    }
    cout << cost << endl;
    
}