ABC178 解法 • knshnbのブログ

A - Not

notを出力。

signed main() {
    Int x;
    std::cin >> x;
    std::cout << !x << std::endl;
}

B - Product Max

$x$を固定すると、$x$が負のとき$y$は小さいほうが、正のとき$y$は大きいほうがいい。同様に考えると、4端点だけ考慮すればよいことがわかる。

signed main() {
    Int a, b, c, d;
    std::cin >> a >> b >> c >> d;
    std::cout << std::max({a * c, a * d, b * c, b * d}) << std::endl;
}

C - Ubiquity

(0をかならず使う) + (9をかならず使う) + (0も9も使わない) - (全体)

signed main() {
    Int n;
    std::cin >> n;
    mint all = pow(mint(10), n);
    mint zero = all - pow(mint(9), n);
    mint nine = all - pow(mint(9), n);
    std::cout << zero + nine + pow(mint(8), n) - all << std::endl;
}

D - Redistribution

各$k$について、各要素0以上で和が$S - 3k$になる場合の数を数えればよい。

signed main() {
    Combination<mint> comb;
    Int S;
    std::cin >> S;
    mint ans = 0;
    REP(k, 1, S + 1) {
        Int rem = S - 3 * k;
        if (rem < 0) continue;
        ans += comb(rem + k - 1, rem);
    }
    std::cout << ans << std::endl;
}

E - Dist Max

45度回転すると、x,y座標の差の絶対値のmaxになる。

signed main() {
    Int n;
    std::cin >> n;
    std::vector<Int> x(n), y(n);
    REP(i, n) std::cin >> x[i] >> y[i];
    Int ans = -1;
    REP(t, 2) {
        Int mi = 1e18, ma = -1e18;
        REP(i, n) {
            chmin(mi, t ? x[i] + y[i] : x[i] - y[i]);
            chmax(ma, t ? x[i] + y[i] : x[i] - y[i]);
        }
        chmax(ans, ma - mi);
    }
    std::cout << ans << std::endl;
}

F - Contrast

aとb合わせて最も多い数が過半数を占めていなければできることが帰納的に示せる。 bの要素を左から、bにこれから使う必要のある数のうち、今見ているaの要素と別のものでa,bの残りで最も数の多い要素に決めていけばよい。

void no() {
    std::cout << "No\n";
    exit(0);
}
using pii = std::pair<Int, Int>;
signed main() {
    Int n;
    std::cin >> n;
    std::map<Int, Int> rem;
    std::vector<Int> a(n), b(n);
    REP(i, n) std::cin >> a[i], a[i]--;
    REP(i, n) std::cin >> b[i], b[i]--, rem[b[i]]++;
    auto seg = make_segment_tree<pii>([&](pii x, pii y) { return std::max(x, y); }, {-1e9, -1});
    seg.set_by_identity(n);
    REP(i, n) seg.update(i, {0, i});
    REP(i, n) {
        for (Int x : {a[i], b[i]}) {
            auto p = seg.query(x, x + 1);
            assert(x == p.second);
            seg.update(x, {p.first + 1, p.second});
        }
    }
    std::vector<Int> ans;
    REP(i, n) {
        {
            auto p = seg.query(a[i], a[i] + 1);
            seg.update(a[i], {p.first - 1, p.second});
        }
        auto p1 = seg.query(0, n);
        while (rem[p1.second] == 0) {
            seg.update(p1.second, {-1, p1.second});
            p1 = seg.query(0, n);
        }
        if (p1.second != a[i]) {
            ans.push_back(p1.second);
            rem[p1.second]--;
            seg.update(p1.second, {p1.first - 1, p1.second});
        } else {
            seg.update(p1.second, {0, p1.second});
            auto p2 = seg.query(0, n);
            while (rem[p2.second] == 0) {
                seg.update(p2.second, {-1, p2.second});
                p2 = seg.query(0, n);
            }
            if (p2.first <= 0) no();
            ans.push_back(p2.second);
            rem[p2.second]--;
            seg.update(p2.second, {p2.first - 1, p2.second});
            seg.update(p1.second, p1);
        }
    }
    std::cout << "Yes\n";
    REP(i, n) std::cout << ans[i] + 1 << " ";
    std::cout << std::endl;
}