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

※このマガジンは不定期投稿です。

Intro

ちわ、今日も競プロをやっていきます。
本日解いた問題は、AtCoder Beginner Contest 121のA-C問題です。
AとBは難しくないので、コードだけぺっと貼って進めます。

A - White Cells

提出

問題概要

A - White Cells

行と列の数値が2回与えられます。1回目はマス目の大きさで、2回目は塗りつぶす範囲です。塗られなかったサイズを答えなさい。

解答（コード）

#include <cstdio>
 
using namespace std;
 
typedef long long int ll;
#define REP(i, I, N) for (int i = I; i < N; ++i)
#define rep(i, N) REP(i, 0, N)
 
int main() {
    int H, W, h, w;
    scanf("%d %d", &H, &W);
    scanf("%d %d", &h, &w);
 
    printf("%d\n", (H - h) * (W - w));
    return 0;
}

・H行W列がマス目の範囲
・h行w列が塗りつぶす範囲
上記のように考えると、塗られていないマス目のサイズは
(H-h) * (W-w)で求められるはず。求め方はわかったけどなんか公式とかあるのかな、言語化できなかったので知識がないですね。

ACだったので、進めます。

B - Can you solve this?

提出

問題概要

B - Can you solve this?

M個の整数で表されるN個のソースコード（ソースコードというか引数？）と整数B1,B2,...,BM、そして整数Cが与えられるので、以下の式が成立するのを数え上げなさい。

Ai1B1+Ai2B2+...+AiMBM+C>0

解答（コード）

#include <iostream>

using namespace std;

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

