Educational Codeforces Round177

2025-04-04

お久しぶりです。オンサイトやら何やらが被りに被って更新が途切れていましたが、ちまちまと更新していきます。競プロ以外の、シンプルな日記とかもたまには更新したいと思っていますが、まぁそのうち...

A. Cloudberry Jam

2kgのcloudberryから色々すると3kgのジャムが完成するので、3kgのジャムをn個用意するのに必要なcloudberryは \(2N\) です。

void solve() {
    int n; cin>>n;
    cout<<2*n<<'\n';
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--)solve();
}

B. Large Array and Segments

難しいですね。初め、 \(L, R\) の組を数え上げるものだと思っており「どう考えても64bitに収まらなくないですか？」と叫んでいました。が、よく見るとこれ \(L\) を数えるんですね、なるほど。
これは真ん中を圧縮してRがどこになるかを \(A\) を2つ並べた配列で累積和を取って二分探索することで右端がどこになるかを持ってやればいいですね～と言いながら適当に書くとWAが帰ってきます。あの？
一旦C, Dを通してから戻ってくると、明らかに二分探索の下界を間違えているので直して提出すると通ります。

void solve() {
    ll n, k, x;cin>>n>>k>>x;

    vll a(2*n);rep(i,n)cin>>a[i], a[n+i]=a[i];
    vll csum(2*n+1,0); rep(i,2*n)csum[i+1]=csum[i]+a[i];
    ll sum = csum[n] - csum[0];
    vll r(n);
    rep(i,n){
        ll full = 0;
        ll left = x;
        if(x>=sum){
            full = x/sum;
            left = x%sum;    
        }
        
        ll ok = 2*n+1;
        ll ng = i-1;
        while(abs(ok-ng)>1){
            ll mid = (ok+ng)/2;
            if(csum[mid]-csum[i]>=left) ok = mid;
            else ng = mid;
        }

        r[i]=full*n+ok-1;
    }
    ll ans = 0;
    rep(i,n){
        if(r[i]>=n*k) continue;
        ll t = r[i]/n;
        ans+=(k-t);
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--)solve();
}

ECRはICPCルール(のはず)なので、ペナとACが遅れたぶんを合わせて+100ほど。流石に勿体ないです。

C. Disappearing Permutation

操作をした結果、「値を置き換える必要があるもの」を考えてあげると、どうも残っているもので閉路をなしているものは置き換える必要はなくて、そうでないものは置き換える必要がありそうです。適当にUnionFindでチェックしてあげればよいですね。

void solve() {
    int n; cin >> n;
    vll p(n); rep(i,n)cin>>p[i],p[i]--;
    vll q(n); rep(i,n)cin>>q[i],q[i]--;

    dsu uf(n);
    rep(i,n) {
        uf.merge(p[i], p[p[i]]);
    }

    vector<bool> seen(n, false);
    vll ans(n);
    ll cur=0;
    rep(i,n){
        if(!seen[uf.leader(p[q[i]])]) {
            cur+=uf.size(p[q[i]]);
            seen[uf.leader(p[q[i]])]=true;
        }
        ans[i]=cur;
    }

    rep(i,n)cout<<ans[i]<<((i+1==n)?'\n':' ');
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--)solve();
}

D. Even String

...ん？これどこかで見覚えがありますね？

Dこれの気持ちになってしまったので気合でメモ化再帰で980ms https://t.co/KmRSxQVNDb

— ardririy❄* (@ardririy) April 3, 2025

ということで、メモ化再帰でやると通ります。あとから指摘されましたが計算量保証はできません。とりあえず定数倍の良い \(O(T2^\sigma)\) です。テストケースが弱いのでOK！

using mint = ModInt<998244353>;
mint fact[300003];

const int n = 26;
vector<int> c(n);

mint choose(int n, int k) {
    return fact[n] / (fact[k] * fact[n-k]);
}

map<pair<int, int>, mint> memo;
mint rec(int i, int e, int o) {
    if(i==n) {
        if(e==0&&o==0){
            return 1;
        } else {
            return 0;
        }
    }
    if(e>o) swap(e, o);
    P p = {e,o};
    if(memo.find(p)!=memo.end()){
        return memo[p];
    }
    if(c[i]==0){
        return rec(i+1, e, o);
    }

    mint res = 0;
    if(e>=c[i]) {
        res = res + choose(e, c[i]) * rec(i+1, e-c[i], o);
    }
    if(o>=c[i]){
        res = res + choose(o, c[i]) * rec(i+1, e, o-c[i]);
    }

    return memo[p]=res;

}

void solve() {
    int sum = 0;
    memo.clear();
    rep(i,n)cin>>c[i], sum+=c[i];

    int even = sum/2;
    int odd = sum-even;

    cout << rec(0, even, odd).value << '\n';

}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    
    fact[0] = 1;
    rep(i,300001){
        fact[i+1] = fact[i]*(i+1);  
    }

    while(t--)solve();
}