#1 - 文系出身エンジニアが競プロをやる

こんばんは。前回から時間が経ってしまいました。
あまり時間が取れなかったのですが、毎日1問ずつAtCoderで問題を解くのを目標に仕事が終わってからPCと向き合っていました。

実際にはBeginnersSelectionに記載されている問題を1問を残して全て解いています。
どうせなので記録に残そうと思ってGitHubへソースコードをPushしていってます。その時一番良いコードを書くことを心がけていますが、翌日見直すとクソコードだったりします。尚、コードに対してアドバイスがあったら是非ください。

paveg/programming_contest

ABC081B - Shift only

黒板にN個の正の整数A1,...,Anが書かれています.
すぬけ君は、黒板に書かれている整数がすべて偶数であるとき、次の操作を行うことができます.
・黒板に書かれている整数すべてを、2で割ったものに置き換える
すぬけ君は最大で何回操作を行うことができるかを求めてください.

制約
・1 ≦N≦200
・1≦Ai≦10^9
入力
・N
・A1 A2 ... An

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int size;
    int iterator;
    bool result = true;
    cin >> size;

    vector<int> data(size);

    for (int iterator = 0; iterator < size; iterator++) {
        cin >> data[iterator];
    }
    while (result) {
        for (int iterator = 0; iterator < data.size(); iterator++) {
            if (data[iterator] % 2 != 0) {
                result = false;
            }
            data[iterator] /= 2;
        }
        if (result) {
            counter++;
        }
    }

    cout << counter;
    return 0;
}

コピペがうまく行かないので次から問題文は書きません…
偶数かどうかをチェックして、操作を行うかを判別するものですね。商を確認して偶数かを変別し処理を行います。

ABC087B - Coins

#include <iostream>

using namespace std;

int main() {
    int a, b, c, x;
    int sum;
    int counter = 0;

    cin >> a >> b >> c;
    cin >> x;

    for (int i = 0; i <= a; i++) {
        for (int j = 0; j <= b; j++) {
            for (int k = 0; k <= c; k++) {
                sum = ((500 * i) + (100 * j) + (50 * k));
                if (x == sum) {
                    counter++;
                }
            }
        }
    }

    cout << counter;
    return 0;
}

これは普通に全探索で解きました。力技なので、効率が悪い。

ABC083B - Some Sums

1以上N以下の整数のうち、10進法での各桁の和がA以上B以下であるものの総和を求めてください。

#include <iostream>

using namespace std;

int main() {
    int n, a, b;
    int x = 0;
    cin >> n >> a >> b;

    for (int i = 1; i <= n; i++) {
        int num = i, sum = 0, dig;
        while (num) {
            dig = num % 10;
            sum = sum + dig;
            num /= 10;
        }
        if (a <= sum && sum <= b) {
            x += i;
        }
    }

    cout << x;
    return 0;
}

1からnまでの数に対して各桁の和を合算する処理を繰り返していきます。各桁の和は、以下のコードを繰り返してあげれば良いはずです。

dig = num % 10;
sum = sum + dig;
num /= 10;

ABC088B - Card Game for Two

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, alice = 0, bob = 0;
    scanf("%d", &n);
    vector<int> cards(n);

    for (int i = 0; i < n; i++) {
        scanf("%d", &cards[i]);
    }
    sort(cards.begin(), cards.end(), greater<int>());
    for (int i = 0; i <= cards.size(); i++) {
        int point = cards[i];
        if (i % 2 == 0) {
            alice += point;
        } else {
            bob += point;
        }
    }

    int result = alice - bob;
    cout << result;
    return 0;
}

ここではなぜか、Cのキー入力 `scanf` を使っていますが、なんとなくなので気にしないでください。標準入力ストリームの便利さを改めて知りました。変数の型認識が自動でされるの便利ですね。
問題はaliceとbobの点数の差分をコードで表現するってやつです。
ちなみに戦略が最適化されているので、先行が絶対勝つクソゲーでした。

少し記事が長くなりすぎたので、一旦ここで切ります。
続いて#2を投稿しようと思います。b問題までは、しっかり頭使えば解ける問題が多い気がしますが、アルゴリズムに頼って楽をすべきだなあという印象が強くなってきたので、アルゴリズムの教本を買おうと思います（蟻本はちょっと難しそうだったので後回しにしました）。