AtCoder Beginner Contest 191 - zeronosu77108’s blog

はい． AtCoder Beginner Contest 191 です
久しぶりにブログを書きます。

ABE の3完でした。 C は問題文の意味が理解できなかったです…

全部解き直ししたのでまとめておききます。

A - Vanishing Pitch

$D$ が、消えている $T$ 秒後から $S$ 秒後までの間に入っていたら打つことができません。等速直線運動をするので、 $T$ 秒後に進んでいる距離は、 $T \times V$ ですね。 $S$ も同様に求められるので、適当に判定します。

int main() {
    int v, t, s, d;
    cin >> v >> t >> s >> d;
 
    if (v*t <= d && d <= v*s) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }
}

B - Remove It

問題文

$X$ と等しいものだけ出力しなければ良いです。 AtCoder のジャッジではスペースや改行を区別らしいので適当に continue しても良いのですが、削除して出力してみました。

int main() {
    int n, x;
    cin >> n >> x;
 
    vector a(n, 0);
    for (int i=0; i<n; i++) cin >> a[i];
 
    a.erase(remove_if(a.begin(), a.end(), [&](const int& a){return a==x;}), a.end());
    for (int i=0; i<a.size(); i++) {
        cout << a[i] << (i+1==a.size()? "" : " ");
    }
    cout << endl;
}

こんな感じでも通ります。

int main() {
    int n, x;
    cin >> n >> x;
 
    vector a(n, 0);
    for (int i=0; i<n; i++) cin >> a[i];
 
    for (const auto& ai : a) {
        if (ai == x) continue;
        cout << ai << endl;
    }
}

C - Digital Graffiti

問題文

本番中に問題文の意味が理解できませんでした… 本番中は凸多角形しか頭にありませんでした。凹多角形も含まれるんですね。

正方形をいくつか塗りつぶした図形があるので、それが何角形か判定してくださいというものです。

以下の図は8角形です。

f:id:zeronosu77108:20210212134507j:plain:w250

角は尖っているところかへこんでいるところなので、以下のように 4マス見て黒が1つか3つの所を数えます。

f:id:zeronosu77108:20210212134523j:plain:w200

向きが変わっても白い部分をベースに周りの4つを確かめたら良いので、全部探索します。

int main() {
    int h, w;
    cin >> h >> w;
 
    vector<string> s(h);
    for (int i=0; i<h; i++) cin >> s[i];
 
    vector dx = { -1,  0, -1,  0};
    vector dy = { -1, -1,  0,  0};
    int ans = 0;
 
    for (int i=1; i<h; i++) {
        for (int j=1; j<w; j++) {
            int cnt = 0;
            for (int k=0; k<4; k++) {
                if (s[i+dy[k]][j+dx[k]] == '#') cnt++;
            }
            if (cnt == 1 || cnt == 3) ans++;
        }
    }
 
    cout << ans << endl;
}

D - Circle Lattice Points

問題文

あの…難しくないですか？

本番中には、 x を（ループを回して）決め打ちして y 座標を上下求めたらその間にある整数の個数を求めることができるなーと考えていました。しかし、円の方程式しか出てこなくてどうやって求めるんだ…ってなっていました。

x座標と円の半径が分かっているので、三平方の定理で求めるらしいです。それが分かっていても、実装が大変… 誤差が大変なのでまず、全値を 10000 倍とかして計算します。 y座標を求めて、良い感じに整数に丸めなければなりません。苦手です。

int main() {
    long double tx, ty, tr;
    cin >> tx >> ty >> tr;
 
    long d = 10000;
    long x = round(tx * d);
    long y = round(ty * d);
    long r = round(tr * d);
 
    long xl = (x-r > 0)? (x-r+d-1)/d*d : (x-r)/d*d;
    long xu = (x+r < 0)? (x+r-d+1)/d*d : (x+r)/d*d;
 
    long ans = 0;
    for (long i=xl; i<=xu; i+=d) {
        long t = r*r - (x-i)*(x-i);
        long yd = sqrt(t) - 1;
        while ((yd+1)*(yd+1) <= t) yd++;
 
        long yu = (y+yd < 0)? (y+yd-d+1)/d : (y+yd)/d;
        long yl = (y-yd > 0)? (y-yd+d-1)/d : (y-yd)/d;
 
        if (yu < yl) continue;
        ans += abs(yu - yl) + 1;
    }
 
    cout << ans << endl;
}

E - Come Back Quickly

問題文

癒やしですか…？こういうの好きです。

$N, M \leq 2000$ とかなり小さいので各頂点からダイクストラしても間に合いそうです。ここである頂点i から出発して i に戻ってきたときの処理がめんどくさいんですが、距離を保存する配列を1つ余分に持っておいて、そこにためていけば良いです。

using P = pair<long, long>;

vector<long> dijkstra(long n, long s, vector<vector<P>> g) {
    vector<long> d(n+1,INT_MAX);
    priority_queue<P, vector<P>,greater<>> q;
    q.emplace(0,s);
    d[s] = 0;

    while (! q.empty()) {
        const auto [cost, u] = q.top(); q.pop();
        if (d[u] < cost) continue;

        for (auto [e, c] : g[u]) {
            if (e == s) { d[n] = min(d[n], d[u] + c); }
            else if (d[e] > d[u] + c) {
                d[e] = d[u] + c;
                q.emplace( d[e], e);
            }
        }
    }
    return d;
}

int main() {
    int n, m;
    cin >> n >> m;

    vector g(n, vector<P>());
    for (int i=0; i<m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        g[a].emplace_back(b, c);
    }

    for (int i=0; i<n; i++) {
        const auto dist = dijkstra(n, i, g);
        if (dist[n] < INT_MAX) cout << dist[n] << endl;
        else cout << -1 << endl;
    }
}

F - GCD or MIN

問題文

min を取るので、 $A$ の最小値以下の値じゃなければ、残らないということはすぐに分かったのですがその後どうするんだーとなりました。

gcd を取るため、残る候補としては $A _ i$ の約数どれかです。その約数を作れるかどうかは、その値を約数に持つ値同士の gcd を取ればその値を作れるか分かります。そしてその約数を持つもの同士の gcd はどうやってもその約数未満にはならないです。

そこで、 $A _ i$ の約数を求めつつ、同じ約数を持つ値と gcd を取って map などにためていきます。そして map にある key と value が一致するものだけが、 $A$ から 1つ以上の要素を選んで gcd で作れる値です。

その値のうち min(A) 以下となるものを数えたら答えです。

int main() {
    int n;
    cin >> n;

    vector a(n, 0);
    for (int i=0; i<n; i++) cin >> a[i];

    int amin = *min_element(a.begin(), a.end());

    unordered_map<int, int> mp;
    for (const auto& ai : a) {
        for (int i=1; i*i<=ai; i++) {
            if (ai%i == 0) {
                mp[i] = mp[i]? gcd(mp[i], ai) : ai;
                mp[ai/i] = mp[ai/i]? gcd(mp[ai/i], ai) : ai;
            }
        }
    }

    long ans = 0;
    for (const auto& [i, j] : mp) if (i<=amin && i==j) ans++;
    cout << ans << endl;
}