スコルの知恵袋

主にプログラミング関係の気になったこと等をまとめたブログ

AtCoder Beginner Contest 174 感想

競プロ日記 競プロ

atcoder.jp

ABCEの4完。

Cで時間をかけてしまい、そこから調子が狂って破滅しました......。

晩御飯をコンテスト直前に食べるのは良くなかった（負け惜しみ）。

A - Air Conditioner

提出コード

リンク： https://atcoder.jp/contests/abc174/submissions/15589788

void solve() {
    ll N;
    cin >> N;
    bool ok = N >= 30;
    cout << (ok ? "Yes\n" : "No\n");
}

B - Distance

念のため、 \sqrt{p^2 + q^2} \le D + 10^{-9} で判定した。

提出コード

リンク：https://atcoder.jp/contests/abc174/submissions/15598123

void solve() {
    ll N;
    cin >> N;
    double D;
    cin >> D;
    ll cnt = 0;
    for (ll i = 0; i < N; i++) {
        double x, y;
        cin >> x >> y;
        double d = sqrt(x * x + y * y);
        if (d <= D + 1e-9) {
            ++cnt;
        }
    }
    prints()(cnt);
}

C - Repsept

めっちゃ時間かかった......。

i 番目の数を a_{i} とすると (0-indexed)

\displaystyle{ a_{i} = 7 \times \sum_{j = 0}^{i} 10^j = 7 \times \frac{10^{i+1}-1}{10-1} }

だから、 a_{i} \bmod K には周期性がある。なので、 i = 1 から順番に調べていき、もし、 a_{i} \equiv 0 となる前に 前に登場した値になったら -1 を出力する。周期は長くても K なので計算量は大丈夫。

はじめに、この前のこどふぉの問題に引っ張られて式変形を試みて時間をかなり消費したのがダメだった。

提出コード

リンク：https://atcoder.jp/contests/abc174/submissions/15618564

void solve() {
    ll K;
    cin >> K;
    bool ok = true;
    ll cur = 7 % K;
    ll base = 1;
    ll ans = 1;
    set<ll> st;
    while (true) {
        if (cur == 0) {
            break;
        }
        if (st.find(cur) != st.end()) {
            ok = false;
            break;
        }
        st.emplace(cur);
        base *= 10;
        base %= K;
        cur = (cur + 7 * base) % K;
        ++ans;
    }
    if (ok) {
        prints()(ans);
    }
    else {
        prints()(-1);
    }
}

D - Alter Altar

解けなかった。

「この問題、超むずかしいですよねぇ！？ねぇ！！？」と聞きまくって共感を得まくりたいところだけど、 順位表を見るとどうやらそう思っているのは僕だけらしい。え、マジ？？

ちなみに、まだ解けていません。解説PDFは死んでも見たくない......。

[追記]

解けました。セーフ！（アウト）

WW...WRR...R となっている塊（ダメ塊と呼ぶ）がなくなるように操作すればいい。 ここでよく考えると、入れ替える操作はダメ塊の構成要素を少なくとも1つ以上消せるのに対し、色を変える操作は1つしか消すことができない。 また、色を変える操作によって消せる要素は入れ替える操作でも消せる。なので、色を変える操作は必要ない！

入れ替える操作だけでいいなら最終形態は確定して、RR..RWW..W のようになればいい。 最小の操作回数でこの形態にするためには、 S の両端から見て行ってこの形態に違反している要素同士を swap すればいい。

コンテスト後提出コード

リンク：https://atcoder.jp/contests/abc174/submissions/15646447

void solve() {
    ll N;
    cin >> N;
    string S;
    cin >> S;
    ll cnt = 0;
    ll left = 0, right = N - 1;
    while (left < right) {
        while (left < N && S[left] != 'W') ++left;
        while (right >= 0 && S[right] != 'R') --right;
        if (left < right) {
            ++cnt;
            ++left;
            --right;
        }
    }
    prints()(cnt);
}

E - Logs

Dがさっぱりだったので、終了20分前にDを飛ばしてEを解き始めた。このムーブのおかげで何とか緑パフォを出す損害に抑えられた。

はじめに、焦りすぎて K の制約を見ずに priority_queue を使って大きいものから分割数を増やしていく解答を投げて1回 TLE を食らったものの、 その後すぐに二分探索が見えたので助かった。

Dの方が998244353倍むずかしいです。

提出コード

リンク：https://atcoder.jp/contests/abc174/submissions/15638921

void solve() {
    ll N, K;
    cin >> N >> K;
    Vl A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
    ll left = 0, right = 1001001001ll;
    while (right - left > 1) {
        ll mid = (left + right) >> 1;
        ll cnt = 0;
        for (ll i = 0; i < N; i++) {
            ll x = (A[i] + mid - 1) / mid;
            cnt += x - 1;
        }
        if (cnt <= K) {
            right = mid;
        }
        else {
            left = mid;
        }
    }
    prints()(right);
}

F - Range Set Query

読めてない。しかし、僕がかつてライバルだと思っていた人たちはみんなこれを解いている。すげぇ。

今では彼らは雲の上の存在です。

[追記]

考えても分からなかったので「区間　種類数」と検索したら答えが出てきた。草。

Twitter が騒がしかったのはこれか、笑。これは検索力もくそもないので、お気持ち表明する人が出てくるのもまぁ仕方ない。

検索して出てきたアルゴリズムを書くとACを得た。色の所有権を管理していく感じだね。

「クエリは別に順番通りに処理しなくてもいいよ！」というのは持っておくべき考え。

コンテスト後提出コード

リンク：https://atcoder.jp/contests/abc174/submissions/15648146

template <typename T>
class BIT {
private:
    int n;
    std::vector<T> vec;
 
public:
    BIT(int n) : n(n), vec(n + 1) {}
    // i 番目の要素に a を足す
    void add(int i, const T& a) {
        for (++i; i <= n; i += i & (-i)) {
            vec[i] += a;
        }
    }
    // 区間[0, i)に対するクエリを実行する
    T query(int i) const {
        T res = 0;
        for (; i >= 1; i -= i & (-i)) {
            res += vec[i];
        }
        return res;
    }
    // 区間[i, j)に対するクエリを実行する
    T query(int i, int j) const {
        return query(j) - query(i);
    }
    size_t size() const noexcept {
        return n;
    }
    void reset() noexcept {
        std::fill(vec.begin(), vec.end(), static_cast<T>(0));
    }
};
 
void solve() {
    ll N, Q;
    cin >> N >> Q;
    Vl C(N);
    for (ll i = 0; i < N; i++) {
        cin >> C[i];
        --C[i];
    }
    using Tup = tuple<ll, ll, ll>;
    vector<Tup> queries(Q);
    for (ll i = 0; i < Q; i++) {
        ll a, b;
        cin >> a >> b;
        --a;
        queries[i] = {b, a, i};  // 左右逆
    }
    sort(queries.begin(), queries.end());
    BIT<ll> bb(N);
    Vl la(N, -1);
    ll cur = 0;
    Vl ans(Q);
    for (ll i = 0; i < Q; i++) {
        auto [right, left, idx] = queries[i];
        while (cur < right) {
            if (la[C[cur]] != -1) {
                bb.add(la[C[cur]], -1);
            }
            la[C[cur]] = cur;
            bb.add(cur, 1);
            ++cur;
        }
        ans[idx] = bb.query(left, right);
    }
 
    for (ll i = 0; i < Q; i++) {
        prints()(ans[i]);
    }
}