AtCoder Beginner Contest 164

ooooox (207th)

問題概要：略
テンプレート：一番下

A - Sheep and Wolves

問題文の通りに実装する　特にコメントはなし

void solver() {
    int s = input(), w = input();

    cout << (s <= w ? "unsafe" : "safe") << endl;
}

B - Battle

操作回数を求めて比較

void solver() {
    int a = input(), b = input(), c = input(), d = input();
    
    int cntt = (c + b - 1) / b;
    int cnta = (a + d - 1) / d;

    cout << (cntt <= cnta ? "Yes" : "No") << endl;
}

C - gacha

こういうのは set に突っ込むだけで ok

void solver() {
    int N = input();
    set<string> st;

    range(i, 0, N) {
        string s;
        cin >> s;

        st.insert(s);
    }

    cout << st.size() << endl;
}

D - Multiple of 2019

急に難易度上がるな

Sの下から i 桁の数を前計算して、

r[6] = 123456
r[5] = 23456
r[4] = 3456
r[3] = 456
r[2] = 56
r[1] = 6

こういうものを得たとする。string の index とは逆順なので reverse するなどして対処するとよし。1-indexed なのも。

[5, 1) = 2345　が欲しいときは

r[5] - r[1] = 23450
(r[5] - r[1]) / 10^1 = 2345

という手順で得るとする。
一般に

(r[i] - r[j]) / 10^j

が [i, j) の値

そうすると

[i, j) について
(r[i] - r[j]) / 10^j ≡ 0 (mod 2019)
ならば、[i, j) は 2019 の倍数。
2019 と 10^j は互いに素なので、10^j は mod 2019 の上での積の逆元をもつ

両辺に 10^j をかけると
r[i] - r[j] ≡ 0 (mod 2019)
⇒ r[i] ≡ r[j] (mod 2019)

になって、おわり

void solver() {
    string s;
    cin >> s;
    s += '.';
   
    vector< int > r(s.size());
    whole(reverse, s);

    int k = 1;
    i64 ans = 0;
    map< int, i64 > cnt;
    cnt[0]++;
    range(i, 1, r.size()) {
        (k *= 10) %= 2019;
        (r[i] += (s[i] - '0') * k + r[i - 1]) %= 2019;
        ans += cnt[r[i]];
        cnt[r[i]]++;
    }

    cout << ans << endl;
}

mod がでかいときの癖で map に突っ込んじゃったけど vector で十分です

実装上の工夫：0桁目を string に追加してreverse することで index と下から何桁目かを合わせる

E - Two Currencies

めんどくさい Dijkstra にしか見えなくて、めんどくさい Dijkstra がめんどくさくなかったことはないので迷わず手を動かします〜完〜

JOI 育ちなので空でこういう Dijkstra を実装するのは一瞬なんだけど全然通されてなくてびっくりしちゃった

void solver() {
    int N = input(), M = input(), S = input();

    struct edge {
        int to, a, b;

        edge() {}
        edge(int to, int a, int b) : to(to), a(a), b(b) {}
    };

    auto G = make_vector(N, 0, edge());

    range(i, 0, M) {
        int u = input() - 1, v = input() - 1;
        int a, b;
        cin >> a >> b;

        G[u].push_back(edge(v, a, b));
        G[v].push_back(edge(u, a, b));
    }

    vector< int > c(N), d(N);
    range(i, 0, N) cin >> c[i] >> d[i];

    int MAX_C = 50 * 100;
    S = min(S, MAX_C);

    auto dist = make_vector(N, MAX_C + 1, infll);
    dist[0][S] = 0;

    using P = pair<i64, pair<int, int>>;
    priority_queue<P, vector<P>, greater<P>> pq;
    pq.emplace(0, make_pair(0, S));

    while (!pq.empty()) {
        auto uku = pq.top();
        pq.pop();

        i64 t;
        pair< int, int > p;
        tie(t, p) = uku;

        int v, m;
        tie(v, m) = p;

        if (dist[v][m] < t) continue;

        if (dist[v][min(m + c[v], MAX_C)] > dist[v][m] + d[v]) {
            dist[v][min(m + c[v], MAX_C)] = dist[v][m] + d[v];
            pq.emplace(dist[v][min(m + c[v], MAX_C)], make_pair(v, min(m + c[v], MAX_C)));
        }

        for (auto u: G[v]) {
            if (m - u.a < 0) continue;

            if (dist[u.to][m - u.a] > dist[v][m] + u.b) {
                dist[u.to][m - u.a] = dist[v][m] + u.b;
                pq.emplace(dist[u.to][m - u.a], make_pair(u.to, m - u.a));
            }
        }
    }


    range(t, 1, N) {
        i64 ans = infll;
        range(i, 0, MAX_C + 1) {
            chmin(ans, dist[t][i]);
        }
        cout << ans << endl;
    }

}

F - I hate Matrix Construction

老後にやります

使っているテンプレート

#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();
}

Luzhiled's memo

メモということです