🔵
【ABC374】AtCoder Beginner Contest 374【C++】
コンテスト名
キーエンスプログラミングコンテスト2024(AtCoder Beginner Contest 374)
コンテストURL
開催日
2024/10/05 21:00-22:40
A: Takahashi san 2
解法
- 問題文通りに判定する
ABC374A.cpp
#include <iostream>
#include <string>
using namespace std;
int main(){
string s;
cin >> s;
if(s.substr(s.size()-3)=="san"){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
return 0;
}
B: Unvarnished Report
解法
- 文字列の長さが異なる場合に注意して問題文通りに判定する
ABC374B.cpp
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
string s, t;
cin >> s >> t;
int n = min(s.size(), t.size());
for(int i=0; i<n; i++){
if(s[i]!=t[i]){
cout << i+1 << endl;
return 0;
}
}
if(s.size()!=t.size()){
cout << n+1 << endl;
}else{
cout << 0 << endl;
}
return 0;
}
C: Separated Lunch
解法
- bit 全探索
- 再帰関数
- それぞれの部署をどちらのグループに割り当てるか全探索する
ABC374C_1.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> K(n);
for(int i=0; i<n; i++){
cin >> K[i];
}
int minv = 3e9;
for(int i=0; i<(1<<n); i++){
int a = 0, b = 0;
for(int j=0; j<n; j++){
if(i&(1<<j)){
a += K[j];
}else{
b += K[j];
}
}
minv = min(minv, max(a, b));
}
cout << minv << endl;
return 0;
}
ABC374C_2.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<int> K;
int minv = 3e9;
int a = 0, b = 0;
void dfs(int num){
if(num==n){
minv = min(minv, max(a, b));
return;
}
a += K[num];
dfs(num+1);
a -= K[num];
b += K[num];
dfs(num+1);
b -= K[num];
return;
}
int main(){
cin >> n;
K.resize(n);
for(int i=0; i<n; i++){
cin >> K[i];
}
dfs(0);
cout << minv << endl;
return 0;
}
D: Laser Marking
解法
- 順列全探索 + bit 全探索
- 順列全探索で線分の順番を探索する
- bit 全探索で各線分の移動方向を探索する
ABC374D.cpp
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main(){
int n, s, t;
cin >> n >> s >> t;
vector<int> A(n), B(n), C(n), D(n);
for(int i=0; i<n; i++){
cin >> A[i] >> B[i] >> C[i] >> D[i];
}
vector<int> V(n);
for(int i=0; i<n; i++){
V[i] = i;
}
double minv = 1e9;
do{
for(int i=0; i<(1<<n); i++){
double sum = 0;
for(int j=0; j<n; j++){
if(i&(1<<j)){
sum += sqrt(pow(A[V[j]]-C[V[j]], 2) + pow(B[V[j]]-D[V[j]], 2))/t;
if(j){
if(i&(1<<(j-1))){
sum += sqrt(pow(A[V[j]]-C[V[j-1]], 2) + pow(B[V[j]]-D[V[j-1]], 2))/s;
}else{
sum += sqrt(pow(A[V[j]]-A[V[j-1]], 2) + pow(B[V[j]]-B[V[j-1]], 2))/s;
}
}else{
sum += sqrt(pow(A[V[j]], 2) + pow(B[V[j]], 2))/s;
}
}else{
sum += sqrt(pow(A[V[j]]-C[V[j]], 2) + pow(B[V[j]]-D[V[j]], 2))/t;
if(j){
if(i&(1<<(j-1))){
sum += sqrt(pow(C[V[j]]-C[V[j-1]], 2) + pow(D[V[j]]-D[V[j-1]], 2))/s;
}else{
sum += sqrt(pow(C[V[j]]-A[V[j-1]], 2) + pow(D[V[j]]-B[V[j-1]], 2))/s;
}
}else{
sum += sqrt(pow(C[V[j]], 2) + pow(D[V[j]], 2))/s;
}
}
}
minv = min(minv, sum);
}
}while(next_permutation(V.begin(), V.end()));
printf("%.9lf\n", minv);
return 0;
}
E: Sensor Optimization Dilemma 2
解法
- 答えを二分探索する
- 機械
とS_i の導入数の求め方に注意するT_i - 機械
のほうがコスパが悪いとき、 機械S_i の導入台数は必ずS_i 台未満となるB_i -
台 の機械B_i による製造能力 (S_i ) は、A_i \times B_i 台の機械A_i による製造能力 (T_i ) で代替できるからB_i \times A_i
-
- 機械
のほうがコスパが悪いとき、 機械T_i の導入台数は必ずT_i 台未満となるA_i -
台 の機械A_i による製造能力 (T_i ) は、B_i \times A_i 台の機械B_i による製造能力 (S_i ) で代替できるからA_i \times B_i
-
- 機械
\lceil \frac{x}{y} \rceil = \lfloor \frac{x + y - 1}{y} \rfloor
ABC374E.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int n, x;
cin >> n >> x;
vector<int> A(n), P(n), B(n), Q(n);
for(int i=0; i<n; i++){
cin >> A[i] >> P[i] >> B[i] >> Q[i];
}
long long int low = -1, high = x*100+1;
while(high-low>1){
long long int mid = low + (high-low)/2;
bool flag = true;
long long int sum = 0;
for(int i=0; i<n; i++){
long long int a = 1e9, b = 1e9;
for(int j=0; j<A[i]; j++){
a = min(a, (long long int)j*Q[i] + ((max(0LL, mid-B[i]*j) + A[i] - 1)/A[i])*P[i]);
}
for(int j=0; j<B[i]; j++){
b = min(b, (long long int)j*P[i] + ((max(0LL, mid-A[i]*j) + B[i] - 1)/B[i])*Q[i]);
}
sum += min(a, b);
if(sum>x){
flag = false;
break;
}
}
if(flag){
low = mid;
}else{
high = mid;
}
}
cout << low << endl;
return 0;
}
Discussion