周りの速さに食らいついた男の備忘録です
コンテスト概要
日本レジストリサービス（JPRS）プログラミングコンテスト2025#1（AtCoder Beginner Contest 392）
開催日:2025年2月8日 21:00-22:40
A - Shuffled Equation
考察
３つの数のうち一番大きいものが積になる必要がある。
なので３つの数をソートしたもの$[A,B,C]$が$A*B=C$になっているかを確認。
提出
A.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
vector<int>num (3);
for(int i = 0;i<3;i++) cin >> num[i];
sort(num.begin(),num.end());
//小さい二つの積と大きい数を比べる
if(num[0]*num[1] == num[2]) cout << "Yes" << endl;
else cout << "No" << endl;
}
B - Who is Missing?
考察
Aの数はすべて違うことが保証されている。なので呼ばれてない数は$n-m$個である。
何かしらで既に呼ばれた数字を管理しておき、それ以外を出力。
提出
B.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
//呼ばれないのはn-m個
cout << n - m << endl;
map<int,bool>mp;
for(int i=0;i<m;i++){
int x;
cin >> x;
//数字が呼ばれたかを管理
mp[x] = true;
}
for(int i=1;i<=n;i++){
//呼ばれてなければ出力
if(!mp[i]) cout << i << endl;
}
}
C - Bib
考察
言われた通りにすればいい。
ただ参照元で参照するので混乱しないよう落ち着いて処理。
提出
C.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
//前からi番目の人が誰を見ているか、何番のゼッケンかを管理
vector<int>gz (n),num (n);
map<int,int>mp;
for(int i=0;i<n;i++) cin >> gz[i];
for(int i=0;i<n;i++){
cin >> num[i];
mp[num[i]] = i;
}
for(int i=1;i<=n;i++){
//i番目の人が見ている人がつけているゼッケンを出力
cout << num[gz[mp[i]] - 1] << endl;
}
}
D - Doubles
考察
さいころは100個しかないので二重ループで組み合わせを全探査。
さいころごとに出目の数を数えておき、(同じで目の通り数)/(2つの出目の通り数)をチェック。
$10^7$個のデータが通るか不安だったが意外とOKだった。
だったら変にこねくり回さなければよかった(2敗)
提出
D.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ll n;
cin >> n;
vector<ll>num (n);
//さいころiの出目の一覧
vector<set<int>>dc (n);
//さいころiに出目jがいくつ出るか？
vector<vector<ll>>cnt (n,vector<ll>(100001,0));
for(int i=0;i<n;i++){
cin >> num[i];
for(int j=0;j<num[i];j++){
int x;
cin >> x;
dc[i].insert(x);
cnt[i][x]++;
}
}
double ans = 0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
double d = num[i]*num[j];
double sum = 0;
//さいころiの出目だけに注目しぞろ目をチェック
for(auto x:dc[i]){
sum += cnt[i][x] * cnt[j][x];
}
ans = max(ans,sum/d);
}
}
cout << fixed << setprecision(9) << ans << endl;
}
E - Cables and Servers
考察
とりあえずすべてのサーバーがつながっているかをUnion-Findでチェック。
つながっていないなら無駄なケーブルを別のサーバーグループに接続。
無駄なケーブルに関しては初め2つのサーバーを結ぶときに確認。
すでに同じグループなら無駄なケーブルリストに追加を繰り返す。
最後に無駄なケーブルが多い順にとりあえずつないでいく。方法としては無駄なケーブルの片方を外し別グループの親に接続。
REが全く取れず困る。25分でDまで通していたのでまあ何とかなるだろうと思っていたが2500位。突然焦る。
Fを通した後意地でREを修正。残り1分。危なかった。
提出
E.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<pair<int,int>>num;
struct UF{
vector<int>par;
vector<vector<int>>ws;
//親かどうかの確認用（正直いらんかった）
vector<bool>st;
//グループの数を管理
int siz;
UF(int n):par(n),ws(n,vector<int>(0)),st(n,true){
for(int i=0;i<n;i++){
par[i] = i;
st[i] = true;
}
siz = n;
}
int root(int n){
if(par[n] == n) return n;
return par[n] = root(par[n]);
}
void unite(int n,int m,int x){
int rn = root(n),rm = root(m);
if(rn == rm){
ws[rn].push_back(x);
return;
}
par[rn] = rm;
st[rn] = false;
siz--;
//無駄なケーブルを親に伝える
if(ws[rn].size() != 0) ws[rm].insert(ws[rm].end(),ws[rn].begin(),ws[rn].end());
return;
}
void ans(int n){
cout << siz - 1 << endl;
if(siz == 1) return;
priority_queue<pair<int,int>> que;
for(int i=0;i<n;i++){
if(!st[i]) continue;
que.push({ws[i].size(),i});
}
//一番無駄なケーブルが多いものからケーブルをつなぐ
auto [s,pos] = que.top();
que.pop();
while(!que.empty()){
auto [x,y] = que.top();
que.pop();
//ケーブルの無駄なものを一本つなぎなおす。
int t = ws[pos].back();
ws[pos].pop_back();
unite(y,pos,0);
cout << t+1 << " " << num[t].first + 1 << " " << y + 1 << endl;
}
return;
}
};
int main(){
int n,m;
cin >> n >> m;
num.resize(m);
UF tree(n);
for(int i=0;i<m;i++){
int x,y;
cin >> x >> y;
x--,y--;
tree.unite(x,y,i);
num[i] = {x,y};
}
tree.ans(n);
}
F - Insert
考察
前からやっていくと席移動が発生してめんどくさい。なので後ろから座ってもらう。
後ろから考えれば「空いてる中で前からi番目に座る」を繰り返せばよい。
前からi番目は何らかの高速な方法を使えばOK。私はいいのが思いつかずセグメントツリーと二分探査のごり押しでAC。
提出
F.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct ST_SUM{
vector<ll>num;
int siz;
ST_SUM(int n){
int x = 1;
while(n > x) x <<= 1;
siz = x;
num = vector<ll> ((x<<1),0LL);
}
void Update(int x,ll i){
x = x + siz - 1;
num[x] = i;
while(x != 0){
x = (x-1)/2; //一段上に上がる
num[x] = num[x*2 + 1]+num[x*2 + 2];
}
}
ll Serch(int n,int m,int k,int l,int r){
if(r <= n || m <= l) return 0;
if(n <= l && r <= m) return num[k];
k *= 2;
int lx = Serch(n, m, k+1, l, (r+l)/2);
int rx = Serch(n, m, k+2, (l+r)/2, r);
return lx + rx;
}
ll Origin_Serch(int n,int m){
return Serch(n, m+1, 0, 0, siz);
}
};
int main(){
int n;
cin >> n;
vector<int> num (n);
for(int i=0;i<n;i++){
int x;
cin >> x;
x--;
num[i] = x;
}
vector<int> ans (n,0);
//埋まった席がいくつあるかを確認する用
ST_SUM tree(n);
for(int i = n-1;i>-1;i--){
int h = 0,t = n-1;
while(h != t){
int c = (h+t) / 2;
//前からC席までに何席埋まっているかをチェック
int k = tree.Origin_Serch(0,c);
//num[i]席空いているかの確認
if(c-k >= num[i]) t = c;
else h = c + 1;
}
//h番目が前からnum[i]番目である。
ans[h] = i+1;
//h番目に座る。
tree.Update(h,1);
}
for(auto x:ans) cout << x << endl;
}
結果
ABCD(2)E(2)F 6完 117:55
順位 1331位
パフォーマンス 1467
感想
人生初6完&入水やったー。
E問題の途中2500位だったときは絶望していたが何とか巻き返した。
落緑しないように頑張るぞ