皆様こんにちは！ばるとーくです！
今回はABC461の振り返りをやっていきます！
講評
結果は3完となりました！
C問題の2ペナがえらく痛いです…
A-Armor
問題文
高橋君は鎧を着ています。
この鎧は威力（整数で表される攻撃の強さ）が $D$ 以下の攻撃をすべて防ぎますが、威力が >$D$ より大きい攻撃は防ぎません。
この鎧は威力が $A$ の攻撃を防ぎますか。
制約
$$
- 1 \le A \le 100
- 1 \le D \le 100
$$- 入力される値はすべて整数
これについては、書かれている通りに実装しました。
(つまり何も話すことがない…)
コードはこちらです
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
Init() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
}
} init;
// ------------------------------------------------
int main() {
int a, d;
cin >> a >> d;
if(a <= d){
cout << "Yes" << "\n";
}else{
cout << "No" << "\n";
}
return 0;
}
B - The Honest Woodcutters
問題文
$N$ 人の木こり $1,2,\dots,N$ が斧を $1$ 個ずつ持っています。全員が斧を池に落としてしまいました。
池に $N$ 個の斧 $1,2,\dots,N$ が沈んでいました。
各木こり $i$ は「自分が持っていた斧は斧 $A_i$ である」と主張しています。
一方、この池の女神は、各斧 $i$ を持っていたのは木こり $B_i$ であることを知っています。$N$ 人の木こり全員が本当のことを言っているかどうかを判定してください。
制約
- $1 \le N \le 100$
- $1 \le A_i \le N$
- $1 \le B_i \le N$
- $A_i \ne A_j \ (i \ne j)$
- $B_i \ne B_j \ (i \ne j)$
- 入力される値はすべて整数
こちらもさくっと通すことが出来ました!(5分半くらい)
実はB問題にしては珍しくもあります。
※沼るときはとことん沼ります
コードはこちらです
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
Init() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
}
} init;
// ------------------------------------------------
int main() {
int n;
cin >> n;
vector<int> a(n), b(n);
for(int i = 0; i < n; i++){
cin >> a<!--SC_0-->;
}
for (int i = 0; i < n; i++) {
cin >> b<!--SC_1-->;
}
for (int i = 0; i < n; i++) {
if(i + 1 != b[a<!--SC_2--> - 1]){
cout << "No" << "\n";
return 0;
}
}
cout << "Yes" << "\n";
return 0;
}
始めに木こり $i$ の主張と女神が知っている持ち主をvecに収納します。
その後、木こり $i$ と、斧 $i$ の持ち主を比較し、1人でも違ったらNoと出力するように組みました。
indexが違うので実装に注意です。※間違えた
C - Variety
問題文
$N$ 個の宝石があります。$i$ 番目の宝石の色（整数で表されます）は $C_i$ で価値は >$V_i$ です。
この $N$ 個の宝石の中から $K$ 個を選びます。ただし、選んだ宝石の色が $M$ 種類以上なければなりません。
このとき、選んだ宝石の価値の総和としてありうる最大値を求めてください。（与えられる入力では、このような選択が必ず可能です。）
制約
- $1 \le M \le K \le N \le 2 \times 10^5$
- $1 \le C_i \le N$
- $1 \le V_i \le 10^9$
- $M$ 種類以上の色の宝石が存在する
- 入力される値はすべて整数
これ、めっちゃ大変でした…
発想としては、こんな感じです。
- 宝石の価値と色をpairにしてvecに収納して降順ソートする。
- 色の種類 $m$ が達成されてない間、色の重複がなければ合計し、重複していれば一旦バッファによける。
- 色の種類が達成された後、まだ宝石の数 $K$ に達していなければ、まずバッファから合計する。バッファがなくなればvecの続きから合計していく。
これを実現するために、最終的に選んだのがsetとqueueです。
setで色の種類を管理し、queueでバッファの役割を担わせる、といった感じですねっ。
が、これがめっちゃ大変でした…
条件分岐が複雑だったり、範囲外参照でエラーを出したり…
最終的なコードがこちら
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
Init() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
}
} init;
// ------------------------------------------------
int main() {
ll n, k, m;
cin >> n >> k >> m;
vector<pair<ll, ll>> jue(n);
for (ll i = 0; i < n; i++) {
cin >> jue<!--SC_3-->.second >> jue<!--SC_4-->.first; // fir:v, sec:c
}
sort(jue.rbegin(), jue.rend());
ll ans = 0;
set<ll> var;
queue<ll> que;
ll now = 0;
ll sel = 0;
while (var.size() < m && sel < k && now < n) {
ll fn = jue<!--SC_5-->.second;
if (var.find(fn) == var.end()) {
ans += jue<!--SC_6-->.first;
var.insert(jue<!--SC_7-->.second);
++sel;
} else {
que.push(now);
}
cerr << now << "\n";
++now;
}
while (sel < k) {
if (que.size() != 0) {
ans += jue[que.front()].first;
que.pop();
++sel;
} else {
ans += jue[now++].first;
++sel;
}
cerr << now << "\n";
}
cout << ans << "\n";
return 0;
}
最初はsetをvecにしててTLEを出したのはナイショです…
レート変化
こんな感じで勝ち越しです！茶パフォ出てます
（コンテスト中の予測だと今回で入茶だったんだけどなぁ…？）
コメント