A – 絵画の枚数

四捨五入を満たす整数列 b を構成する問題。 条件は各 i に対して round(100·b_i/Σb)=a_i。 これを区間に直すと (2a_i-1)·Σb/200 ≤ b_i < (2a_i+1)·Σb/200。 Σb ≤ 201 であることから、s を 1…201 まで全探索し、各 s に対して貪欲に b_i を決めればよい。

bool build(int n, vector<int> a, vector<int> &out) {
    for (int s = 1; s <= 201; ++s) {
        vector<int> b(n);
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            b[i] = max(0, ((2 * a[i] - 1) * s + 199) / 200);
            sum += b[i];
        }
        if (sum > s) continue;
        for (int i = 0; i < n && sum < s; ++i) {
            int up = ((2 * a[i] + 1) * s - 1) / 200;
            int add = min(up - b[i], s - sum);
            b[i] += add;
            sum += add;
        }
        if (sum == s) { out.swap(b); return true; }
    }
    return false;
}

B – Blood Memories

2^n 個の状態を持つグラフを用意し、各辺の重みを「その状態遷移で得られる攻撃力」とする。 最大 R 回の遷移で得られる最大ダメージは行列累乗で求められる。

struct Mat {
    int n; vector<vector<i64>> a;
    Mat(int n):n(n),a(n,vector<i64>(n,-1e18)){}
    Mat operator*(const Mat& o) const {
        Mat res(n);
        for (int i=0;i<n;++i)
            for (int k=0;k<n;++k)
                for (int j=0;j<n;++j)
                    res.a[i][j]=max(res.a[i][j],a[i][k]+o.a[k][j]);
        return res;
    }
    Mat pow(i64 k) const {
        Mat res(n), base=*this;
        for(int i=0;i<n;++i) res.a[i][i]=0;
        while(k){ if(k&1) res=res*base; base=base*base; k>>=1; }
        return res;
    }
};

C – Crossing River

二分＋逆向き貪欲。 時刻 T を仮定し、右岸→左岸→右岸… の順に逆向きにシミュレート。 両岸の人を降ろすタイミングで空船が発生したらその分だけ T から減算し、条件を満たせば T を下げる。

bool check(i64 T, int k, vector<int> A, vector<int> B,
           vector<tuple<i64,int,int>>& seq) {
    int ia=0, ib=0, side=0; i64 cur=T;
    while (ia<A.size() || ib<B.size()) {
        if (side==0) {
            if (ia==A.size()) cur-=k;
            else if (cur-k>=A[ia]){ cur-=k; seq.emplace_back(cur,0,ia++); }
            else return false;
        } else {
            if (ib==B.size()) cur-=k;
            else if (cur-k>=B[ib]){ cur-=k; seq.emplace_back(cur,1,ib++); }
            else return false;
        }
        side ^= 1;
    }
    reverse(seq.begin(), seq.end());
    return true;
}

D – Deductive Snooker Scoring

赤球 15 個、カラー 6 個の得点を前計算。 残り球数 n ≥ 6 なら単純に赤球を左右に振り分ける。 n < 6 の場合は不足分のカラーを 2^n 通り割り当ててから同様に判定。

string table[16][202];   // table[r][s] : 残り赤 r, 必要得点 s の打順
void pre() {
    for (int r=0;r<=15;++r) fill(table[r],table[r]+202,"NA");
    for (int r=0;r<=15;++r)
        for (int s=r;s<=r*8;++s){
            if (s==r+1) continue;
            string seq;
            int red=r, need=s-r;
            while (need>=7 && red){ seq+="17"; need-=7; --red; }
            if (need==1){ seq.back()--; need++; }
            if (need){ seq+="1"; seq+=char('0'+need); --red; }
            while (red--) seq+="//1";
            table[r][s]=seq;
        }
}

G – GCD of Subsets

最大個数の部分集合で gcd=k となるように選ぶ。 まず k の倍数を k に置き換え、0 を自由に使えることから 「ペアを作れない要素数 ≤ 0 の個数」で判定。 m が少ない時は余分にペアを崩しても条件を満たせる。

i64 solve(i64 n, i64 k, i64 m) {
    i64 x = n / k, d = n - x;
    if (m <= d + (x % 2 == 0))
        return m + (x + 1) / 2;
    i64 ans = d; m -= d;
    ans += min(x, m);
    x -= m; x = max(x, 0LL);
    ans += (x + 1) / 2;
    return ans;
}

J – Judging Papers

各論文はレビュア m 人の合計が k 以上で通過。 通らなかったものは rebuttal 1 回まで可能（各レビュア ±1）。 b 回まで rebuttal を使って通過数を最大化する貪欲解法。

int judge(int n,int m,int k,int b,vector<vector<int>> score){
    int pass=0;
    for(auto& s:score){
        int sum=accumulate(s.begin(),s.end(),0);
        if(sum>=k){ ++pass; continue; }
        for(int& v:s) v += (v>0?-1:1);
        sum=accumulate(s.begin(),s.end(),0);
        if(sum>=k && b){ ++pass; --b; }
    }
    return pass;
}

L – Label Matching

各頂点を根とする部分木について、 値 x の出現回数を A[x]、B[x] とし、 Σ|A[x]-B[x]| を未マッチ数、A[0]+B[0] をフリーの 0 の個数とすると 未マッチ数 ≤ フリー数 が成立すれば OK。 重い子を残す Dsu-on-tree で各頂点を判定。

struct Solver {
    int n; vector<vector<int>> g;
    vector<int> a, b, sz, big, ans;
    vector<int> cnt0, diff;
    int free, miss;
    Solver(int n,vector<int> A,vector<int> B):
        n(n),a(A),b(B),g(n),sz(n),big(n,-1),ans(n),cnt0(n+1),diff(n+1){}
    void add(int v,int sgn){
        int x=a[v], y=b[v];
        if(x==0) free += sgn;
        else{ miss -= abs(diff[x]); diff[x]+=sgn; miss += abs(diff[x]); }
        if(y==0) free += sgn;
        else{ miss -= abs(diff[y]); diff[y]-=sgn; miss += abs(diff[y]); }
    }
    void dfs1(int u,int p){
        sz[u]=1;
        for(int v:g[u]) if(v!=p){
            dfs1(v,u); sz[u]+=sz[v];
            if(big[u]==-1||sz[v]>sz[big[u]]) big[u]=v;
        }
    }
    void dfs2(int u,int p,bool keep){
        for(int v:g[u]) if(v!=p && v!=big[u]) dfs2(v,u,false);
        if(big[u]!=-1) dfs2(big[u],u,true);
        add(u,1);
        for(int v:g[u]) if(v!=p && v!=big[u])
            for(int i=L[v];i<R[v];++i) add(seq[i],1);
        ans[u]=(free>=miss);
        if(!keep) for(int i=L[u];i<R[u];++i) add(seq[i],-1);
    }
    vector<int> solve(){
        dfs1(0,-1); dfs2(0,-1,false);
        return ans;
    }
};