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

AtCoder Beginner Contest (ABC) 105の解法をまとめてみます。今回はD問題が詳しめです。

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

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

A - AtCoder Crackers

解法

なるべく公平に配るなら、

• N%K==0のとき 差は0
• N%K!=0のとき 差は1

になる。

ソースコード

int main(void) {
    int n,k;
    cin>>n>>k;
    if(n%k==0){
        cout<<"0"<<endl;
    }else{
        cout<<"1"<<endl;
    }
 
    return 0;
}

B - Cakes and Donuts

解法

7ドルのドーナツを買う→残額が4で割り切れるならtrue、割り切れないならドーナツをもう一つ→……というふうにやっていく。

一応4ドルのケーキを買った後で判定する処理も書いたけど無駄だった。

ところでArcとかいう人はこの問題で2WAも出しているそうですよ。酷いですね。

ソースコード

int main(void) {
    int n;
    cin >> n;
    bool can_buy = false;
    if (n % 7 == 0 || n % 4 == 0) {
        can_buy = true;
    } else {
        for (int i = 0; i <= n; i += 7) {
            if ((n - i) % 4 == 0) {
                can_buy = true;
                break;
            }
        }
        for (int i = 0; i <= n; i += 4) {
            if ((n - i) % 7 == 0) {
                can_buy = true;
                break;
            }
        }
    }
 
    if (can_buy)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
 
    return 0;
}

C - Base -2 Number

解法

10進数nを普通の2進数に変換する際の処理を考えてみると、

nが0になるまで{

(a-1ビットで表現できる最大の数)<nを満たすような最大のaを探す
2進数a桁目にフラグを立てる
n-=2^(a-1)

}を繰り返す

と言う風になる。これを応用して、

nが0になるまで{

n<(a-1ビットで表現できる最小の数)か(a-1ビットで表現できる最大の数)<nを満たすような最大のaを探す
-2進数a桁目にフラグを立てる
n-=(-2)^(a-1)

}を繰り返す

という処理を作ってみる。

ソースコード

const long long MAX_N = 1000000000;
const long long MIN_N = -1000000000;
 
int main(void) {
    int n;
    cin >> n;
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }
 
    bool is_on[101] = {};
    std::vector<long long> max;
    std::vector<long long> min;
 
    // max,minを計算
    //max[a]=(aBitで表現できる最大値)
    max.push_back(0);
    min.push_back(0);
    long long add = 1;
    int count     = 0;
    while (1) {
        count++;
        if (count % 2 == 1) {
            max.push_back(max[count - 1] + add);
            min.push_back(min[count - 1]);
        } else {
            max.push_back(max[count - 1]);
            min.push_back(min[count - 1] + add);
        }
        if (max[count] >= MAX_N && min[count] <= MIN_N)
            break;
        add *= -2;
    }
 
    int top_digit = 0;
    while (n != 0) {
        if (n > 0) {
            int digit = 1;
            while (max[digit] < n) {
                digit++;
            }
            is_on[digit] = true;
            if (top_digit == 0)
                top_digit = digit;
            n -= std::pow(-2, digit - 1);
        } else {
            int digit = 1;
            while (min[digit] > n) {
                digit++;
            }
            is_on[digit] = true;
            if (top_digit == 0)
                top_digit = digit;
            n -= std::pow(-2, digit - 1);
        }
    }
 
 
    for (int i = top_digit; i >= 1; i--) {
        if (is_on[i])
            cout << 1;
        else
            cout << 0;
    }
    cout << endl;
 
    return 0;
}

D - Candy Distribution

解法

累積和を計算した後、累積和のそれぞれの項に対してMで割った余りを計算。 Mで割った余りがiであるような項がn個あるなら、それらの項から2つを選択すると条件を満たす和が得られる。個数はn C 2。これをそれぞれのiに対して計算することで答えが得られる。

実装

実装がきつかったので詳しめに書いてみる。

「余りがiであるような項の個数」をどう保持するか?

余りのパターンはM通り存在するから、配列を用意するとメモリが足りない。

公式PDFにもある通り、std::map系のコンテナを利用することになる。今回の実装はstd::multimapを利用している。キーを余り、値を累積和の項にして、count(i)で個数を取得する作戦。なおmap系を利用するのは今回が初めてな模様。

イテレータを最初から最後まで回して、前に見たキーと別のキーが出現したら計算用関数を呼び出す事にした(キーが順番通りに出現する必要があるのでunordered_multimapは使えない)。

unorderedの実装ってどうやるんでしょうね……。

組み合わせの数n C 2をどう計算するか?

ソースコードでコメントアウトした関数のように、階乗を利用して計算するとlong longでもオーバーフローしてREを吐く。階乗をなめたらいけない。

結局「n!を少しずつ計算→途中で(n-2)!か2!の因数で約分できそうだったら約分」というクッッッッソ醜いやり方で押し通した。

……と、ここまで書いたが実は全て罠。n C 2なら普通に(n-1)+(n-2)+...+2+1を計算するだけで済む。

これに気づいたのはACした後の話でしたとさ。

コンパイラによって異なる言語実装

GCC5.4.1、ローカル環境のClang(clang-902.0.39.2)だと、ローカル変数宣言時に自動で0初期化が行われる。

Clang 3.8.0だと初期化が行われないらしく、結果「ClangでコンパイルするとWAになる」という現象が発生していた。

とりあえず明示的にint hoge=0としておいた方が精神衛生上よろしいかも。

ソースコード

/*
long long factorial(long long n) {
    long long result = 1;
    for (long long i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}
 
long long combination(long long n, long long r) {
    long long result = factorial(n) / factorial(n - r) / factorial(r);
    return result;
}
*/
 
long long combination_improved(long long n, long long r) {
    long long d      = n - r;
    long long result = 1;
    while (n > 1 || d > 1 || r > 1) {
        if (n > 1) {
            result *= n;
            n--;
        }
        if (d > 1 && result % d == 0) {
            result /= d;
            d--;
        }
        if (r > 1 && result % r == 0) {
            result /= r;
            r--;
        }
    }
    return result;
}
 
int main(void) {
    long long n, m;
    long long count;//Clangだと初期化の必要あり
    long long cum[100001];
    std::multimap<long long, long long> mod_map; //(mod M,number)
    cin >> n >> m;
    long long m1;
    for (int i = 0; i < n; i++) {
        cin >> m1;
        if (i == 0)
            cum[i] = m1;
        else
            cum[i] = cum[i - 1] + m1;
    }
    for (int i = 0; i < n; i++) {
        mod_map.insert(std::make_pair(cum[i] % m, cum[i]));
    }
 
    int prev = m;
    for (auto itr : mod_map) {
        if (prev != itr.first) {
            if (itr.first == 0) {
                if (mod_map.count(0) >= 1)
                    count += combination_improved(mod_map.count(0) + 1, 2);
            } else {
                if (mod_map.count(itr.first) >= 2) {
                    count += combination_improved(mod_map.count(itr.first), 2);
                }
            }
        }
        prev = itr.first;
    }
 
    cout << count << endl;
 
    return 0;
}

おまけ

ABC105-D AC!!
やっと通ったああああ(画像はこれまで積み上げてきた屍の山です) pic.twitter.com/1ui6LwKflJ

— ｱｰｸ@std::mapを使え (@arcslab123) August 12, 2018

散っていったコードに敬意を。(?????)