Educational Codeforces Round 97 (Rated for Div. 2)

codeforces.com

A. Marketing Scheme

x mod aを考えるとxがaよりも大きいとaはそのままになるので考えやすくなる
$x \lt a$とすると$ \frac{a}{2} \leq $ x mod a は$ \frac{a}{2} \leq $ l mod a $ \leq $ r mod a $ \lt a$ を満たせばいい
よって$ r \lt 2 \times l $ であれば条件を満たすことができる
提出コード

void solve(){
    ll l, r;
    cin >> l >> r;
    if(r + 1 <= 2 * l) cout << "YES" << endl;
    else cout << "NO" << endl;
}

B. Reverse Binary Strings

エスパーした、難しい
$ S[i] = S[i+1] $の個数を$ n $とすると1回の操作で最大2個、この個数を減らすことができる
そのため、$ \lceil \frac{n + 1}{2} \rceil $を出力する
提出コード

void solve(){
    int n;
    string s;
    cin >> n >> s;
    int cnt = 0;
    REP(i,n-1) if(s[i] == s[i+1]) cnt++;
    cout << (cnt + 1) / 2 << endl;
}

C. Chef Monocarp

難しいのでとりあえずdpを考えた
$ dp[i][j] := $時刻iのときにをjを取った時の最小値みたいにやろうとしてバグる
$ t_i $ の昇順にある時刻で取ったほうが嬉しそうなので$ t_i $を昇順ソートしてから上記のdpをすればいい
本番中頭から抜けてたけどフローで殴れる
提出コード(dp)

void solve(){
    int n;
    cin >> n;
    vector<int> t(n);
    REP(i,n) cin >> t[i];
    sort(t.begin(), t.end());
    vector<vector<int>> dp(n+1, vector<int>(2*n+10, INF));
    dp[0][0] = 0;
    REP(i,n){
        REP(j,2*n){
            for(int k=j+1;k<2*n;k++){
                if(dp[i][j] == INF) continue;
                chmin(dp[i+1][k], dp[i][j] + abs(t[i] - k));
            }
        }
    }
    int ans = INF;
    REP(j,2*n) chmin(ans, dp[n][j]);
    cout << ans << endl;
}

提出コード(フロー)

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    int m = 3*n;
    PrimalDual<ll, ll> g(n + m +10);
    int s = m + n + 1;
    int t = m + n + 2;
    REP(i,m) REP(j,n){
        g.add_edge(i, m+j, 1, abs(i + 1 - a[j]));
    }
    REP(i,m) g.add_edge(s, i, 1, 0);
    REP(i,n) g.add_edge(m+i, t, 1, 0);
    cout << g.min_cost_flow(s, t, n) << endl;
}

D. Minimal Height Tree

ある頂点の子は昇順に並んでいる
そのため単調増加の間は、今見ている頂点の子、そうでなければ次の頂点の子になる
そのため、頂点をqueueに入れていき、単調増加の間q.front()の子にそうでなければpop()して次の頂点の子にすることを繰り返していく
最後にdfsなどで高さを求めればいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    REP(i,n){
        cin >> a[i];
        --a[i];
    }
    queue<int> q;
    q.emplace(0);
    int cur = 0;
    vector<vector<int>> g(n);
    for(int i=1;i<n;i++){
        if(cur > a[i]) q.pop();
        g[q.front()].emplace_back(a[i]);
        cur = a[i];
        q.emplace(a[i]);
    }
    int ans = 0;
    auto dfs = [&](auto && self, int v, int par, int d = 0)->void{
        chmax(ans, d);
        for(auto nv : g[v]){
            if(nv == par) continue;
            self(self, nv, v, d + 1);
        }
    };
    dfs(dfs, 0, -1);
    cout << ans << endl;
}