#12 - 文系出身エンジニアが競プロをやる
※このマガジンは不定期投稿です。
Intro
ちわ、今日も競プロをやっていきます。
本日解いた問題は、AtCoder Beginner Contest 121のA-C問題です。
AとBは難しくないので、コードだけぺっと貼って進めます。
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?
問題概要
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）
問題概要
栄養ドリンクにレーティング上昇効果がある（すげえな）らしく、登場人物の高橋くんはこれにあやかろうとして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クラスも提供されている。
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を布教したのでちゃんと使えるようになってると良いな。
それではみなさま、月曜も張り切って。
いいなと思ったら応援しよう！
