# Clothing Store $XL$サイズから順に計算していって、余ったTシャツがあれば次に繰り越していけばよいです。 ```cpp void solve() { int x, y, z, a, b, c; cin >> x >> y >> z >> a >> b >> c; int left = 0; int ans = 0; ans += min(z, c); left = max(0, z-c); ans += min(y+left, b); left = max(0, y+left-b); ans += min(x+left, a); cout << ans << ' '; } int main() { cin.tie(0); ios::sync_with_stdio(false); int t; cin >> t; while(t--) solve(); } ``` # Costly Summit 制約が小さいので、各言語について学習するかどうかを決めるbit全探索をします。翻訳してもらうときのコストは言語別ではないことに注意。 ```cpp using ll = long long; #define rep(i,n) for (ll i=0;i> n >> c; string s; cin >> s; rep(i, m) times[i] = 0; rep(i, n) times[s[i] - 'A'] += 1; ll ans = inf; rep(i, 1<>j)&1==1) sum2 += times[j]; else sum += c; } chmin(ans, sum+(sum2 * (sum2+1)/2)); } cout << ans << ' '; } int main() { cin.tie(0); ios::sync_with_stdio(false); int t; cin >> t; while(t--) solve(); } ``` # Same And 3つめの条件を満たすためには、$N$でもともと立っているbitは必ず立てておく必要があり、そうでないbitについては$S$に含める数の中で競合しなければよいです。これを競合させたくないこと、またできるだけ$S$を長く取りたいことから、$N$のまだ立っていないbitを1つだけ立てる、$M$以下ならば$S$に加えるということを考えるのが良さそうです。実装においてC++ではリテラルの数はsuffixに何もつけなければ32bit符号あり整数として解釈されることを完全に忘れており、オーバーフローによってかなりの時間を消費しました... ```cpp using ll = long long; #define rep(i,n) for (ll i=0;i> n >> m; vector ans; ans.push_back(n); rep(i, 63) { if((n>>i)&1 == 1) continue; ll val = n | (1LL<m) continue; ans.push_back(val); } if(ans.size() == 1) cout << "-1 "; else { cout << ans.size() << ' '; rep(i, ans.size()) cout << ans[i] << ((i+1==ans.size()) ? ' ' : ' '); } } int main() { cin.tie(0); ios::sync_with_stdio(false); int t; cin >> t; while(t--) solve(); } ``` # Friendly Binary Strings(Upsolve) これは全く分からず。解説を聞いても思いつかなかったなぁと思うなど。操作しても「変わらないもの」に着目します。この問題においては、$A_i, B_i$の組み合わせが不変です[^1]。組み合わせとしてありうるものは$(0, 0), (0, 1), (1, 1)$の3種類です。自由にswapが可能なことを考えると、回文を構成するためには「ペア」が存在する必要があるので、それぞれの組み合わせの種類が偶数となっているかを判定すればよいでしょう[^2]。 ```cpp void solve() { int n; cin >> n; string s, t; cin >> s >> t; int cnt[3] = {0, 0, 0}; rep(i, n) { if (s[i] != t[i]) cnt[1]++; else if (s[i] == '0') cnt[0]++; else cnt[2] ++; } int odd = 0; rep(i, 3) odd += (cnt[i] % 2); odd -= n%2; if(odd>0) cout << "No "; else cout << "Yes "; } int main() { cin.tie(0); ios::sync_with_stdio(false); int t; cin >> t; while(t--) solve(); } ``` [^1]: $A_i$と$B_i$のswapは組み合わせそのものを変えるわけではなく、また$A_i$と$A_j$、$B_i$と$B_j$をそれぞれswapでも、$i, j$を同時に入れ替えるのでやはり組み合わせは変わらない [^2]: 長さが奇数の場合は1つだけペアがない値があっても良いが、それは実装でよしなに # Mex-P Tree (Easy) 解きはしたんですが、コンテスト時間中には間に合わず。 $A_i \leq 10^9$であり、$10^9 \leq 2\times3\times\cdots\times29$であることを考えると、答えはこれぐらいの範囲に収まります。この事実に思い当たれば、Easyでは$N=2000$と小さいため、各頂点を根とする木を考えて愚直に全探索を行うことで$O(N^2)$時間で解くことができます。 ```cpp int primes[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}; ll dfs(int p, vvll& g, vector& seen, int count[], int dept, int a[]) { seen[p] = true; ll idx = 13; rep(i, 12) { if(a[p] % primes[i] == 0) count[i]++; if(count[i] != dept) idx = min(idx, i); } ll res = primes[idx]; for(ll ni: g[p]) { if(seen[ni]) continue; res += dfs(ni, g, seen, count, dept+1, a); } rep(i, 12) { if(a[p] % primes[i] == 0) count[i]--; } return res; } void solve() { int n; cin >> n; int a[n]; rep(i, n) cin >> a[i]; vvll g(n); rep(i, n-1) { int u, v; cin >> u >> v; u--;v--; g[u].push_back(v); g[v].push_back(u); } vll ans; int count[12]; rep(i, 12) count[i] = 0; rep(i, n) { vector seen(n, false); ans.push_back(dfs(i, g, seen, count, 1, a)); } rep(i, n) cout << ans[i] << ((i+1==n)? ' ' : ' '); } int main() { cin.tie(0); ios::sync_with_stdio(false); int t; cin >> t; while(t--) solve(); } ```

Codechef Starters176 Div.2