int main() {
    int N, M, C;
    cin >> N >> M >> C;
    int B[M], l;
    rep(i, M) {
        cin >> l;
        B[i] = l;
    }

    int ans = 0;
    int amount = 0;
    rep(i, N) {
        int A;
        rep(j, M) {
            cin >> A;
            amount += A * B[j];
        }
        if (amount + C > 0) ans++;
        amount = 0;
    }

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

O(NM)ですかね、計算量は…。
(amount +C) > 0となるものだけを数え上げます。
つまり、 Ai1B1+Ai2B2+...+AiMBM+C>0が成立してるかどうかを最後に確認してます。これも難なくAC。

C - Energy Drink Collector

提出（TLE）

問題概要

C - Energy Drink Collector

栄養ドリンクにレーティング上昇効果がある（すげえな）らしく、登場人物の高橋くんはこれにあやかろうとしてM本購入しようと考えたようです。
魔法の栄養ドリンクの売り先はN軒存在しており、i軒目の店では1本Ai円の栄養ドリンクをBi本まで購入可能とのこと。その際、M本購入するまでの最小必要金額を求めなさいとのこと。

普段はプロテインとBCAAとグルタミンとクレアチンしか飲んでいない俺ですが、普通にこの栄養ドリンクは飲みたいです。糖質高いのかな？

解答（コード） - 1回目 TLE

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
typedef long long int ll;
#define REP(i, I, N) for (ll i = I; i < N; ++i)
#define rep(i, N) REP(i, 0, N)
 
struct shop {
    ll price;
    ll stock;
 
    bool operator<(const shop &another) const {
        return price < another.price;
    }
};
 
int main() {
    ll N, M;
    cin >> N >> M;
    vector<shop> S(N);
 
    ll A, B;
    rep(i, N) {
        cin >> A >> B;
        S[i].price = A;
        S[i].stock = B;
    }
    sort(S.begin(), S.end());
 
    ll ans = 0;
    ll bought = 0;
    while (bought != M) {
        shop s = S[0];
        while (s.stock > 0) {
            ans += s.price;
            s.stock--;
            bought++;
            if (bought == M) break;
        }
        S.erase(S.begin());
    }
    cout << ans << endl;
}

わざわざ、shopというstructを作成して price（価格） / stock（在庫）を入れました。priceでsortできるようにboolのoperatorを定義してます。

実際に提出すると正解しますがTLEに…。多分この時2つ目のループ処理を綺麗に書くことを意識すればなんとかなったはずですが、思いつかず。別解を探します。

解答（コード） - 2回目 AC

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
 
using namespace std;
 
typedef long long int ll;
#define REP(i, I, N) for (ll i = I; i < N; ++i)
#define rep(i, N) REP(i, 0, N)
 
int main() {
    ll N, M, ans = 0;
    cin >> N >> M;
    vector<pair<ll, ll>> pairs(N);
 
    rep(i, N) {
        ll A, B;
        cin >> A >> B;
        pairs[i] = make_pair(A, B); // pairを挿入 price, stock
    }
 
    sort(pairs.begin(), pairs.end());
 
    rep(i, N) {
        ll price, stocks;
        price = pairs[i].first;
        stocks = pairs[i].second;
 
        if (pairs[i].second < M) {
            M -= stocks;
            ans += price * stocks;
        } else {
            ans += M * price;
            cout << ans << "\n";
            return 0;
        }
    }
}

pair、そういえば使えそうと思ってそちらに書き直してAC。
ループ処理の部分を 0 to Nに切り替えてMを減産させる方向で実装しました。
Mの数が在庫より多けりゃ丸っと引いて積をansに足してやります。
もし在庫が上回りそうなケースでは、普通にMと価格の積をansに加算して答えを出力します。

無事AC。多分1回目の書き方でもこのループ処理の書き方ならパスするはず。

解答（コード） - 3回目 AC

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

using namespace std;

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

struct shop {
    ll price;
    ll stock;

    bool operator<(const shop &another) const {
        return price < another.price;
    }
};

int main() {
    ll N, M, ans = 0;
    cin >> N >> M;
    vector<shop> S(N);
    ll A, B;
    rep(i, N) {
        cin >> A >> B;
        S[i].price = A;
        S[i].stock = B;
    }
    sort(S.begin(), S.end());

    rep(i, S.size()) {
        if (M > S[i].stock) {
            M -= S[i].stock;
            ans += S[i].price * S[i].stock;
        } else {
            ans += M * S[i].price;
            cout << ans << "\n";
            return 0;
        }
    }
}

はいこちら、無事ACです。やっぱり処理速度ですねー。TLE増えてきてるので意識しないとな…2回目の提出みたいなコードを一発で書けるようになりたい。

タイトル未設定

Pair

pairは、2つの異なる型の値を保持する「組」を表現するためのクラスである。また、N個の異なる型の値を保持する「タプル」を表現するためのクラスとして、tupleクラスも提供されている。

pair - cpprefjp C++日本語リファレンス

Example

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

using namespace std;

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

int main() {
    int n, f, s;
    cin >> n;
    vector<pair<int, int>> p(n);
    rep(i, n) {
        cin >> f >> s;
        p[i] = make_pair(f, s);
    }

    // unchanged
    rep(i, n) printf("[unsorted] first: %d, second: %d\n", p[i].first, p[i].second);
    sort(p.begin(), p.end());

    rep(i, n) printf("[sorted] first: %d, second: %d\n", p[i].first, p[i].second);
    return 0;
}

Input

・3
・2 10
・1 9
・3 11

Output

[unsorted] first: 2, second: 10
[unsorted] first: 1, second: 9
[unsorted] first: 3, second: 11
[sorted] first: 1, second: 9
[sorted] first: 2, second: 10
[sorted] first: 3, second: 11

正しくsortされて出力されますね。
尚、 下記のようにすると上記とは逆に並び替えられます。降順ですね。

sort(p.begin(), p.end(), greater<pair<int, int>>());

Output

[unsorted] first: 2, second: 10
[unsorted] first: 1, second: 9
[unsorted] first: 3, second: 11
[sorted] first: 3, second: 11
[sorted] first: 2, second: 10
[sorted] first: 1, second: 9

Outro

母の日でしたね。結構実用的なものを送りたいので、どうしようか迷った結果スタバのeギフトカードを送りつけました。この間帰省した時にLINE Payを布教したのでちゃんと使えるようになってると良いな。

それではみなさま、月曜も張り切って。