Codechef Starters176 Div.2

Clothing Store

\(XL\) サイズから順に計算していって、余ったTシャツがあれば次に繰り越していけばよいです。

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 << '\n';
}

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

Costly Summit

制約が小さいので、各言語について学習するかどうかを決めるbit全探索をします。
翻訳してもらうときのコストは言語別ではないことに注意。

using ll = long long;
#define rep(i,n) for (ll i=0;i<n;++i)

void solve() {
    ll n, c; cin >> 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<<m) {
        ll sum = 0;
        ll sum2 = 0;
        rep(j, m) {
            if(times[j]==0) continue;
            if ((i>>j)&1==1) sum2 += times[j];
            else sum += c;
        }
        chmin(ans, sum+(sum2 * (sum2+1)/2));
    }
    cout << ans << '\n';
}

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符号あり整数として解釈されることを完全に忘れており、オーバーフローによってかなりの時間を消費しました...

using ll = long long;
#define rep(i,n) for (ll i=0;i<n;++i)

void solve() {
    ll n, m; cin >> n >> m;
    vector<ll> ans;

    ans.push_back(n);
    rep(i, 63) {
        if((n>>i)&1 == 1) continue;
        ll val = n | (1LL<<i);
        if(val>m) continue;
        ans.push_back(val);
    }
    if(ans.size() == 1) cout << "-1\n";
    else {
        cout << ans.size() << '\n';
        rep(i, ans.size()) cout << ans[i] << ((i+1==ans.size()) ? '\n' : ' ');
    }
}

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\) の組み合わせが不変です 。
組み合わせとしてありうるものは \((0, 0), (0, 1), (1, 1)\) の3種類です。自由にswapが可能なことを考えると、回文を構成するためには「ペア」が存在する必要があるので、それぞれの組み合わせの種類が偶数となっているかを判定すればよいでしょう 。

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\n";
    else cout << "Yes\n";
}

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

Mex-P Tree (Easy)

解きはしたんですが、コンテスト時間中には間に合わず。
\(A_i \leq 10^9\) であり、 \(10^9 \leq 2\times3\times\cdots\times29\) であることを考えると、答えはこれぐらいの範囲に収まります。この事実に思い当たれば、Easyでは \(N=2000\) と小さいため、各頂点を根とする木を考えて愚直に全探索を行うことで \(O(N^2)\) 時間で解くことができます。

int primes[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
ll dfs(int p, vvll& g, vector<bool>& 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<bool> seen(n, false);
        ans.push_back(dfs(i, g, seen, count, 1, a));
    }
    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();
}