AtCoder Beginner Contest 169

atcoder.jp

ooooox (1175th)

問題概要：略
コード：テンプレートのsolver部分のみ、ライブラリはリンク先
テンプレート：一番最後

A - Multiplication 1

言われた通りに実装する

void solver() {
    cout << input() * input() << endl;
}

B - Multiplication 2

うわあめんどくさい
0は困るので最初に処理、オーバーフローが困るのでコンテスト中は `__int128_t` でごまかした

あきらかにこれが楽　人類が求めていた__builtin_mul_overflow

sort してから __builtin_mul_overflow で判定する（最後に 0 があったりすると厄介なので）

— えびちゃん (@rsk0315_h4x) 2020年5月31日

コンテスト中のコード

void solver() {
    int n = input();
    vector< i64 > as(n);
    cin >> as;

    whole(sort, as);
    if (as[0] == 0) {
        cout << 0 << endl;
        return;
    }

    i64 ans = 1;
    range(i, 0, n) {
        if ((__int128_t)ans * as[i] > 1000000000000000000) {
            cout << -1 << endl;
            return;
        }

        ans *= as[i];
    }

    cout << ans << endl;
}

多分こんな感じで書くのが楽

void solver() {
    int n = input();
    vector< i64 > as(n);
    cin >> as;

    whole(sort, as);

    i64 ans = 1;
    for (auto a: as) {
        if (__builtin_mul_overflow(a, ans, &ans)) {
            cout << -1 << endl;
            return;
        }
    }

    if (ans > 1000000000000000000) {
        cout << -1 << endl;
        return;
    }

    cout << ans << endl;
}

まあ __int128_t でもそんなに変わらないかもしれない

C - Multiplication 3

小数点以下2桁で誤差出るとは思わなくてびっくりしちゃったな　かなり学び

コンテスト中は long double でやったらなんかよくわからないうちに通ったけどこれでも誤差出ているっぽい

b を string でうけとって '.' けしてint にして /100 すると通る

void solver() {
    i64 a;
    string s;
    cin >> a >> s;

    int b = stoi(s.substr(0, 1) + s.substr(2, 2));

    cout << a * b / 100 << endl;
}

D - Div Game

まあ素因数分解してくださいって顔に書いてる

DPしたけど多分いらなくて、1, 2, 3, 4, 5, ...とやってとれなくなったら終わりでOKだと思う

なんか素因数分解のライブラリ紛失してたのでうしライブラリからもってきた
ライブラリ：https://raw.githubusercontent.com/ei1333/library/master/math/number-theory/prime-factor.cpp

void solver() {
    i64 n = input();
    auto cnt = prime_factor(n);

    int max_m = 0;
    for (auto p: cnt) {
        chmax(max_m, p.second);
    }

    vector< int > dp(max_m + 1, -1);
    dp[0] = 0;

    range(d, 1, max_m + 1) {
        rrange(i, d, max_m + 1) {
            if (dp[i - d] == -1) continue;
            chmax(dp[i], dp[i - d] + 1);
        }
    }

    int ans = 0;
    for (auto p: cnt) {
        ans += dp[p.second];
    }

    cout << ans << endl;
}

E - Count Median

まず中央値の最小と中央値の最大は簡単に得られて、Nが奇数か偶数かで若干挙動が変わるけど、どちらも少しずつずらしていくと最小から最大の間をすべて網羅できることがわかる

なんか考察あってるのにN偶数のときにやりたいことと全然違うことをしていて1WAした　C通せてないからって慌てず落ち着こうね

void solver() {
    int n = input();
    vector< pair< int, int > > ps(n);
    for (auto &p: ps) cin >> p;

    i64 l, r;

    whole(sort, ps);
    l = ps[n / 2].first;
    if ((n & 1) == 0) l += ps[n / 2 - 1].first;

    whole(sort, ps, [&](auto a, auto b) { return a.second < b.second; });
    r = ps[n / 2].second;
    if ((n & 1) == 0) r += ps[n / 2 - 1].second;

    cout << r - l + 1 << endl;
}

F - Knapsack for All Subsets

本番中に通せなかった　くやしい

集合 の部分集合 であって、 であるようなものを考えると、
残りの 要素を追加するかしないかで構成された 個の集合は条件を満たすので、 要素の集合 がいくつかるかを数え上げたくなる

愚直にやると

として、

dp[0][0] = 1;

for (int i = 0; i < N; ++i) {
  for (int c = N; c > 0; c--) {
    for (int v = S; v >= A[i]; v--) {
      dp[c][v] += dp[c - 1][v - A[i]];
    }
  }
}

ans = 0;
for (int c = 0; c <= N; ++c) {
  ans += dp[c][S] * pow(2, N - c);
}

cout << ans << endl;

になります

これだとまだ なので高速化を考えるのですが、最後に答えを足し込むときに c が1大きくなるにつれて値は1/2倍されていることを使うと、

dp[0][0] = pow(2, N);
(略)
dp[c][v] += dp[c - 1][v - A[i]] / 2;

という遷移になります。各遷移では次に行くと 1/2 倍されているということしか利用していないので c は答えに影響せず、状態が一つ落とせます

ライブラリ: modint 公開しているところに置いていないことを忘れていた　へんなことはしていないので何使ってもいいです

void solver() {
    int n, s;
    cin >> n >> s;

    vector< int > as(n);
    cin >> as;

    auto dp = make_vector(s + 1, modint(0));
    dp[0] = pow(modint(2), n);
    for (auto a: as) {
        rrange(v, a, s + 1) {
            dp[v] += dp[v - a] / modint(2);
        }
    }

    cout << dp[s] << endl;
}

使っているテンプレート

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

// template {{{
#define  range(i, l, r) for (int i = (int)(l); i < (int)(r); (i) += 1)
#define rrange(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); (i) -= 1)

#define  whole(f, x, ...) ([&](decltype((x)) container) { return (f)(  begin(container),  end(container), ## __VA_ARGS__); })(x)
#define rwhole(f, x, ...) ([&](decltype((x)) container) { return (f)( rbegin(container), rend(container), ## __VA_ARGS__); })(x)

#define debug(x) cerr << "(" << __LINE__ << ")" << #x << ": " << (x) << endl

using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

// constexpr i32 mod   = 998244353;
constexpr i32 mod   = 1e9 + 7;
constexpr i32 inf   = 1001001001;
constexpr i64 infll = 1001001001001001001ll;

constexpr int dx[] = {0, -1, 1, 0, -1, 1, -1, 1};
constexpr int dy[] = {-1, 0, 0, 1, -1, -1, 1, 1};

struct IoSetup { IoSetup(int x = 15){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(x); cerr << fixed << setprecision(x); } } iosetup;

template <typename T = i64> T input() { T x; cin >> x; return x; }

template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { range(i, 0, v.size()) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; }
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }

template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }

template <typename T> vector<T> make_vector(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_vector(size_t a, Ts... ts) { return vector<decltype(make_vector(ts...))>(a, make_vector(ts...)); }

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
// }}}

void solver() {
    
}

signed main(int argc, char *argv[]) {
    solver();
}