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

GW初日、いかがお過ごしでしょうか。
本日2019/4/27の21:00から22:40にかけて初コンテストに参加したので、それについて書いていきます。

このnoteは一部問題の解説を含むため、初見で解きたいという方はブラウザバックを推奨します。

AtCoder Beginner Contest 125

A: Biscuit Generator

問題文

ビスケット生産装置を起動すると、起動してから A秒後、2A秒後、3A秒後、...(Aの倍数秒後) に B枚ずつビスケットを生産します。

ビスケット生産装置を起動してから T+0.5秒後までに生産されるビスケットの合計枚数を求めてください。

制約

・入力は全て整数である。
・1≤A,B,T≤20

コード（解答）

#include <iostream>

using namespace std;

int main() {
    int A, B, T;
    cin >> A >> B >> T;

    int counter = 0;
    for (int i = 1; i * A < T + 0.5; i++) {
        counter += B;
    }

    cout << counter << endl;
    return 0;
}

T + 0.5秒後までに生産されるビスケットはA秒 * B回でビスケットの枚数はカウンタで足していってます。
ここは5分ぐらいでパス。簡単でした。

B: Resale

問題文

N個の宝石があり、i番目の宝石の価値は Viです。
あなたはこれらの宝石の中からいくつかを選んで手に入れます。

このとき、1つも選ばなくとも、全て選んでも構いません。ただし、i番目の宝石を手に入れる場合コスト Ciを支払わなければいけません。

手に入れた宝石の価値の合計を X、支払ったコストの合計を Yとします。X−Yの最大値を求めてください。

制約

・入力は全て整数である。
・1≤N≤20
・1≤Ci,Vi≤50

コード（解答）

#include <iostream>

using namespace std;

int main() {
    int N, R = 0;
    cin >> N;
    int V[50], C[50];

    for (int i = 0; i < N; i++) cin >> V[i];
    for (int i = 0; i < N; i++) cin >> C[i];

    int tx;
    for (int i = 0; i < N; i++) {
        tx = V[i] - C[i];
        if (tx > 0) {
            R += tx;
        }
    }

    cout << R << endl;
    return 0;
}

数字がプラス（0より大きい）かったケースのみ加算していきます。
見事にパス、これは全探索ですね。簡単でした。

C: GCD on Blackboard

この問題まで取り組むことができました。解けなかった。

問題文

N個の整数 A1,A2,...,ANが黒板に書かれています。
あなたはこの中から整数を 1つ選んで、1以上 10^9以下の好きな整数に書き換えます。
元の整数と同じ整数に書き換えても構いません。書き換えた後の N個の整数の最大公約数の最大値を求めてください。

制約

入力は全て整数である。
・2≤N≤10^5
・1≤Ai≤10^9

コード（解答）

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int A[100000000];
int limit = 1;
int counter = 0;
 
int euclid(int a, int b) {
    if (a < b) swap(a, b);
 
    if (a % b == 0) {
        return b;
    }
    while (limit > counter) {
        for (int i = a; i > 1; i--) {
            if (b % i == 0) {
                counter++;
                return euclid(b, i);
            }
        }
    }
    return euclid(b, a % b);
}
 
int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    int ans = A[0];
 
    for (int i = 1; i < N; i++) {
        ans = euclid(ans, A[i]);
    }
 
    cout << ans << endl;
    return 0;
}

まずユークリッドの互除法が頭にあったのでそれっぽい実装をしていきました。そこまではいけるかもって感じだったのですが、最大値を形成するために、問題のある箇所をあぶり出す部分を見つけるのが難しかったです。

ユークリッドの互除法 - Wikipedia

結果1回目はこれで提出しました。サンプル入出力が全てパスするといけるかもと思うの良くないですね。

最初の2問は30分もかからずスッとパスしたのですが、ここでハマって4問目にたどり着けなかったです。

解説

Cの解法です pic.twitter.com/isCis7Kjk7

— アルメリア (@armeria_betrue) April 27, 2019

どうやら左右から累積された最大公約数（GCD）を求むると解けるようだ。

すでに詳細の解答や説明を書いている人がいるようなので、そちらに詳細は譲ります。

AtCoder ABC 125 C - GCD on Blackboard (300 点) - けんちょんの競プロ精進記録

最大公約数のことをgcdと呼ぶことさえ知らないレベルなので、結構勉強になった。

D: Flipping Signs

未着手。
解いたら解説を別の記事で書きます。

初コンテスト

初コンテスト、難しかったです。
19新卒が今回のコンテストを全完したようで身が引き締まりますね。

継続してアルゴリズムの学習をしつつレートをあげようと思います。
今回の結果は以下へ貼っておきます。

All Submissions - AtCoder Beginner Contest 125