ARC 063

コンテストに出るのは久しぶりだ。
消化不良気味の問題がないと特に書くこともないのだが、久しぶりなので書く。

C

　これは既出なような。

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    char before = s.front();
    int cnt = 0;
    for(char c : s) {
        if(c != before) ++cnt;
        before = c;
    }
    cout << cnt << endl;
    return 0;
}

D

　結局、高橋君はもっとも差が大きいペアだけでりんごの売買をすると得なので、そのようなペアの数を求めればよい。

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, t;
    cin >> n >> t;
    vector<int> a(n);
    for(auto& x : a) cin >> x;
    int ma = -1, num = 0;
    map<int, int, greater<int>> mp;
    for(int i : in(n - 1, -1)) {
        int x = a[i];
        if(ma > x) mp[ma - x] += num;
        else if(ma == x) ++num;
        else {
            ma = x;
            num = 1;
        }
    }
    if(!mp.empty()) {
        auto it = mp.begin();
        cout << it->second << endl;
    }
    else {
        cout << 0 << endl;
    }
    return 0;
}

E

愚直に、上下に範囲を伝播させるようなDFSを書いた。
割りと実装ゲーだけどこういうのけっこう好き。
コンテスト中に書いたのは汚かったので書き直した。
ダイクストラ解法もあるらしい（つよい）。

vector<vector<int>> adj;
vector<int> num;
vector<pair<int, int>> range;
inline pair<int, int> upPair(const pair<int, int> p) { return make_pair(p.first - 1, p.second + 1);}
bool update(pair<int, int>& l, const pair<int, int>& r) {
    if(l.second < r.first || r.second < l.first) return false;
    bool ok = false;
    if(l.first <= r.first && r.second <= l.second) ok = true;
    if(r.first <= l.first && l.second <= r.second) ok = true;
    if(!ok) if((l.first & 1) == (r.first & 1)) ok = true;
    l.first = max(l.first, r.first);
    l.second = min(l.second, r.second);
    return ok;
}
bool dfs(int cur, int par) {
    auto& myRange = range[cur];
    if(num[cur] != INF) myRange = make_pair(num[cur], num[cur]);
    bool res = true;
    if(par != -1) res &= update(myRange, upPair(range[par]));
    pair<int, int> nRange = upPair(myRange);
    for(int nxt : adj[cur]) if(nxt != par) {
        res &= update(range[nxt], nRange);
        res &= dfs(nxt, cur);
        res &= update(myRange, upPair(range[nxt]));
    }
    return res;
}
void dfs2(int cur, int par) {
    if(num[cur] == INF) {
        num[cur] = range[cur].first;
    }
    pair<int, int> nRange = upPair(range[cur]);
    for(int nxt : adj[cur]) if(nxt != par) {
        update(range[nxt], nRange);
        dfs2(nxt, cur);
    }
}
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    adj.assign(n, vector<int>());
    for(int _ : in(n - 1)) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    num.assign(n, INF);
    int q;
    cin >> q;
    for(int _ : in(q)) {
        int v, p;
        cin >> v >> p;
        --v;
        num[v] = p;
    }
    range.assign(n, make_pair(-INF, INF));
    if(dfs(0, -1) == false) {
        cout << "No" << endl;
    }
    else {
        cout << "Yes\n";
        dfs2(0, -1);
        for(int x : num) cout << x << '\n';
    }
    return 0;
}

F

　分割統治法好き。
　まあコンテスト中は全然解けなかったし解説見ながら実装するだけのやる気もないんだけど。

　わりと好きな問題が出て楽しめた。
　AGCは発想ゲーすぎて歯が立たないので、このくらいが僕にはちょうどいい気がする。