Photo by
pav
#15 - 文系出身エンジニアが競プロをやる
Intro
AtCoder Beginner Contest 127です。
正解については公式の解説を参照ください。
やっていきます…！
A - Ferris Wheel
問題
年齢Aに応じて、金額Bが通常・半額・無料になる。与えられるAとBから適切な金額を出力しなさい（13歳以上はB円、6歳以上12歳以下はB/2円、5歳以下無料）。
解答（コード）
#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 A, B;
cin >> A >> B;
if (6 <= A && A <= 12) {
B /= 2;
} else if (A <= 5) {
B = 0;
}
cout << B << endl;
return 0;
}何も難しいことは必要ないですね…AC。
B - Algae
問題
生えてる藻類の重さの合計についてx2001...x2010までを順に出力しなさい。
解答（コード）
#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 r, D, x;
cin >> r >> D >> x;
for (int i = 1; i < 11; i++) {
x = x * r - D;
cout << x << endl;
}
return 0;
}久しぶりに競プロやった感があって、頭回らず35分かかってしまった…。
C - Prison
問題
N枚の ID カードとM個のゲートがあります。
i番目のゲートは Li,Li+1,...,Ri番目の ID カードのうちどれか 1枚を持っていれば通過できます。
1枚だけで全てのゲートを通過できる ID カードは何枚あるでしょうか。
問題みた時よくわからず、結局ずるずる引きずって時間ないに解けず。
悔しいなあ…解説を読みながら、解きました。
解答（コード） - WA
#include <iostream>
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, l, r;
cin >> n >> m;
ll ans = 0;
rep(_, m) {
cin >> l >> r;
rep(i, n) {
ll point = i + 1;
if (l <= point) {
if (r == point || r == point + 1) {
ans++;
break;
}
}
}
}
cout << ans << endl;
return 0;
}解答（コード） - 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)
int main() {
ll n, m, l, r;
cin >> n >> m;
ll ans = 0;
ll mn = 100001, mx = -100001;
vector<ll> lm(m), rm(m);
rep(i, m) {
cin >> l >> r;
mx = max(l, mx);
mn = min(r, mn);
}
REP(i, 1, n + 1) {
if (mx <= i && i <= mn) {
ans++;
}
}
cout << ans << endl;
return 0;
}最小値、最大値を割り出してカードと比較し、条件内に含まれるものだけ数え上げるものでした。
D - Integer Cards
問題
N枚のカードがあり、i番目のカードには整数 Aiが書かれています。
あなたは、j=1,2,...,Mについて順に以下の操作を 1回ずつ行います。
操作: カードを Bj枚まで選ぶ(0枚でもよい)。選んだカードに書かれている整数をそれぞれ Cjに書き換える。
M回の操作終了後に N枚のカードに書かれた整数の合計の最大値を求めてください。
解答（コード） - TLE
#include <iostream>
#include <vector>
#include <numeric>
#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;
cin >> N >> M;
vector<ll> card(N);
rep(i, N) cin >> card[i];
sort(card.begin(), card.end(), less<ll>());
ll B, C;
rep(i, M) {
cin >> B >> C;
rep(j, B) {
if (card[j] < C) {
card[j] = C;
}
}
sort(card.begin(), card.end(), less<ll>());
}
cout << accumulate(card.begin(), card.end(), 0LL) << endl;
return 0;
}こちらも解答はあっているっぽいんですが、計算量がカバーできずTLEで終わってしまいました。O(MB）になるのでMとBの数が増えると遅くなってしまうみたいでした。
解答（コード） - AC
解説をみながら再度考えて実装していきます。ソートの話が出てきましたが、Priority queueを使ったことなかったのでこちらで実装していきました。
#include <iostream>
#include <vector>
#include <queue>
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, A, B, C, ans = 0;
cin >> N >> M;
vector<ll> card(N);
priority_queue<pair<ll, ll>> que;
rep(i, N) {
cin >> A;
que.push(make_pair(A, 1));
}
rep(i, M) {
cin >> B >> C;
que.push(make_pair(C, B));
}
rep(i, N) {
pair<ll, ll> p = que.top();
que.pop();
ans += p.first;
if (p.second > 1) {
p.second--;
que.push(p);
}
}
cout << ans << endl;
return 0;
}priority queueは下記に記載があります。
priority_queueはコンテナアダプタであり、優先順位付きキューを実現する目的で設計されている。要素をpush()で追加し、取り出す際にtop()を呼び出すことで、Compare述語によって優先順に要素が取り出される。
E - Cell Distance
未解答
F- Absolute Minima
未解答
Outro
パフォーマンスは276でした 😇😇😇
強くなりたい…
けんちょん氏が作成されている ac-predictorが便利なので、紹介しておきます。
コンテスト中に推定のパフォーマンスをチェックすることができるスクリプトです。
PriorityQueue
priority_queueについて軽く確認してみます。
っていうかauto型めちゃ便利だな、全部autoになりそう。
TypeScriptでany使うなって怒られる感じが想起されますが…
#include <iostream>
#include <queue>
#include <random>
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;
priority_queue<int> q;
cin >> n;
rep(i, n) {
int r = random() / 10000000;
printf("input: %d\n", r);
q.push(r);
}
printf("\n");
while (!q.empty()) {
auto p = q.top();
q.pop();
printf("output: %d\n", p);
}
return 0;
}
/* In Out…
input: 180
input: 84
input: 168
input: 171
input: 195
output: 195
output: 180
output: 171
output: 168
output: 84
*/大きいものから出力されるようですね、めっちゃ良いな…。
明日もコンテストがあるのでそれまでは蟻本に目を通しつつ数学の勉強でもします。
😡😡😡😡
いいなと思ったら応援しよう！
