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

funai(pav)

2019年5月3日 19:36

お久しぶりです。
実家に帰省して、堕落を極めていた結果投稿がおろそかになっていました。

令和も何卒よろしくお願いします。

投稿はおろそかになっていたものの、AOJやAtCoderの問題は解いていたので内容には困らないと思います。
1月毎の振り返りは、ブログにでも書こうと思ってます。
2019/4/7にスタート始めたので来週末ぐらいかな。

さて、それではいつもの通り進めていきます。

今回取り組んだのは以下です。
そして本記事より、問題文はサイト先へ譲ることにしてコードの説明と補足だけ書いていきます。

・AtCoder Beginner Contest 124
・A
・B
・C
・AOJ
・LinerSearch
・BinarySearch

A - Buttons

問題

解答（コード）

#include <iostream>

#define rep(i, N) for (LL i = 0; i < N; ++i)
typedef long long int LL;

using namespace std;

int main() {
    LL A, B;
    LL limit = 2;
    cin >> A >> B;
    LL ans = 0;
    rep(i, limit) ans += (A > B) ? A-- : B--;

    cout << ans << endl;
    return 0;
}

ボタンを押すと渡されたA,Bのどちらかの数だけコインを取得でき、押した方のボタンの値が1小さくなるそうです。
AかBか比較して大きい方を加算した後に数値を1小さくしてあげる処理を実装するだけです。A問題は簡単ですね。

B - Great Ocean View

問題

解答（コード）

#include <iostream>
 
#define rep(i, N) for (LL i = 0; i < N; ++i)
typedef long long int LL;
 
using namespace std;
 
int main() {
    LL N, H[100], r = 1;
    cin >> N;
    rep(i, N) cin >> H[i];
    for (LL i = 1; i < N; ++i) {
        bool check = true;
        if (H[i] < H[0]) check = false;
        for (LL j = 0; j < i; j++) {
            if (H[i] < H[j]) {
                check = false;
            }
        }
        if (check) r++;
    }
 
    cout << r << endl;
    return 0;
}

前提として、自分より高い旅館が存在すると海が見えない。
この前提を置いた上で海が見える旅館の数を数え上げるアルゴリズムを実装するものです。
一番最初の旅館は絶対海を見ることが可能なので、答えは1以上N以下となります。
先頭の旅館と比較した後後続の旅館と比較しています。
と思ったけど j =0になってますね… j=1で良さそう。

とりあえずパス。（記事を書きながら最終的に下記のように修正）

#include <iostream>
#include <vector>
 
#define rep(i, N) for (LL i = 0; i < N; ++i)
typedef long long int LL;
 
using namespace std;
 
int main() {
    LL N, r = 0;
    vector<LL> H(100);
    cin >> N;
    rep(i, N) cin >> H[i];
    for (LL i = 0; i < N; ++i) {
        bool check = true;
        for (LL j = 0; j < i; ++j) {
            if (H[i] < H[j]) {
                check = false;
              	break;
            }
        }
        if (check) r++;
    }
 
    cout << r << endl;
    return 0;

なんか無駄な書き方してましたね、日が空いて何考えてたか思い出せない…

C - Coloring Colorfully

問題

コード（解答）

#include <iostream>
#include <cstring>
 
#define rep(i, N) for (LL i = 0; i < N; ++i)
typedef long long int LL;
 
using namespace std;
 
int main() {
    LL c = 0;
    string S;
    cin >> S;
 
    for (LL i = 1; i < S.length(); ++i) {
        if (S[i] == S[i - 1]) {
            S[i] = (S[i] == '0') ? '1' : '0';
            ++c;
        }
    }
    
    cout << c << endl;
    return 0;
}

0と1で作られたn字の文字列が与えられるので、交互になるように並び替えてその最小の並び替え回数を出力する。

なので1からループ処理を行い、現在の文字と1つ前の文字が一緒だったら今の文字を置き換える処理を行います。
公式の解答だと、どうやら01 or 10の開始点を調べてそこと違う部分の数を数える感じですかね。

計算量は `O(|S|)` とのことでした。

解説

AtCoder公式？の解説を一応置いておきます。

ALDS1_4_A - Linear Search

問題

解答（コード）

#include <cstdio>
#include <vector>

#define rep(i, N) for (int i = 0; i < N; ++i)

using namespace std;

bool linerSearch(vector<int> vec, int key) {
    rep(i, vec.size()) if (vec[i] == key) return true;
    return false;
}

int main() {
    int n, q, key;
    scanf("%d", &n);
    vector<int> S(n);
    rep(i, n) scanf("%d", &S[i]);

    int ans = 0;
    scanf("%d", &q);
    for (int i = 0; i < q; ++i) {
        scanf("%d", &key);
        if (linerSearch(S, key)) ++ans;
    }

    printf("%d\n", ans);
    return 0;
}

線形探索を実装して、それで探索を行います。（C++11）
与えられた配列Sに存在しうるkeyの数を数え上げます。

線形探索は O(n)のアルゴリズムですが、番兵を使った実装は定数倍の高速化が見込まれ、大きなデータに対して効果が期待できます。

ALDS1_4_B - Binary Search

問題

解答（コード）

#include <cstdio>

#define rep(i, N) for (int i = 0; i < N; ++i)

bool binarySearch(int A[], int l, int r, int key) {
    while (l < r) {
        int m = (l + r) / 2;
        if (key == A[m]) return true;
        if (key > A[m]) l = m + 1;
        else if (key < A[m]) r = m;
    }
    return false;
}

int main() {
    int n, q;
    scanf("%d", &n);
    int left = 0, right = n, sum = 0;
    int S[n];
    rep(i, n) scanf("%d", &S[i]);

    scanf("%d", &q);
    int T[q];
    rep(i, q) scanf("%d", &T[i]);
    for (int &key: T) {
        if (binarySearch(S, left, right, key)) sum++;
    }

    printf("%d\n", sum);
    return 0;
}

バイナリサーチの実装です。

バイナリサーチとは、ソート済みのデータあるいは配列への検索の際に中央の値を見て大小関係を判断し、検索範囲を狭めていく探索アルゴリズムのことです。

n個のデータがある場合、時間計算量はO(log 2 n)

おわりに

今回は有名な探索アルゴリズムが2つでてきました。
これらの時間計算量は頭に入れておくと良さそうです。
要素数をnとした時の計算量は以下の通りです。

・線形探索（Linear Search） - O(n)
・二分探索（Binary Search） - O(log ₂ n)

はしがきですが、コッホ曲線の計算の時に三平方の定理が一切出てこなかったので中学と高校数学を学び直す必要性を強く感じました。

なので…書いました。頑張ります。

面白ければシェアをお願いします！ twitterのフォローとブログの購読も！ blog: www.pavlog.tokyo twitter: https://twitter.com/_pavlog