皆様こんにちは！ばるとーくです！
今回はABC474の振り返りをしていこうと思います！
はじめに ～結果～
ABDの3完でした！（自分にしては珍しい）
C問題が個人的にめっちゃ難しかった記憶がある
各問題振り返り
A - Not X
問題文
$1$ 以上 $3$ 以下の整数 $X$ が与えられます。
$1$ 以上 $3$ 以下の整数であって $X$ と異なる整数を $1$ つ出力してください。
制約
- $X$ は $1$ 以上 $3$ 以下の整数
$1 \to 2, 2 \to 3, 3 \to 1$ と変換してやりました．
if文がすごく汚く見えますが，確実に解けるから...
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (ll i = a; i < b; ++i)
#define rrep(i, a, b) for (ll i = a; i >= b; --i)
// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
Init() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
}
} init;
// ------------------------------------------------
int main() {
int x;
cin >> x;
if (x == 1) {
cout << 2 << "\n";
} else if (x == 2) {
cout << 3 << "\n";
} else {
cout << 1 << "\n";
}
return 0;
}
B - Exit Order
問題文
ある映画館には $1$ から $N$ までの番号が付いた $N$ 個の座席があり、各座席には客が一人ずつ座っています。
この映画館では混雑対策として以下のルールに従って客が退場することになっています。
- 座っている座席の番号が小さい順に、客を 10 人ずつのグループに分ける。
- 座席番号が小さい客からなるグループから順に退場する。ただし、同じグループ内の客の退場順は自由である。
最後のグループの客の人数は $10$ 人未満にもなり得ることに注意してください。
$i$ 番目に退場したのは座席 $P_i$ に座っていた客でした。
N$ 人の客がルールに従って退場したかどうかを判定してください。制約
- $10 \leq N \leq 100$
- $(P_1,P_2,\dots,P_N)$ は $(1,2,\dots,N)$ の順列
- 入力される値はすべて整数
グループの順番を0-indexed（$0$ 始まり）に直して，$10$ で割ることで，$i$ 番目に出た客が本来どのグループに属するかが簡単に管理できるようになります．
で，groupを-1から始めて，$10$ の剰余が余りを取らないたびに $+1$ します．これにより，「今はどのグループの時間か」が管理できます．
よって，この問題を効率的に解くことができました～ってな感じです．
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (ll i = a; i < b; ++i)
#define rrep(i, a, b) for (ll i = a; i >= b; --i)
// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
Init() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
}
} init;
// ------------------------------------------------
int main() {
int n;
cin >> n;
int group = -1;
rep(i, 0, n){
if(i % 10 == 0){
++group;
}
int p;
cin >> p;
--p;
if(p / 10 != group){
cout << "No\n";
return 0;
}
}
cout << "Yes\n";
return 0;
}
C - Remove and Append
問題文
$(1,2,\dots,N)$ の順列 $P=(P_1,P_2,\dots,P_N)$ が与えられます。
$q=1,2,\dots,Q$ の順に、以下の操作を行います。
- $P$ から値が $a_q$ である要素を削除し、それを $P$ の末尾に追加する。
$Q$ 個の操作を行った後の $P$ の各要素の値を求めてください。
制約
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq Q \leq 2 \times 10^5$
- $(P_1,P_2,\dots,P_N)$ は $(1,2,\dots,N)$ の順列
- $1 \leq a_q \leq N$
- 入力される値はすべて整数
これ本当に難しかったです...
めちゃくちゃ考えましたがわからず，飛ばしましたからね一回（）
なぜかというと，「それ愚直にやると毎回 $O(N)$ 掛かりません!?」から抜け出せなかったからですね．
ただ，最後の最後に気づいて，「連想配列をもって，一番先頭の数字を $n$ 番目とする．そこから後ろに行くごとに $n$ を $1$ ずつ減らす．そして，後ろに行かされる数字は (1 + i) * -1) で上書きすることで，降順ソート1回で正しい順番になる！」と．
急ぎ実装しましたが間に合わず...そもそもCEでした．
(pair配列を初期化する方法を間違えてただけでした．もったいない．)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (ll i = a; i < b; ++i)
#define rrep(i, a, b) for (ll i = a; i >= b; --i)
// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
Init() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
}
} init;
// ------------------------------------------------
int main() {
int n, q;
cin >> n >> q;
vector<pair<int, int>> p(n + 1, {INT_MIN, INT_MIN});
rep(i, 0, n) {
int inp;
cin >> inp;
p[inp].first = n - i;
p[inp].second = inp;
}
rep(i, 0, q) {
int inp;
cin >> inp;
p[inp].first = min(p[inp].first, (int)((1 + i) * -1));
}
sort(p.rbegin(), p.rend());
rep(i, 0, n) {
cout << p[i].second << " ";
}
cout << "\n";
return 0;
}
D - Outweigh
問題文
$N$ 種類の石 $1,2,\dots,N$ があり、同じ種類の石の重みはすべて同じです。
高橋君と青木君は石 $i$ をそれぞれ $A_i,B_i$ 個ずつ持っています。
以下の条件を満たすような正整数列 $W=(W_1,W_2,\dots,W_N)$ が存在するかどうかを判定し、存在するならば一つ構成してください。
- $1 \leq W_i \leq 10^{18}$
- 石 $i$ の重みが $W_i$ のとき、高橋君が持っている石の重みの総和が青木君が持っている石の重みの総和よりも真に大きい。
制約
- $1 \leq N \leq 10^5$
- $1 \leq A_i \leq 10^9$
- $1 \leq B_i \leq 10^9$
- 入力される値はすべて整数
所謂「構築」と呼ばれる類の問題らしいですね
私この問題は得意だったかもしれません．すぐに方針が浮かんできましたから．
このようにします.
$$\begin{cases} (A_i > B_i) ：& \text{その石の重さを } 10^{18} \text{ に} \\ (\text{otherwise}) ： & \text{その石の重さを } 1 \text{ に} \end{cases}$$
これが自明だなぁ～と思ったのでこうして（実際のコードはオーバーフローに謎にビビったので $10^{17}$ にしていますが）,
すべての石で重さが $1$ になった場合は No, そうでないなら Yes とします．
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (ll i = a; i < b; ++i)
#define rrep(i, a, b) for (ll i = a; i >= b; --i)
// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
Init() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
}
} init;
// ------------------------------------------------
int main() {
int n;
cin >> n;
vector<ll> a(n), b(n);
ll asum = 0;
ll bsum = 0;
rep(i, 0, n) {
cin >> a[i];
asum += a[i];
}
rep(i, 0, n) {
cin >> b[i];
bsum += b[i];
}
vector<ll> w(n);
bool isOnly1 = true;
rep(i, 0, n) {
if (a[i] > b[i]) {
w[i] = 1e17;
isOnly1 = false;
} else {
w[i] = 1;
}
}
if (isOnly1) {
cout << "No\n";
} else {
cout << "Yes\n";
rep(i, 0, n) {
cout << w[i] << " ";
}
cout << "\n";
}
return 0;
}
最後に ～レート変化～
順調に伸びていますねっ！
茶色に向けていい感じだと思います！
最後までお読みいただきありがとうございました！
時間がある方は，おすすめ欄よりぜひほかの記事ものぞいて行ってくださいね！
また，作品集のページ・リンク集ものぞいてみてくださいね！
それでは，またお会いしましょう！
コメント