Mister雑記

競プロやります。

ABC106 解説

D問題、大罪を犯す。

目次

A. Garden

概要

東西 Aヤード、南北 Bヤードの長方形をした土地がある。

この土地に、東西方向と南北方向にそれぞれ幅1ヤードの道を土地の端から端まで引く。

このとき、道に含まれない土地の面積を求めよ。

制約

  •  2 \leq A, B \leq 100

解説

小学校の算数で見たことがある人も多いであろう定番問題。道をそれぞれ端っこに平行移動させれば (A - 1)(B - 1)平方ヤードになることが分かるので、それを出力すればいい。

実装例

#include <iostream>
using namespace std;

int main() {
    int A, B;
    cin >> A >> B;
    cout << (A - 1) * (B - 1) << endl;
    return 0;
}

ところでヤード・ポンド法は滅ぶべし。

B. 105

概要

1以上 N以下の奇数で、正の約数をちょうど8個含むものの個数を求めよ。

制約

  •  1 \leq N \leq 200

解説

素因数分解とか難しいことを考えなくても、制約が緩いので2重ループで約数をカウントするだけでいい。誤読に少し注意。

実装例

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;
    
    int ans = 0;
    
    // 対象が奇数のみなのでステップ数は2
    for (int i = 1; i <= N; i += 2) {
        int cnt = 0;
        // 正の約数カウンタ
        
        for (int j = 1; j <= i; ++j) {
            if (i % j == 0) ++cnt;
        }
        
        if (cnt == 8) ++ans;
    }
    
    cout << ans << endl;
    return 0;
}

ちなみに N = 200での該当例は以下の通り。意外と多い。

105
135
165
189
195

C. To Infinity

概要

数字のみからなる文字列 Sが与えられる。この文字列は1日ごとに「各数字がその数字の数だけ増える」という風に成長する。

たとえば、1234は以下のように成長する。

1234 -> 1223334444 -> 122223333333334444444444444444 -> ...

このとき、5000兆日経った時点での K文字目の数字を求めよ。

制約

  •  1 \leq |S| \leq 100
  •  1 \leq K \leq 10^{18}
  • 5000兆日後に文字列長が K以上になっていることが保証されている。

解説

1日経つと、数字 N N個に増殖する。さらにもう1日経つと、 N個の Nが全て N個に増殖するので、 Nの個数は N^2個になる。そんなわけで、数字 N D日後には N^D個に増殖している。

言わずもがな、2の5000兆乗は 10^{18}の比ではない大きさである1

したがって、1は増殖しないが2以上の数は全て K個以上に増殖する。ここから「一番最初に出てくる1以外の数が答え」と分かる。

しかしこれではケース漏れがある。それが「最初から1が K個以上連続している」ケースである。この場合は1が答えなので、実際は頭から K文字までのみを見ればいい。

実装例

#include <iostream>
#include <string>
using namespace std;
using ll = long long;

int main() {
    string S;
    ll K;
    cin >> S >> K;
    
    // K文字目までをチェック
    for (ll i = 0; i < K; ++i) {
        if (S[i] != '1') {
            // 1以外が出たら答え
            cout << S[i] << endl;
            return 0;
        }
    }
    
    // K文字目まで全部1 -> 1が答え
    cout << 1 << endl;
    return 0;
}

D. AtCoder Express 2

概要

直線上に並んだ N個の駅からなる路線があり、 M本の列車が走っている。列車 iは駅 L_iから R_iの間を走っている。

ここで2つの整数 p_j, q_jからなっている Q個のクエリが与えられる。各クエリについて、走行区間 [ p_j, q_j ]に完全に含まれている列車の本数を答えよ。言い換えれば、「 p_j \leq L_iかつ R_i \leq q_j」を満たす iの個数を答えよ。

制約

  •  1 \leq N \leq 500
  •  1 \leq M \leq 2 \times 10^5
  •  1 \leq Q \leq 10^5
  •  1 \leq p_i \leq q_i \leq N  (1 \leq i \leq M)
  •  1 \leq L_j \leq R_j \leq N  (1 \leq j \leq Q)

解説

各クエリについて列車 N本の区間を調べていると計算量は O(MQ)でとてもじゃないので間に合わない。よって前計算をする必要がある。

まず考えられるのは、予め全区間について完全に走行区間が含まれる列車の本数を求めることである。しかし区間の総数が N^2であることから計算量は O(MN^2)で、これでも間に合わない2

そこで、ひとまず区間の始点についてのみ考えることにする。 (p, q)のクエリには L_i \geq pなる iしか考えなくていい(これを満たさなければ完全に含まれることはない)ので、例えばdp[p]を「 L_i \geq pなる iについて R_iからなる配列」とかすれば、dp[p]q以下の成分の個数を数えればいい。

これを高速で実現できるのがBIT(Binary Indexed Tree)というデータ構造。各始点についてBITを構築するのに O(MN \log N)、各クエリに答えるのに O(\log N)で全体の計算量は O(MN \log N + Q \log N)。際どいが、C++なら辛うじて通る。

実装例

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

class BIT {
public:
    // 要素数N、値vで初期化
    BIT(ll N, ll v) : V_NUM(N) {
        data.resize(N);
        fill(data.begin(), data.end(), v);
    }

    // [1, i]の総和を求める
    ll query(ll i) {
        ll ret = 0;
        while (i > 0) {
            ret += data[i];
            i -= (i & -i);
        }
        return ret;
    }

    // data[i]にv可算
    void update(ll i, ll v) {
        while (i < V_NUM) {
            data[i] += v;
            i += (i & -i);
        }
    }

    ll V_NUM;
    vector<ll> data;
};

int main() {
    ll N, M, Q;
    cin >> N >> M >> Q;
    
    // 各始点についてBITを構築
    vector<BIT> bit(N + 1, BIT(N + 1, 0));

    for (ll i = 0; i < M; ++i) {
        ll L, R;
        cin >> L >> R;
        for (ll j = 1; j <= L; ++j) {
            // 始点がL以下の区間にRを追加
            bit[j].update(R, 1);
        }
    }

    for (ll i = 0; i < Q; ++i) {
        ll p, q;
        cin >> p >> q;
        
        // 始点がpより後の区間で、終点がqより前の区間の数
        cout << bit[p].query(q) << endl;
    }
    
    return 0;
}

正直BITはD問題としては高度すぎる技術だが、解ければいいのだ。

感想

A~Cの難易度は最近の中では随分とマシな方だったが、その分Dが難しめ。

Dは Nの制約的に正直通るとは思っていなかった。模範解答の方を思い付けるようにならないとまだまだという感じ。


  1.  2^{10} \sim 10^3を使うと、100日時点で十分だと分かる。ちなみに 2^{5 \times 10^{15}} \sim 10^{15 \times 10^{14}}となる。

  2. と言っているが、imos法を使えば余裕で構築できてしまう。そっちが模範解答。