接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

トップ > AtCoderBeginnerContest162 > AtCoder Beginner Contest 162（ABC162）

AtCoder Beginner Contest 162（ABC162）

AtCoderBeginnerContest162 AtCoderBeginnerContest ABC162 ABC

atcoder.jp

4完13:30でパフォ1500ちょっと
1500取ってもレートが10とかしか上がらなくなってきたね

A - Lucky 7

N mod 10と\lfloor \frac{N}{10} \rfloor mod 10と \lfloor \frac{N}{100} \rfloor mod 10が7になるか見ればいい
文字列でやったほうが楽だったかな
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    if(N % 10 == 7 || (N / 10) % 10 == 7 || (N / 100) == 7) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - FizzBuzz Sum

ループで愚直に足していっても間に合うので愚直にやる
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    ll sum = 0;
    for(int i=1;i<=N;i++){
        if(i % 3 == 0 || i % 5 == 0) continue;
        sum += i;
    }
    cout << sum << endl;
}

C - Sum of gcd of Tuples (Easy)

200^3なら余裕で間に合うので3重ループで求める
gcd(a, b, c)はgcd(gcd(a,b), c))で求められる
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int K;
    cin >> K;
    ll ans = 0;
    for(int i=1;i<=K;i++){
        for(int j=1;j<=K;j++){
            for(int k=1;k<=K;k++){
                ans += gcd(gcd(i,j), k);
            }
        }
    }
    cout << ans << endl;
}

D - RGB Triplets

これ緑difficulty行かないんだね、すごいなあ
条件よりS_i \neq S_jなのでiとjを全探索することを考える
そうすると S_i \neq S_k and S_j \neq S_kを満たすものを高速に数えられればいい
これは累積和を使うことで可能となる
ただし j - i \neq k - jという条件があるので、S_{j + ( j - i)}が条件を満たしていた場合、その分を引いて上げる必要がある
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    string S;
    cin >> N >> S;
    vector<ll> cumR(N+1), cumG(N+1), cumB(N+1);
    REP(i,N){
        cumR[i+1] = cumR[i] + (S[i] == 'R');
        cumG[i+1] = cumG[i] + (S[i] == 'G');
        cumB[i+1] = cumB[i] + (S[i] == 'B');
    }
    ll ans = 0;
    REP(i,N){
        for(int j=i+1;j<N-1;j++){
            if(S[i] == S[j]) continue;
            if(S[i] != 'R' && S[j] != 'R'){
                ans += cumR[N] - cumR[j];
                if(j + j - i > N) continue;
                if(S[2*j - i] == 'R') ans--;
            }
            if(S[i] != 'G' && S[j] != 'G'){
                ans += cumG[N] - cumG[j];
                if(j + j - i > N) continue;
                if(S[2*j - i] == 'G') ans--;
            }
            if(S[i] != 'B' && S[j] != 'B'){
                ans += cumB[N] - cumB[j];
                if(j + j - i > N) continue;
                if(S[2*j - i] == 'B') ans--;
            }
        }
    }
    cout << ans << endl;
}

E - Sum of gcd of Tuples (Hard)

これ難しい
まずgcdがk( 1 \leq k \leq K) となる場合の数を数えたい
ただし、kを数える時kの倍数の分を引いて上げる必要がある
そのためには、上から個数を保存しながら数えていき、その分を引いてあげればいい
本番ではここまでは考えられていたけど、包除する分がずっと上手く行かないまま終わってしまった
kの倍数の個数のカウントと、場合の数のカウントを同時にやろうとしてたから沼にハマってたっぽい
終わった後他の人の実装見ながら別々にやってあげるとすっきりしたコードでAC

提出コード

using mint = Fp<MOD>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;

    vector<ll> cnt(K + 1, 1);
    for(int i=1;i<=K;i++){
        for(int j=2*i;j<=K;j+=i) cnt[i] += cnt[j];
    }
    vector<mint> res(K + 1);
    for(int i=K;i>=1;i--){
        res[i] += modpow(mint(cnt[i]), N);
        for(int j=2*i;j<=K;j+=i) res[i] -= res[j];
    }
    mint ans = 0;
    for(int i=1;i<=K;i++) ans += mint(i) * res[i];
    cout << ans << endl;
}

F - Select Half

本番中はチラ見しただけで終わった
パッと見た感じ貪欲だと死にそうでDPしないといけなさそうな見た目だった
良い感じのDPらしいのでちゃんと解いておきたい

おわりに

1500取っても微増しかしないの直感に反しちゃうね
青パフォ安定して取れるようにしたいなあ（青difficultyを本番で通したい）