高性能枝刈機を所望する男の備忘録です
コンテスト概要
AtCoder Beginner Contest 390
開催日:2025年1月25日 21:00-22:40
A - 12435
考察
150点問題ということもありいったんスルー。問題終わりで着手。
いろいろ出来そうだが高々4通りしか正解がないのでパターンを書き出して照合。
きれいにやろうとすれば沼にはまりそうな問題。ごり押しは正義。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
//できうるパターンは下の４つだけ。
vector<vector<int>>ans={{2,1,3,4,5},
{1,3,2,4,5},
{1,2,4,3,5},
{1,2,3,5,4}};
vector<int> che (5);
for(int i=0;i<5;i++) cin >> che[i];
string wer = "No";
//作ったパターンと同じものがあればYes
for(auto x:ans){
if(x==che) wer = "Yes";
}
cout << wer << endl;
}
B - Geometric Sequence
考察
愚直に前2項から公比を出そうかとも思ったが、公比が整数とは限らないことを確認し再考。
等比数列[$a,b,c$]において$a*c = b^2$が必ず成り立つ。
つまり、ある項に対して（前項X後項）が自分の2乗に等しいかをすべて確認すればよい。
これ200点問題か？とも思わなくはない。やるだけと言われたらそれまでだが。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n;
cin >> n;
ll a,b;
//とりあえず前2項をキープ
cin >> a >> b;
string ans = "Yes";
for(int i=2;i<n;i++){
ll x;
cin >> x;
//前＊後＝中＊中になってるかの確認。
if(a*x != b*b) ans = "No";
//値をずらす。
a = b;
b = x;
}
cout << ans << endl;
}
C - Paint to make a rectangle
考察
はぐれる黒いマスがあってはならないので、すべての黒いマスを含むように長方形を書きその中をすべて黒にできるかを確かめる。
全てを含む最小の長方形を考えその中に白いマスがあればNO。
最小の長方形の求め方は上下左右のそれぞれで最も端にある黒いマスに合わせればOK。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int h,w;
cin >> h >> w;
vector<vector<char>>num (h,vector<char>(w));
set<int> x,y;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
cin >> num[i][j];
//黒いマスのx座標とy座標をメモ
if(num[i][j] == '#'){
x.insert(i);
y.insert(j);
}
}
}
//それぞれの座標で端っこにあるものが上限（下限）
int ht = *x.begin(),hb = *x.rbegin() + 1;
int wl = *y.begin(),wr = *y.rbegin() + 1;
string ans = "Yes";
//求めた長方形の中を全探査
for(int i=ht;i < hb;i++){
for(int j=wl;j < wr;j++){
if(num[i][j] == '.') ans = "No";
}
}
cout << ans << endl;
}
D - Stone XOR
考察
Nが12なら多少の無理も問題ないだろうと思っていた時期が私にもありました。
とりあえず重複が出ないようにN個をいくつかの組に分け。それぞれの組で合計値を出しXOR。この手の奴は深さ優先で全通り調べましょう...
という方針だったのだが何度やってもTLE*3。どうして。
提出（失敗）
TLE＊3のコードです
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
set<ll>ans;
vector<ll> num;
void BDF(vector<ll> vec,int now,int ed){
if(now == ed){
ll sum = 0;
for(auto x:vec) sum ^= x;
ans.insert(sum);
return;
}
int siz = vec.size();
for(int i=0;i<siz;i++){
vec[i] += num[now];
BDF(vec,now+1,ed);
vec[i] -= num[now];
}
vec.push_back(num[now]);
BDF(vec,now+1,ed);
}
int main(){
int n;
cin >> n;
num.resize(n);
for(int i=0;i<n;i++) cin >> num[i];
vector<ll>dp ={num[0]};
BDF(dp,1,n);
cout << ans.size() << endl;
}
E - Vitamin Balance
考察
実はD問題から嫌な予感を察知して先にE問題に手を付けていた。まぁうまくいかなかったんですが。
ビタミンが1種類ならただのDPでおしまい。今回は3種類あるのでDPを3回する。
そうすればカロリーごとの栄養量の値が求まる。あとは3重ループだと間に合わないのでビタミン１とビタミン２を固定してビタミン３の最大値をもとめればOK。
なおビタミン３の最大値の取り方を間違えたせいで50分近くを浪費する。
なにやってんだ。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//DPを行う関数を制作
void mdp(vector<vector<int>> &v,vector<pair<int,int>> vv,int vit,int x){
for(int i=0;i<vit;i++){
auto[a,c] = vv[i];
for(int j=0;j<=x;j++){
if(v[i][j] == -1) continue;
v[i+1][j] = max(v[i+1][j],v[i][j]);
if(j+c <= x) v[i+1][j+c] = max(v[i+1][j+c],v[i][j] + a);
}
}
}
int main(){
int n,x;
cin >> n >> x;
vector<pair<int,int>> vv1 (0),vv2 (0),vv3 (0);
int vit1 = 1,vit2 = 1,vit3 = 1;
for(int i=0;i<n;i++){
int v,a,c;
cin >> v >> a >> c;
if(v == 1) vv1.push_back({a,c}),vit1++;
if(v == 2) vv2.push_back({a,c}),vit2++;
if(v == 3) vv3.push_back({a,c}),vit3++;
}
//各ビタミンごとにDPを取る。
vector<vector<int>>v1 (vit1,(vector<int>(x+1,-1))),v2 (vit2,(vector<int>(x+1,-1))),v3 (vit3,(vector<int>(x+1,-1)));
v1[0][0] = 0,v2[0][0] = 0,v3[0][0] = 0;
mdp(v1,vv1,vit1-1,x);
mdp(v2,vv2,vit2-1,x);
mdp(v3,vv3,vit3-1,x);
//カロリーX以下の最大栄養量を表にする。
for(int i=0;i<x;i++) v3[vit3 - 1][i + 1] = max(v3[vit3 - 1][i],v3[vit3 - 1][i+1]);
int ans = 0;
for(int i=0;i<=x;i++){
for(int j=0;j+i<=x;j++){
//ビタミン１とビタミン２の摂取カロリーを決めれビタミン３の最大値も求まる。
int k = x-i-j;
int c = min({v1[vit1-1][i],v2[vit2-1][j],v3[vit3-1][k]});
ans = max(ans,c);
}
}
cout << ans << endl;
}
結果
結果 ABCE(3) 4完 109:41
順位 1899位
パフォーマンス 1253
感想
ただただ実装力のなさ、考えの詰めの甘さが露呈している。今回もＥ問題を早く仕留めればさらに上位を目指せたのに。
ただただ惜しい。
次回1400のパフォが出れば入水。手はかかっているはず。