Arc's Laboratory

プログラミングとかの研究室

AtCoder Beginner Contest (ABC) 106 を解いてみた

AtCoder Beginner Contest (ABC) 106 の解法ログです。

問題文はAtCoder公式からどうぞ。

注:ソースコードの変数と解法中の文字は無関係です

A - Garden

解法

算数の問題にこういうのありましたね。道の重なりに注意。

ソースコード

int main(void) {
    int a, b;
    cin >> a >> b;
    cout << a * b - a - b + 1 << endl;

    return 0;
}

B - 105

解法

Nが小さいので、N以下の数で割ったあまりを全て見ていけばOK。

余り0になる場合が8つあるなら、その数は約数を8個持つ。

ソースコード

int main(void) {
    int n;
    cin >> n;
    int result = 0;
    for (int i = 1; i <= n; i += 2) {
        int count = 0;
        for (int j = 1; j <= i; j++) {
            if (i % j == 0)
                count++;
        }
        if (count == 8)
            result++;
    }

    cout << result << endl;

    return 0;
}

C - To Infinity

解法

1<=n<=K文字目に1以外の文字が存在する場合、5000兆日経つと、たとえK=10^18でも1以外の文字がKの場所に到達する(指数関数は一瞬で膨れ上がるので)。

そうでない場合は5000兆日経ってもK文字目は1のまま。

K文字目まで1が続くのなら1を、そうでないなら最初に出現した1以外の文字を出力する。

ソースコード

int main(void) {
    std::string s;
    int64_t k;
    cin >> s;
    cin >> k;
    for (int i = 0; i < k; i++) {
        if (s[i] != '1') {
            cout << s[i] << endl;
            return 0;
        }
    }
    cout << '1' << endl;

    return 0;
}

D - AtCoder Express 2

解法

愚直に解く場合、『クエリ(p,q)に対して、「全列車に対しp<=L,R<=qであるかを調べる」』という解法を思いつける。計算量はO(Q*M)なので間に合わない。

都市の数が少ないことに着目すると、train[L][R]=LからRに向かう電車の数という配列を作ることができそう。この配列を利用して「p<=L,R<=qを満たす場所を足していく」という解法を思いつける。計算量はO(QN^2)。……計算量増えてるじゃーん!!

しかし、「p<=L,R<=qを満たす場所を足していく」処理は累積和を利用することでO(N)に落とせる。ということで、先程の配列から累積和を作ってクエリに答えればAC。

ソースコード

(printf/scanfで書いてます)

int main(void) {

    int n, m, q;
    cin >> n >> m >> q;
    int train[501][501] = {};
    int cum[501][501]   = {};

    int m1, m2;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &m1, &m2);
        train[m1][m2]++;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cum[i][j] = cum[i][j - 1] + train[i][j];
        }
    }

    int a, b;
    int answer;
    for (int i = 0; i < q; i++) {
        answer = 0;
        scanf("%d%d", &a, &b);
        for (int j = a; j <= b; j++) {
            answer += cum[j][b];
        }
        printf("%d\n", answer);
    }

    return 0;
}

その他

37分全完やったぜ。