お久しぶりです。オンサイトやら何やらが被りに被って更新が途切れていましたが、ちまちまと更新していきます。競プロ以外の、シンプルな日記とかもたまには更新したいと思っていますが、まぁそのうち... # A. Cloudberry Jam 2kgのcloudberryから色々すると3kgのジャムが完成するので、3kgのジャムをn個用意するのに必要なcloudberryは$2N$です。 ```cpp void solve() { int n; cin>>n; cout<<2*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を通してから戻ってくると、明らかに二分探索の下界を間違えているので直して提出すると通ります。 ```cpp 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 << ' '; } 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でチェックしてあげればよいですね。 ```cpp 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 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<> t; while(t--)solve(); } ``` # D. Even String ...ん？これどこかで見覚えがありますね？ `

Dこれの気持ちになってしまったので気合でメモ化再帰で980ms https://t.co/KmRSxQVNDb
— ardririy❄* (@ardririy) April 3, 2025

` ということで、メモ化再帰でやると通ります。あとから指摘されましたが計算量保証はできません。とりあえず定数倍の良い$O(T2^\sigma)$です。テストケースが弱いのでOK！ ```cpp using mint = ModInt<998244353>; mint fact[300003]; const int n = 26; vector c(n); mint choose(int n, int k) { return fact[n] / (fact[k] * fact[n-k]); } map, 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 << ' '; } 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(); } ```

Educational Codeforces Round177