読者です 読者をやめる 読者になる 読者になる

CodeForces Round#380 Div2


http://codeforces.com/contest/738

A
なんか普通に数える。

#include <bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    string s;
    cin >> s;
    string ans = "";
    for(int i = 0; i < n; ){
        bool ok = [&]() {
            if(i >= n - 2) return true;
            if(s.substr(i, 3) != "ogo") return true;
            i = i + 3;
            for(int j = i; j < n - 1; j += 2) {
                if(s.substr(j, 2) == "go")
                  i = j + 2;
                else
                  break;
            }
            return false;
        }();
        if(ok) {
            ans += s[i];
            ++i;
        }
        else {
            ans += "***";
        }
    }
    cout << ans << endl;
    return 0;
}

B
累積和

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> fld(n, vector<int>(m, 0));
    for(auto& v : fld) for(int& x : v) cin >> x;
    auto yoko = fld, tate = fld;
    for(int i : in(n)) {
        for(int j : in(m - 1))
          yoko[i][j + 1] += yoko[i][j];
    }
    for(int j : in(m)) {
        for(int i : in(n - 1))
          tate[i + 1][j] += tate[i][j];
    }
    int cnt = 0;
    for(int i : in(n)) for(int j : in(m)) {
        if(fld[i][j]) continue;
        if(i > 0) if(tate[i - 1][j] > 0) ++cnt;
        if(j > 0) if(yoko[i][j - 1] > 0) ++cnt;
        if(n - 1 > i) if(tate[n - 1][j] - tate[i][j] > 0) ++cnt;
        if(m - 1 > j) if(yoko[i][m - 1] - yoko[i][j] > 0) ++cnt;
    }
    cout << cnt << endl;
    return 0;
}

C
二分探索。
そもそもtが無理ゲーのとき(二分探索して、rの値が最初に設定した上限になる場合)の対応を忘れていて落ちた。
このくらいpretestに入れろよ、とは思うけど仕方ないね。
4行追加しただけで通って鬱になった。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 INF = 1e18;
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    i64 n, k, s, t;
    cin >> n >> k >> s >> t;
    vector<pair<i64, i64>> cars(n);
    for(auto& p : cars) cin >> p.first >> p.second;
    vector<i64> gas(k + 1);
    for(int i : in(k)) cin >> gas[i];
    gas.back() = s;
    sort(gas.begin(), gas.end());
    i64 l = -1LL, r = s * 3;
    while(r - l > 1LL) {
        i64 mid = (l + r) / 2LL;
        bool ok = [&]() {
            i64 before = 0LL, sum = 0LL;
            const i64 can_use = mid;
            for(auto cur : gas) {
                i64 dist = cur - before;
                if(dist > can_use) return false;
                if(can_use >= dist * 2) {
                    sum += dist;
                    before = cur;
                    continue;
                }
                i64 diff = can_use - dist;
                sum += diff + (dist - diff) * 2LL;
                before = cur;
            }
            return sum <= t;
        }();
        if(ok)
          r = mid;
        else
          l = mid;
    }
    if(r == s * 3) {
        cout << -1 << endl;
        return 0;
    }
    i64 ans = INF;
    for(auto p : cars) {
        if(p.second >= r)
          ans = min(ans, p.first);
    }
    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}

D
とりあえず左から貪欲に置いて、あとは鳩の巣原理。
 普通に解けなかった。

#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n, num, len, m;
    cin >> n >> num >> len >> m;
    string s;
    cin >> s;
    s += '1';
    vector<int> blocks;
    int start = 0;
    bool in_range = false;
    for(int i : in(n + 1)) {
        if(s[i] == '1') {
            if(in_range == true) {
                in_range = false;
                int length = i - start;
                for(int k : in(length / len))
                  blocks.emplace_back(start + k * len);
            }
        }
        else {
            if(in_range == false) {
                in_range = true;
                start = i;
            }
        }
    }
    vector<int> ans;
    for(int i : in((int)(blocks.size()) - (num - 1)))
      ans.emplace_back(blocks[i] + (len - 1));
    cout << ans.size() << endl;
    for(auto x : ans) cout << x + 1 << ' ';
    cout << endl;
    return 0;
}

Dはちょっと難しいけどまあ普通に解けなきゃいけない感じだし、Cを落とすのはキツイなあ。
なんかこどふぉ久々すぎてコーナーケースに対する勘が鈍っていた感じがあり、険しい。