皆様こんにちは！ばるとーくです！
今回はABC463の振り返りをしていこと思います！
（前回負けたから書いてないのはナイショね…）
※実際負けると萎えてしまうので執筆のモチベがないなる（当然あまりよろしくないと思ってる）
結果
今回の結果は3完でした！
しかも結構速い！
※１ペナは痛い
振り返り
A - 16:9
問題文
横 $X$ ピクセル、縦 $Y$ ピクセルの画像があります。 横の長さと縦の長さの比が $16$ 対 $9$ であるか、すなわち $X:Y=16:9$ であるかを判定してください。
制約
- $1 \leq X \leq 1000$
- $1 \leq Y \leq 1000$
- 入力はすべて整数
一発ACです。
私が提出したコードはこれでした
#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 x, y;
cin >> x >> y;
if(x % 16 == 0 && y % 9 == 0){
cout << "Yes" << "\n";
}else{
cout << "No" << "\n";
}
return 0;
}
しかし…どうやらこれは嘘解法だったようです…
調べた感じ、（AtCoder Sempaiのコメントより）例えば $(x = 16 : y = 18)$ のようなケースでWAとなるそうで…
悪運が強いというかなんというか…（はじかれてたら多分また沼ってたよ）
大げさな…って思うかもしれんけど‼テンパると比の計算方法すら忘れるんだよっ‼
B - Train Reservation
問題文
高橋君は列車の座席を予約しようとしています。
高橋君が予約する候補としている列車は $N$ 本あり、列車 $1,2,\dots,N$ と番号が付けられています。 いずれの列車も座席は $5$ 列からなり、それぞれ A 列、B 列、C 列、D 列、E 列と呼ばれています。
各列車の現在の空席情報が文字列 $S_1,S_2,\dots,S_N$ として与えられます。 ここで $S_1,S_2,\dots,S_N$ はすべて長さ $5$ で、列車 $i$ の A 列から E 列までがそれぞれ $S_i$ の $1$ 文字目から $5$ 文字目と対応しており、その文字が o ならば対応する列に空席があることを、x ならば対応する列に空席がないことを意味します。
高橋君は $X$ 列の席を予約したいです。ここで $X$ は A、B、C、D、E のいずれかです。 $1$ 本以上の列車において $X$ 列に空席があるか判定してください。
制約
- $N$ は $1$ 以上 $100$ 以下の整数
- $X$ は A、B、C、D、E のいずれか
- $S_i$ は o、x からなる長さ $5$ の文字列
これも一発ACです。
これはこんなコードで実装しました。
#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;
char x;
cin >> x;
int res = 0;
switch (x) {
case 'A':
res = 0;
break;
case 'B':
res = 1;
break;
case 'C':
res = 2;
break;
case 'D':
res = 3;
break;
case 'E':
res = 4;
break;
default:
break;
}
for (int i = 0; i < n ; i++) {
string s;
cin >> s;
if(s<!--SC_0--> == 'o'){
cout << "Yes" << "\n";
return 0;
}
}
cout << "No" << "\n";
return 0;
}
席のアルファベットをインデックスに置き換え、文字列の中のインデックスが1つでもoならそれで良い、というコードです。
charの変換はまだ覚えられましぇん…それできればもっと短縮できる。
C - Tallest at the Moment
問題文
現在、会議室に $N$ 人の高橋くんがいます。 $i$ 番目 $(1\le i\le N)$ の高橋くんの身長は $H _ i$ であり、今から $L _ i$ 分後に会議室を去ります。 一度会議室を去った高橋くんはそれ以降会議室に戻ることはありません。
$Q$ 個のクエリが与えられるので、順に答えてください。 $i$ 番目 $(1\le i\le Q)$ のクエリでは整数 $T _ i$ が与えられるので、今から $T _ i+\dfrac12$ 分後に会議室にいる高橋くんの身長の最大値を答えてください。 この問題の制約のもとで、今から $T _ i+\dfrac12$ 分後には会議室に $1$ 人以上の高橋くんがいることが保証されます。
制約
- $1\le N\le3\times10 ^ 5$
- $1\le H _ i\le10 ^ 9\ (1\le i\le N)$
- $1\le L _ 1\le L _ 2\le\cdots\le L _ N\le10 ^ 9$
- $1\le Q\le3\times10 ^ 5$
- $0\le T _ i\lt L _ N\ (1\le i\le Q)$
- 入力はすべて整数
これはTLE -> ACとなりました。
開始から30分でここまでこれたのは結構でかいと思ってます！
まず、初めに出したコードがこちら
#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<pair<ll, ll>> h(n);
vector<ll> l(n);
for(int i = 0; i < n; i++){
cin >> h<!--SC_1-->.first >> l<!--SC_2-->;
h<!--SC_3-->.second = i;
}
sort(h.rbegin(), h.rend());
int q;
cin >> q;
for(int i = 0; i < q; i++){
ll t;
cin >> t;
auto it = lower_bound(l.begin(), l.end(), t + 1);
cerr << *it << it - l.begin() << "\n";
for(int j = 0; j < n; j++){
if (h<!--SC_4-->.second >= it - l.begin()){
cout << h<!--SC_5-->.first << "\n";
break;
}
}
}
return 0;
}
まず、$L$ が単調増加だったので二分探索ということはすぐにわかりました。
しかし、残念ながらこの時は最高の身長の高橋君を見つける方法がうまくならず…
始めに思ってたのは、「身長と元のインデックスを持たせた配列を高い順にソートして、二分探索で求めた $L$ より大きければ採用する、をfor文で実装する」というのをやってました。
しかし、これは $O(n^2)$ なので当然TLEでした。
勘違いで通ってくれたらうれしかったのになぁ～（なわけ）
というわけでAC版がこちら
#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<pair<ll, ll>> h(n);
vector<ll> l(n);
for (int i = 0; i < n; i++) {
cin >> h<!--SC_6-->.first >> l<!--SC_7-->;
}
h<!--SC_8-->.second = h<!--SC_9-->.first;
for (int i = n - 2; i >= 0; i--) {
h<!--SC_10-->.second = max(h<!--SC_11-->.first, h<!--SC_12-->.second);
}
int q;
cin >> q;
for (int i = 0; i < q; i++) {
ll t;
cin >> t;
auto it = lower_bound(l.begin(), l.end(), t + 1);
cerr << *it << it - l.begin() << "\n";
cout << h<!--SC_13-->.second << "\n";
}
return 0;
}
$H$ を逆から走査して、その時点での最大身長を記録するようにしたらうまくいきましたねっ！
計算量は… $O(N + Q \log N)$ ですかね…？
※「それは違うよ！」っていう方ぜひコメントで教えてください
2026/6/21修正：計算量を修正しましたっ
最後に～レート変動～
なんとなんと、やっとの思いで入茶できました！
本当にうれしい…
でも、まだまだこれから頑張っていかんとなぁ…
※そういえばこれまだスタート地点
ばるとーくならまだまだやれるはず！精進の時間が圧倒的に足りてないのはそうだけども！
入茶記事は必ず書きます！
ろくに書くことやアドバイスなんてないけどもね…
あと一番怖いのは次に落灰することですね（フラグじゃないよ！）
ここまでお読みいただきありがとうございましたっ！
お時間ありましたら、ほかの記事も読んでいってください！
それから！リンク集から私のアカウントがある色んなサイトに飛べます！
そちらもチェックしてみてくれると嬉しいです！
それではまた～
コメント