ABC 249 参加記

2022.04.25

競技プログラミング

30分4完、パフォは1565でした。レートが下がって悲しいです…

終了後にFを通せて、さらに悲しくなりました。priority_queueが出てきませんでした、やばいです。

A Jogging

問題

高橋くんと青木くんはジョギングをすることにしました。

高橋くんは「$A$秒間秒速$B$メートルで歩き、$C$秒間休む」ことを繰り返します。

青木くんは「$D$秒間秒速$E$メートルで歩き、$F$秒間休む」ことを繰り返します。

二人が同時にジョギングを始めてから$X$秒後、高橋くんと青木くんのうちどちらが長い距離を進んでいますか？

$1 \leq A, B, C, D, E, F, X \leq 100$

提出コード

int main(){

    ll A, B, C, D, E, F, X; cin >> A >> B >> C >> D >> E >> F >> X;

    ll Taka = 0, Aoki = 0;

    rep(x, X){
        if(x % (A + C) < A) Taka += B;
        if(x % (D + F) < D) Aoki += E;
    }

    if(Taka == Aoki){
        cout << "Draw" << endl;
    }elif(Taka < Aoki){
        cout << "Aoki" << endl;
    }else{
        cout << "Takahashi" << endl;
    }

}

B Perfect String

問題

英大文字と英小文字からなる文字列のうち、以下の条件をすべて満たすものを素晴らしい文字列ということにします。

英大文字が文字列の中に現れる

英小文字が文字列の中に現れる

すべての文字が相異なる

文字列$S$が与えられるので、$S$が素晴らしい文字列か判定してください。

$1 \leq |S| \leq 100 $

提出コード

int main(){

    string S; cin >> S;
    
    map<char, int> cn;
    bool sm = false, bi = false;

    for(auto s: S){
        if(0 <= s - 'a' && s - 'a' <= 26) sm = true;
        else bi = true;
        cn[s]++;
    }

    bool on = true;

    for(auto [k, v]: cn) if(v > 1) on = false;

    YesNo(sm && bi && on);

}

C Just K

問題

英小文字のみからなる$N$個の文字列$S_1, S_2, \cdots, S_N$が与えられます。この中から文字列を好きな個数選ぶことを考えます。この時、「選んだ文字列の中でちょうど$K$個の文字列に登場する英小文字」の種類数としてあり得る最大値を求めてください。

$1 \leq N \leq 15$

$1 \leq K \leq N$

$S_i$は英小文字からなる空でない文字列であり、同じ文字は2個以上含まれない。

$i \neq j$ならば$S_i \neq S_j$である。

考察

$N$が小さいのでbit全探索をします。それぞれの場合についての最大値を見ていけばよいです。

提出コード

int main(){

    ll N, K; cin >> N >> K;
    vector<string> S(N); for(int i = 0; i < N; i++) cin >> S[i];
    ll ans = 0;
    rep(F, 1 << N){
        ll nx = 0;
        map<char, int> cn;
        rep(i, N) if((F >> i) & 1) {
            for(auto s: S[i]) cn[s]++;
        }

        for(auto [k, v]: cn) if(v == K) nx++;
        chmax(ans, nx);
        
    }
    cout << ans << '\n';

}

D Index Trio

問題

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

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

$A_i = A_j \times A_k$

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

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

考察

$A_i$を固定します。すると、$A_j$は$A_i$の約数である必要があります。よって、$A_i$の約数のみ見ればよいです。$A_i$の約数を求めるパートですが、$\sqrt{A_i}$以下の数を全通り試すのは時間制約が怖かったので、素因数分解を行ってから約数列挙をしました。ですが、このままやっても通るらしいです。

提出コード

// https://github.com/Kyo-s-s/Kyo_s_s_Library/blob/main/md/Eratos.md

int main(){
 
    ll N; cin >> N;
    vector<ll> A(N); for(int i = 0; i < N; i++) cin >> A[i];
    
    ll ans = 0;
 
    vll count(200010, 0);
    for(auto a: A) count[a]++;
 
    Eratos Era(200010);
 
    for(auto a: A){
        auto div = Era.divisor(a);
 
        for(auto d: div){
            ans += count[d] * count[a / d];
        }
 
    }
    
    cout << ans << endl;
    
}

E

解けていません、解けたら考察記事を上げる予定です。

F Ignore Operations

問題

高橋くんは整数$x$を持っています。はじめ、$x = 0$です。

$N$個の操作があります。$i$個目の操作は整数$t_i, y_i$を用いて以下のように表されます。

$t_i = 1$のとき、$x$を$y_i$で置き換える。

$t_2 = 2$のとき、$x$を$x+y_i$で置き換える。

高橋くんは$0$個以上$K$個以下の好きな個数の操作を無視することができます。残った操作を1度ずつ順序を変えずに行ったとき、最終的な$x$の値としてあり得る最大値を求めてください。

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

$1 \leq K \leq N$

$t_i \in {1, 2}$

$|y_i| \leq 10^9$

考察

最後の$t_i = 1$の操作以前は、$x$がどんなに小さくなってもかまいません。重要なのは最後の$t_i = 1$の操作をしてからの$t_i = 2$で、どの操作を無視するかになります。$y_i \geq 0$のときは無条件で操作を行い、$y_i < 0$のときには操作を無視するかしないかを考えます。

これを後ろから頑張っていくと解けます。priority_queueを使うと簡単に書けるのですが、コンテスト中はその発想に至れず、ぐちゃぐちゃしていました…

ACコード

int main(){

    ll N, K; cin >> N >> K;
    vpll ty = {{1, 0}};
    rep(i, N){
        ll t, y; cin >> t >> y;
        ty.pb({t, y});
    }

    ll ans = -INF;

    priority_queue<ll> que;   // 魔法を使い無視するもの
    ll cnt = 0;				  // 無視するタスクの個数

    ll dec = 0;
    ll add = 0;

    ll k = 0;


    repd(i, N + 1){
        auto [t, y] = ty[i];


		// K個以上の操作を無視してしまっているとき　yが最大の操作を採用する
        while(cnt > K - k && cnt > 0){
            ll pop = que.top(); que.pop();
            cnt--;
            dec += pop;
        }

        if(cnt > K - k) break;

        if(t == 1){
            chmax(ans, y + add + dec);
            k++;
        }else{
            if(y < 0){
                que.push(y);
                cnt++;
            }else{
                add += y;
            }
        }
    }

    cout << ans << '\n';

}