ちょっとやる気になった男の備忘録です
コンテスト概要
AtCoder × Engineer Guild オンサイトコンテスト ～集結！高レート人材～予選（AtCoder Beginner Contest 424）
開催日:2025年9月20日 21:00-22:40
A - Isosceles
考察
相当シンプルなA問題。
全ての辺の組のうち一つでも同じものがあればOK。
正三角形も二等辺三角形なので例外処理の必要もなし。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int a,b,c;
cin >> a >> b >> c;
//それぞれ2辺が同じかチェック
if(a==b || b==c || c == a) cout << "Yes" << endl;
else cout << "No" << endl;
}
B - Perfect
考察
問題文がごちゃっとしているが要するに「M回正解した人を順番に出してください」ってだけ。
同じ人が同じ問題を複数回正解することもないので、問題番号は無視して正解した回数だけを数えればOK。
まぁ、高々10問なのでどの問題を正解したかを律儀にメモしてもいいけど、単純に出来るならその方がいいね。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m,k;
cin >> n >> m >> k;
vector<int>num (n,0);//正解数をメモ
vector<int>ans (0);//完答した順をメモ
for(int i=0;i<k;i++){
int x,y;
cin >> x >> y;
num[x-1]++;//正解数を1増やす
if(num[x-1] == m) ans.push_back(x);//完答したらリストに入れる。
}
//リストを出力
for(auto x:ans) cout << x << endl;
}
C - New Skill Acquired
考察
例えばスキルNが(A,B)のとき、スキルN習得への道のりは「スキルA→スキルN」か「スキルB→スキルN」の二通りだけ。
また、(0,0)の場合スキル0というものを作り「スキル0→スキルN」ということにすればいい。
これをまとめると0~Nまでの有向グラフが出来上がる。
後は0をスタートとしてたどることができる頂点の数を数えればいい。
方法はBFSでもDFSでもなんでも大丈夫のはず。
今回は少しさぼって0から行けるところをすべてqueueに入れる多始点BFSで実装。
まぁ先に思いついたので多少の汚さはご愛敬ということで。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<vector<int>>num (n,vector<int>(0));//次に取れうるスキルをまとめる
vector<bool>gone (n,false);//すでに確認したかどうか
queue<int>que;
for(int i=0;i<n;i++){
int x,y;
cin >> x >> y;
if(x == 0 && y == 0){
//スキルが習得できるなら確認してqueに入れる。
gone[i] = true;
que.push(i);
}else{
//まだ習得できないなら、前のスキルから矢印を伸ばす。
num[x-1].push_back(i);
num[y-1].push_back(i);
}
}
int ans = 0;
while(!que.empty()){
//スキル獲得ごとに1増やす。
ans++;
int now = que.front();
que.pop();
for(auto nex:num[now]){
if(!gone[nex]){
//次とれるスキルが未確認なら確認してque
gone[nex] = true;
que.push(nex);
}
}
}
cout << ans << endl;
}
D - 2x2 Erasing 2
考察
見た目のわりにどうしようにもなかった。
2,3個方針を思いついて実装したが駄目。
解説の「答えは高々9個」という部分には思わず膝を打った。
E - Cut in Half
考察
Dが駄目な以上、死守せねばならないE問題。必死に考察を進める。
愚直な方針としては「長い棒を探して割ることをK回繰り返す」方法。
もちろん1ケースあたり最大$10^9$回割るので到底間に合わない。
なのでできるだけ事前に割っておきたい。
ここでどの棒もパーツが$10^9$個より多く分割されることはない。
$2^{29} < 10^9 < 2^{30} $なので1つの棒を30回より多く折半することはない。
なので1つの棒が取りうる長さは高々31通りしかない。
全ての棒が取りうる長さ$31\times N$通りのうちどれかが割るべき長さの境界があるはず。
ここまでくればちまちまやっても間に合いそうだが二分探査でパッパと境界を求める。
後は境界の長さまで割り端数も適当に割れば、棒の長さはすべて求まる。
ただこのままX番目に長い棒を探してしまうとせっかくの時短が無駄になる。
棒はできる限り半分にし続けているので同じ長さの棒が何本もできていることになる。
だったら棒の長さと個数でまとめてやったほうが楽に決まっている。
あとは、優先度付きQUEUEとかに投げればOK。
というか、どうせランレングス圧縮みたいなことするなら最初の二分探査いらなかったね。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//目標の長さになるまで切る回数を求める関数
ll ct(double tr,double std){
ll ans = 0;
while(tr > std){
//目標より長いなら半分にする。
ans <<= 1;
ans++;
tr /= 2.0;
}
return ans;
}
int main(){
int t;
cin >> t;
for(int fr=0;fr<t;fr++){
int n,k,x;
cin >> n >> k >> x;
vector<double>num (n);
vector<double>len (0);//取りうる長さを求める。
for(int i=0;i<n;i++){
double d;
cin >> d;
num[i] = d;
len.push_back(d);
for(int j=1;j<31;j++){
//ガンガン半分にしていく
d /= 2.0;
len.push_back(d);
}
}
sort(len.begin(),len.end());
int hd = 0,tl = n*31;
//二分探査で長さの上限を決める
while(hd != tl){
int c = (hd+tl)/2;
double std = len[c];
ll cnt = 0;
for(auto d:num){
cnt += ct(d,std);
}
//切るべき回数が多すぎるなら目標が短い。
if(cnt > k) hd = c + 1;
else tl = c;
}
double std = len[hd];
priority_queue<pair<double,ll>>que;
ll c = 0;
for(auto d:num){
//全部の棒を目標の長さ以下になるまでカット
ll pt = 1;
while(d > std){
pt <<= 1;
d /= 2.0;
}
que.push({d,pt});
c += pt;
}
k += n;
while(c != k){
//端数が出たなら長い順に適当に切る
ll rem = k-c;
auto[siz,cnt] = que.top();
que.pop();
if(cnt <= rem){
c += cnt;
que.push({siz/2.0,cnt*2LL});
}else{
cnt -= rem;
que.push({siz,cnt});
que.push({siz/2.0,rem*2LL});
c += rem;
}
}
while(x > 0){
//前から順番に見てX番目を探す。
auto[siz,cnt] = que.top();
que.pop();
x -= cnt;
if(x <= 0){
cout << fixed << setprecision(10) << siz << endl;
}
}
}
}
結果
ABCE 4完 73:56
順位 1232位
パフォーマンス 1369
レート 1343(+3)
感想
ここ最近ずっと燻っていたので定位置に戻ってこれただけでも良しとする。
ただ、D問題のようなちゃんと考察しないといけない問題を克服しないと青コーダーは遠い。